Mam problem, w mojej pracy na temat problemu komiwojażera muszę rozwiązać zadanie za pomocą algorytmu "droga do najbliższego sąsiada". Ogólnie rozumiem jak działa taki algorytm, wybieramy zawsze najbliższy nie dołączony jeszcze wierzchołek, jednak problem leży w tym, iż w mojej macierzy odległości już na starcie spotykam się z sytuacją że najbliższa odległość pojawia się dwa razy (tzn odległość z punktu startowego jest taka sama jak do miejscowości A i D). Co w takiej sytuacji? Jak rozwiązać to zadanie?

Witam,

co prawda nie znamy treści zadania, ale wg mnie należałoby sprawdzić jakie odległości pojawiają się w przypadku następnych miejscowości oraz z której z nich uda się zamknąć cykl. Należy mieć świadomość, że algorytm najbliższego sąsiada nie daje gwarancji znalezienia najlepszego z możliwych rozwiązań.
Proponuję zajrzeć np. do książki: Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010.

Pozdrawiam
ŁP