Uniform-Cost-Suche: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen (→Nachteil) |
|||
| (2 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 2: | Zeile 2: | ||
== Ablauf == | == 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. | + | *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 == | == 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.
