Hej.
Od kilku dni bawię się w algorytmy takie jak A*, Dijkstra.
Wszystko działa fajnie ale załóżmy mam 10 miast. Chcę z Wawy jechać taką konfiguracją miast aby żadnego miasta nie odwiedzić więcej niż raz najszybszą możliwą trasą i wrócić do Wawy na końcu.
Jest na to jakiś sprawdzony sposób ?
Dijkstra działa ale bez punktu powrotu z tylko z A do B, podobnie A*. Chyba, ze ja coś mylę i czegoś nie rozumiem.
Nie chcę gotowego rozwiązania, proszę aby ktoś mnie naprowadził jak do tego można dojść.
Brzmi jak problem komiwojażera.
W sumie to co kolega powyżej tylko musisz wziąć pod uwagę, że graf jest skierowany, bo jednak nie masz nieskończonej ilości dróg do każdego miasta.
No dijkstra działa tak, że znajdzie najkrótszą drogę w grafie i pominie wszystkie inne.
Czyli powrotną też znajdzie najkrótszą, czyli wszystko się zgadza.
Ale dodałeś kilka szczegółów, czyli nie mogą być miasta więcej niż raz odwiedzone i muszą być jakieś miasta odwiedzone, a nie tylko najkrótsza droga do danego miejsca.
To rodzi wiele problemów, jak użyjesz dijistry to znajdzie krótką drogę, ale kilka razy przejdziesz przez te same miasta, musiałbyś warunek dać, że jak jakieś miasto było odwiedzone to przy rozwiązaniu nie uwzględniasz, wtedy wyjdą nawet gorsze rozwiazania bo może być tak, że najlepsze i najszybsza trasa jest jeśli się powtarzają miasta tak może być.
jak dobre constraints zrobisz to jakoś to rozwiążesz, jest coś takiego jak cfs constraints satiscfatcion problem, jak masz dobre ograniczenia to można wyliczyć łatwo grafem możliwe rozwiązania, dalej problem może być trudny do rozwiązania i przez ograniczenia jakie nałożysz jeszcze trudniejszy.
Jest na to jakiś sprawdzony sposób ?
Nie wiadomo. Odpowiedź na to pytanie jest warta conajmniej milion dolarów.
Tak jak @yarel pisał to problem komiwojażera. On ma wykładniczą złożoność, są algorytmy które potrafią znaleźć rozwiązanie z błędem nie większym od X od optymalnego rozwiązania, ale pewną odpowiedź da tylko brute-force, który będzie za wolny.