Uniform-Cost-Suche

Aus Byte-Welt Wiki
Version vom 25. Juli 2007, 16:10 Uhr von EagleEye (Diskussion | Beiträge) (Nachteil)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springenZur Suche springen

Die Uniform-Cost-Suche, ist ein Sucherverfahren um Bäume zu durchsuchen. Sie zählt zu den uninformierten Suchen und ist unter gewissen Bedingungen vollständing und optimal.

Ablauf

  • Es wird ein Startknoten gewählt und expandiert.
  • Die neu erscheindenen Knoten werden anhand ihrer Kosten sortiert in eine Queue eingereiht, so dass immer der Knoten mit den kleinsten Kosten als nächster Knoten gewählt wird.
  • Sollte das Ziel nicht bei diesen Knoten sein, wird der Knoten mit den gringstens Kosten ausgewählt und expandiert.
  • Die neuen Knoten werden wieder in die Queue eingereiht und es wird nachgesehen ob das Ziel dabei ist.
  • Sollte es nicht der Fall sein wird dieser Schritt wiederholt bis das Ziel gefunden wurde.

Nachteil

Diese Suche kann vollständig sein, muss es jedoch nicht.

  • Problem: Wenn ein Knoten immer die Hälfte der Kosten des Vorgängers hat, ist es möglich in eine Endlosschleife zu geraten und/oder nicht den optimalen Weg zu finden.