Das Problem des kürzesten Weges taucht nicht nur beim travelling salesperson problem (tsp) auf. Schaut man genauer auf die mögliche Modellierung vieler Probleme der KI, dann stellt man fest, dass man sie sehr oft als ein Problem des kürzesten Weges beschreiben kann. Das Problem an ihnen ist also nicht die Vielseitigkeit der Beschreibung und dass es etwa an Konzepten zur Lösung fehlen würde.
Wie wir schon betrachtet haben, führen die Versuche, das Problem des tsp mit vollständigen Algorithmen zu lösen, aus anderen Gründen in eine Sackgasse. Das Hauptproblem ist, dass diese Probleme einen exponentiellen Anstieg der Komplexität aufweisen.
Vielfach leicht zu überblicken sind Strategiespiele: Beim Mühle - Spiel beispielsweise hat man für das Setzen des ersten Steines 24 Möglichkeiten, für den vom Gegner gesetzten zweiten dann noch 23 usw.
Selbst dann, wenn man wie beim Mühle - Spiel keine Wiederholungen von Positionen zulässt, werden es schnell sehr viele Möglichkeiten. Allein für die ersten 8 Züge ergibt sich -selbst wenn man die Reihenfolge ausser Acht lassen könnte- 24*23*22*21*20*19*18*17/8*7*6*5*4*2*2*1 ~ 800.000 oder mit einer einfacheren Abschätzung von 20/4 8 mit 390.625 eine in der Grössenordnung nicht viel andere Zahl. Und dann hat jeder Spieler bestenfalls vier Steine auf dem Brett stehen ! Bei vielen anderen realen Problemen ist die Zahl der Wahlmöglichkeiten noch viel größer !
In einem solchen Fall alle Nachfolger einer Ecke im Graphen erzeugen zu wollen, muss fehlschlagen.
Wie kann man Erfolg versprechender vorgehen?