Algorytm Komiwojażera

Witam,
Mam do napisania program, który rozwiąże problem komiwojażera.
Program wczytuje 5 punktów i oblicza długości odcinków
(AB, AC, AD, AE, BC, BD, BE, CD, CE, DE)

Komiwojażer wyrusza z punktu A. Wszystko do tego momentu działa fajnie, tylko mam teraz problem z dobieraniem odcinków.
Algorytm ma wybierać najkrótsze odcinki, czyli oblicza długości odcinków i widzi, że z punktu A ma najbliżej np. do punktu D, więc udaje się do punktu D. I teraz pojawia się problem, ponieważ nie wiem jak wykluczyć punkt A z kolejnych obliczeń, czyli żeby program nie brał już pod uwagę długości odcinka AD, bo po obliczeniu okazuje się, że najbliżej ma do punktu A, wraca do niego i się zapętla.

Jeśli ktoś ma jakąś wskazówkę to z góry dziękuję i pozdrawiam ;)

Zapisuj w tablicy wykluczone punkty?

Hm, ok. Powiem tak, z programowaniem nie mam ogólnie raczej nic wspólnego. Próbuję napisać program o własnych siłach i udało mi się go napisać do połowy. Wiem, że to pewnie nie jest nic trudnego, ale jakby mógł ktoś wyjaśnić chociaż w przybliżeniu jak zastosować te tablice, byłoby naprawdę fajnie.
Z góry dzięki za pomoc ;)

Metoda przedstawiona przez Ciebie, to znajdowanie najkrótszej drogi w grafie - ale działa tylko gdy wierzchołek początkowy jest różny od końcowego i nie ma nic wspólnego z problemem komiwojażera. Rozwiązanie Twojego problemu nie jest tak proste:  musisz przeszukać wszystkie cykle Hamiltona i wybrać cykl o najmniejszej wadze (suma odległości). Zazwyczaj robi się to przez programowanie z powrotami. Najgorszą metodą w sensie złożoności czasowej, ale najłatwiejszą do zaimplementowania będzie wygenerowanie wszystkich cykli (temat z działu permutacje) pięciu punktów, a następnie sprawdzenie, czy pomiędzy wszystkimi sąsiednimi wierzchołkami cyklu jest odcinek łączący (czyli, czy jest możliwość przejścia miast w kolejności wymienionej w cyklu) i obliczenie długości drogi dla tego cyklu. Cykl z najkrótszą drogą jest rozwiązaniem.

Temat jest stary, ale dla może ten komentarz pomoże komuś innemu: jednym ze sposobów rozwiązania problemu komiwojażera jest zastosowanie mutacji/krzyżowania. Przykładowa logika działania z zastosowaniem samej mutacji jest następująca:
1. wygeneruj x (około 20-50) osobników o losowej trasie pomiędzy wszystkimi istniejącymi punktami
2. oblicz wartość funkcji celu dla każdego z nich (w naszym przypadku wynikiem działania funkcji celu jest długość trasy każdego z osobników - im ta wartość jest mniejsza, tym lepiej)
3. wybierz y (np. 5) najlepszych osobników. Przejdą oni do kolejnej generacji nienaruszeni oraz będą rodzicami dla wszystkich pozostałych, nowych osobników z kolejnej generacji
4. w najprostszym modelu każdy z 5 najlepszych osobników będzie miał tyle samo dzieci (np. jeśli mamy w sumie 50 osobników na generację, to 5 najlepszych będzie miało po 9 dzieci, co da 45 dzieci, oraz sami przejdą dalej, co daje 50 osobników w nowej generacji). Utworzenie dziecka polega na skopiowaniu trasy rodzica, a następnie losowej zamianie miejscami kilku z pozycji. Istotnym jest dobranie odpowiedniego natężenia mutacji, nie za małego i nie za dużego. Podczas moich eksperymentów doszedłem do wniosku, że niezłym rozwiązaniem jest 100% szans na pierwszą mutację i malejąca szansa na każdą kolejną w ramach tego samego dziecka (~60%, ~35%, ~15%, aż do ~0,5% przy mutacji ~10 rzędu). Mało prawdopodobne mutacje wyższych rzędów służą wyskakiwaniu z ekstremów lokalnych, czyli rozwiązań optymalnych lokalnie, ale nieoptymalnych globalnie.
5. powtarzaj punkty 2-4 przez Z (kilkaset) kroków. Najlepszy osobnik z generacji numer Z jest wynikiem działania tego podejścia algorytmu i jest to rozwiązanie dobre, ale niekoniecznie najlepsze. Warto jest puścić algorytm kilkanaście-kilkadziesiąt razy, bo bardzo często taki algorytm zbiega do różnych wartości, zależnie od tego, jaka wylosuje się populacja początkowa oraz jaką losową drogę obiorą mutacje w kolejnych krokach.

Program działający w ten sposób przy 15 miastach (czyli ilość możliwych tras rzędu 10^12) zapewniał mi poprawne rozwiązanie raz na 10-15 prób, a w pozostałych przypadkach zapewniał mi rozwiązanie o około 5% gorsze od poprawnego. Ilość obliczeń do wykonania w porównaniu do metody analitycznej jest o wiele rzędów wielkości mniejsza.

Jednak podkreślam, że nigdy nie można być pewnym, czy otrzymaliśmy poprawne rozwiązanie, korzystając z tej metody. Dla małych ilości punktów metoda analityczna jest niezastąpiona, ale wraz ze wzrostem punktów bardzo gwałtownie rośnie liczba możliwych tras:
5 punktów - 5! = 120 możliwych tras
10 punktów - 10! = ok. 3,6 miliona możliwych tras
15 punktów - 15! = ok. 1,3 biliona możliwych tras
20 punktów = 20! = ok. 2,4 tryliona możliwych tras

Jak widać, gdybyśmy chcieli łopatologiczną metodą analityczną określić najkrótszą drogę między 30 miastami, prawdopodobnie zajęłoby nam to kilka dni na domowym pececie, a gdybyśmy chcieli łopatologicznie-analitycznie wyznaczyć najkrótszą drogę pomiędzy 50 miastami na domowym pececie, nie starczyłoby nam życia. I tutaj wchodzą algorytmy genetyczne, które skracają czas obliczeń o kilka, kilkanaście lub nawet kilkadziesiąt rzędów wielkości, zapewniając na koniec odpowiedź zbliżoną do poprawnej (lub poprawną, ale nigdy nie możemy być tego pewni).