W nowej wersji programu dodałem kolejne obliczenia, niestety wydłużyło to czas oczekiwania na wynik.
Na początku wszystko jest jak poprzednio, pierwszy przebieg to obliczenie wszystkich odległości od punktu startowego. Następnie wyszukiwana jest najkrótsza odległość, która staje się punktem startowym i ponownie obliczana jest odległość do wszystkich punktów z pominięciem tych, które już były punktem startowym. W ten sposób po nitce do kłębka dochodzimy do punktu początkowego, który staje się końcowym. Wynik jest trochę lepszy, odległość po wpisaniu Ciężkowice, Tuchów, Tarnów, Jasło w pierwszym artykule wynosiła 184,5 km, a obecnie jest to wynik 182,1 km.
Nadal taki wynik mnie nie satysfakcjonuje, pojawia się również problem, jeśli kilka punktów będzie oddalone od siebie w różnych stronach. Mogą zostać pominięte i program wróci do nich na końcu. Poniżej dwa zrzuty, gdzie na drugim zaznaczyłem kolejność wykonywania obliczeń.





Nagrałem w formie prezentacji film na youtube

W ostatnim czasie zainteresował mnie temat map Google i tworzenie programów z tym związanych. Pomyślałem aby zrobić swoją aplikację do której będę mógł wkleić w losowy sposób adresy miejscowości, a program sam ułoży je w odpowiedniej kolejności i pokaże optymalną trasę przejazdu z przypisanego wcześniej punktu startowego i powrotem do niego. Pojęcie to nazywane jest "Problemem komiwojażera".

Program zacząłem pisać w C# wykorzystując bibliotekę GMap. Liczbę możliwych do wpisania miast ograniczyłem na ten moment do 40, ponieważ w przypadku źle wykonanej pętli bałem się wykorzystania wszystkich środków na koncie. Wynika to z tego, że aby móc pisać programy oparte o mapy Google trzeba podpiąć do nich kartę płatniczą.

W przypadku pierwszej wersji programu poszedłem na łatwiznę. Po wpisaniu różnych adresów obliczam odległość od punktu startowego, do każdego z nich. W ten sposób ustaliłem kolejność od najmniejszej odległości do największej i w takiej kolejności wyznaczyłem trasę.

Nie wyszło to najgorzej, o dziwo w sporej liczbie przypadków trasa jest bardzo dobra, jak w przypadku poniżej. Można również wpisywać nazwy firm zamiast adresu i Google również je rozpoznaje na mapie. Niebieskim kolorem wyznaczyłem trasę powrotną do punktu startowego, w moim przypadku będzie to Zamek w Melsztynie.


Problem pojawia się wtedy, kiedy bardziej rozrzucimy nasze adresy. W podanym niżej przypadku program pokierował najpierw do Ciężkowic, które uznał, że są najbliżej, następnie do Tarnowa, a potem tą samą drogą kazał wracać do Tuchowa, pomimo że już przez niego przejeżdżaliśmy. Według mnie najpierw powinniśmy jechać do Tarnowa, potem do Tuchowa (lub odwrotnie najpierw Tuchów, potem Tarnów), następnie do Jasła i na powrocie odwiedzić Ciężkowice.


Kolejna wersja programu próbująca rozwiązać ten problem pojawi się w kolejnym artykule.