Ich habe eine Menge von mit unterschiedlich langen Straßen untereinander verbundenen Städten und will möglichst schnell von Stadt A nach Stadt Z kommen. Das beste Ergebnis kriegt man, indem man alle möglichen Wege durchprobiert (und ggf. abbricht, wenn man schon beim Probieren sieht, daß der aktuelle Weg zu lang wird), aber das ist zeitaufwändig.
Eine mögliche Heuristik sieht für alle an die aktuelle Stadt angrenzenden Städte nach, wie viele Städte sich zwischen der untersuchten und der Zielstadt befinden und wählt dann als nächste anzufahrende Stadt die aus, bei der diese Zahl am gerinsten ist. Damit kann man einige ganz schlechte Wege ausschließen und es ist schneller, als alles durchzuprobieren, aber optimal ist es nicht. Tatsächlich läßt sich ganz einfach ein Fall konstruieren, bei dem die Heuristik ein schlechtes Ergebnis liefert:
Die Heuristik nimmt alle an A angrenzenden Städte (also B und Z) und bestimmt, wie weit diese jeweils vom Ziel entfernt sind (B: 1 Schritt, Z: 0 Schritte). Da 0 < 1 wird Z als nächster Schritt ausgewählt und die Heuristik liefert als "besten" Weg A->Z, obwohl A->B->Z deutlich kürzer wäre.
Ja, das ist eine dumme Heuristik, aber sie ist schnell. Und sobald man in 100.000 "Städten" einen halbwegs optimalen Weg finden will, kann es sein, daß man den Qualitätsverlust beim Endergebnis in Kauf nimmt, nur damit man statt einem Tag fünf Minuten Rechenzeit braucht.