Uniform-Cost-Suche: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen (→Ablauf) |
(→Nachteil) |
||
| Zeile 10: | Zeile 10: | ||
== Nachteil == | == Nachteil == | ||
Diese Suche kann vollständig sein, muss es jedoch nicht. | 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. | ||
[[Kategorie:Suchalgorithmus]] | [[Kategorie:Suchalgorithmus]] | ||
Aktuelle Version vom 25. Juli 2007, 16:10 Uhr
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.
