Uniform-Cost-Suche

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.