Es wird ein Suchbaum mit einer Kostenfunktion eingesetzt, um den idealsten Pfad zu finden. In die Kostenfunktion fließen ein:
- die Kosten für eine neue Kante
- die legal gangbaren Kanten
- das Halten bei dem letzten Knoten
Wir können ,,branch and bound'' verwenden, um die Suche zu beschleunigen.
Ausgesuchter Pfad soll den gewünschten Pfad möglichst gut approximieren. Die oben genannte Kostenfunktion wird über den quadratischen Abstand definiert.