[Algorytmika] Najkrótsza trasa

Witam,

Wiem, ze pojawilo sie wiele postow odnoscnie algorytmow wyszukiwania najkrotszej trasy, jednak nie moge znalezc odpowiedz na meczace mnie pytanie.
Czy istnieje algorytm na wyznaczenie najkrotszej trasy przez punkty (znajdujace sie np. w tablicy kwadratowej), gdy nie jest dla nas wazne, ktory punkt jest punktem poczatkowym, a ktory koncowym (punkt poczatkowy na pewno nie jest punktem koncowym), z uwzglednieniem faktu, ze trasa musi przejsc przez kazdy punkt? To tak jakbysmy chcieli zaplanowac sobie podroz po swiecie, zwiedzajac Polske, Wlochy, Brazylie, Kanade, Indie, Argentyne, Kenie, RPA, Japonie i chcemy znalezc z jakiego punktu najlepiej zaczac, przez jakie przejechac i w jakim skonczyc, by trasa byla najkrotsza. Czy w tym przypadku musze przesledzic wszystkie mozliwe opcje i w ten sposob zadecyduje o najkrotszej trasie? (brzmi bardzo nieoptymalnie)

Drugie pytanie to, jakiego algorytmu (znow - o ile istnieje) uzyc, gdy wiem, ze wyruszam z danego miejsca, nie jest ono natomiast miejscem koncowym podrozy. Czyli startuje z Polski, chce zobaczyc wszystkie kraje i w tym ostatnim (na mojej najkrotszej trasie z Polski) sie osiedlic;)?

Pozdrawiam,
Fsh

Co do drugiego:
http://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera
A jeżeli chodzi o pierwsze to wydaje mi się, że jest uogólnieniem tego drugiego i też jest problemem NP-trudnym

Pierwsze: można użyć algorytmu genetycznego dla problemów bardzo złożonych, dla mniejszych, bruteforce sie nada :P
Drugie: Dijkstra ?

Jak już powiedziano: oba problemy to pewne uproszczenie Problemu Komiwojażera i nie ma to algorytmu.

Dijkstra tutaj nic nie da, bo on znajdzie ci najkrótsze drogi z miasta A do każdego innego miasta.

„Nie ma na to algorytmu” jest nieprawdą; algorytm oczywiście jest, tylko już dla rozsądnie dużej liczby punktów liczenie będzie trwało nierozsądnie długo.

Zgodnie z taką logiką to "na wszystko jest algorytm".
Powiedzmy inaczej: nie ma algorytmu wielomianowego rozwiązującego ten problem.

Shalom napisał(a)

Zgodnie z taką logiką to "na wszystko jest algorytm".

To już Turing wykazał; zresztą nie na wszystko, nie istnieje rozwiązanie np. problemu stopu.

Powiedzmy inaczej: nie ma algorytmu wielomianowego rozwiązującego ten problem.

Ściślej: nie jest znany taki algorytm, i nie wiadomo czy istnieje.

Wielkie dzieki za odpowiedz.

W sumie ilosc danych do przetworzenia nie jest duza, wiec chyba ten bruteforce to i tak byloby najodpowiedniejsze wyjscie.

Tak jak powiedział marseel, problem komiwojażera(algorytm genetyczny) sam wczoraj skończyłem taki algorytm :) trochę się męczyłem ale w końcu działa :) jeśli chcesz napisać taki program tu masz link do tego, jak tego dokonać :) http://www.k0pper.republika.pl/geny.htm