Das folgende Beispiel eines sehr einfachen hill climbing - Verfahrens zum tsp - Problem zeigt sehr schön, wie das Verfahren in einer Sackgasse, einem lokalen Minimum der Länge, landet:
Das Verfahren arbeitet mit einem dem Bubble - Sort ähnlichen Algorithmus. Es erreicht eine lokale Verbesserung durch den Tausch zweier benachbarter Knoten :
>>> t(0) t(1) ... t(k) t(k+1) ... t(n) wird getauscht zu: >>> t(0) t(1) ... t(k+1) t(k) ... t(n)
Das dargestellte Bild ist nicht etwa das Startbild, sondern das Ergebnis (Gesamtverbesserung ca. 30%). Beim letzten durchgeführten Durchlauf hat das Programm festgestellt, dass keine Verbesserung mit dem Verfahren mehr erzielt werden konnte. Es ist offensichtlich, dass und warum es in einem lokalen Minimum der Länge hängen bleibt.
ProgrammDa der erste und der letzte Knoten in der tour identisch sein müssen, dürfen sie nicht getauscht werden.
Aber selbst die verbesserte Variante, bei der ganze Wegabschnitte getauscht werden können, erreicht nicht das Ziel, wie das folgende Bild zeigt: