Uniform-Cost-Suche: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springenK (1 Versionen) |
(→Ablauf) |
||
| 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 == | ||
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.
