Uniform-Cost-Suche

Aus Byte-Welt Wiki
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.