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.

• 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.

Nachteil

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