Program planujący trasę kuriera przez 30 miast nie sprawdza wszystkich możliwych tras, lecz z każdego miasta jedzie do najbliższego jeszcze nieodwiedzonego. Co można powiedzieć o tej metodzie?

Dlaczego tak

Problem komiwojażera dla 30 miast ma ok. 29!/2 różnych tras, więc przegląd zupełny jest niewykonalny w rozsądnym czasie. Metoda najbliższego sąsiada jest heurystyką zachłanną o złożoności O(n²): daje dobre rozwiązanie szybko, ale lokalnie najlepsze wybory nie muszą złożyć się na trasę optymalną. Przekonanie, że najkrótszy odcinek w każdym kroku daje najkrótszą całą trasę, to typowy błąd myślenia o algorytmach zachłannych.