Heuristiken sind dann notwendig, wenn es extrem viele Möglichkeiten (in unserem Beispiel Pfade) zu entdecken gibt. Dann kann man nämlich nicht mehr alle möglichen Kombinationen durchprobieren, da dies zu viel Zeit, Speicher oder sonstige Ressourcen in Anspruch nehmen würde. Also muss man vor allem die Pfade absuchen, welche am vielversprechensten scheinen.
In dieser Übung betrachten wir eine Heuristik, die die Anzahl der verbleibenden Sprünge zum Ziel schätzt. Dazu wird vom Ziel aus für jeden Knoten gezählt, wie viel Sprünge bis zum Ziel notwendig sind.
S → A → G
S → B → A → G wäre der schnellste Weg, da bei diesem Weg die Summe der Kosten der Kanten minimal ist. Dies zeigt, dass eine Heuristik allein nur eine Schätzung ist. Schätzungen können auch falsch liegen.
In dieser Übung betrachten wir eine Heuristik, die die verbleibende Distanz zum Ziel schätzt. Dazu wird vom Ziel aus für jeden Knoten gezählt, wie viel die kürzesten Wege bis zum Ziel kosten. Machen Sie dies, indem Sie die Kosten der Kanten der jeweiligen Wege aufaddieren. Dieser Prozess kann vom Ziel iterativ ausgeführt werden.
A(G → F → A): h=7
B(G → F → D → B): h=9
C(G → F → C): h=8
S(G → F → C → S): h=12
oder
S(G → F → D → B → S): h=12
Es gibt also zwei schnellste Wege vom Ziel zum Start.
Sie schauen, bei welchem der möglichen Kindknoten, die Sie von einem Knoten aus erreichen können, der Wert Heuristik des Kindknoten + Kantenkosten zum Kindknoten minimal ist.
Beispiel: Von B aus können wir S, A oder D erreichen.
S: Heuristik + Kantenkosten zum Kindknoten = 12 + 3 = 15
A: Heuristik + Kantenkosten zum Kindknoten = 7 + 6 = 13
D: Heuristik + Kantenkosten zum Kindknoten = 7 + 2 = 9
D besitz hier den minimalen Wert, ist also der nächste Knoten auf dem Weg zum Ziel.
Weil Sie die Distanzen vom Ziel aus oftmals noch gar nicht wissen. Für viele Probleme müssen Sie den Suchbaum und/oder den Graphen laufend aufbauen. Das Verfahren, welches Sie hier angewendet haben, lässt sich jedoch vom Start aus Problemlos ausführen. Dieses Verfahren heist Dijstras Algorithmus. Diesen Algorithmus lernen Sie auf der nächsten Seite.
In grossen Graphen ist es natürlich nicht mehr sinnvoll, von Hand Heuristiken einzutragen. Oftmals sind die Bäume dann auch zu gross, um alle Möglichkeiten durchzuprobieren. In diesem Fall werden Algorithmen in Kombination mit Heuristiken verwendet, um nur die erfolgsversprechendsten Teile eines Baumes zu untersuchen.
Es gibt viele Ansätze, die Sie hier verfolgen könnten. Ein naiver Ansatz wäre, einfach alles Wege durchzuprobieren. Dies funktioniert jedoch bei grossen Suchproblemen nicht mehr. Eine andere Möglichkeit wäre, die Distanz von jedem Knoten bis zum Ziel zu messen, und dies als Heuristik zu verwenden. Alternativ könnten Sie auch das Verfahren aus der Aufgabe 2 vom Start aus durchführen.