pytanie jaki algptytm zastosowac - najkrotsza droga

0

problem taki: mam jakies miasto, ktore ma iestam miejsc i dwukierunkowe drogi miedzy tymi punktami, miedzy dwoma punktami moze byc wiecej niz jedna droga (moge brac tylko ta najkrotsza a reszty nie brac od uwage?), punkt nie ma drogi do samego siebie, mam objechac od startu do startu cale miasto (wszystkie miejsca) zeby byla jak najkrotsza droga
moje pytanieto jaki algorytm zastosowac, bo nie wiem, ale chce napisac sam i troche poczytac o takich zadankach
pozdrwawiam

0

To sie nazywa "problem komiwojażera", na necie znajdziesz sporo na ten temat. Ciekawym rozwiązaniem jest zastosowanie algorytmu genetycznego.

0

Problem komiwojazera bylby, gdyby w kazdym punkcie mogl byc raz i tylko raz. To jest problem najkrotszej drogi czyli algorytmy Dijkstry i Bellmana-Forda na przyklad.

pozdrawiam
johny

0

Mam napisane ze w drodze ktora wyznacze kazdy punkt musi byc inny, i jednoczesnie droga ma byc najkrotsza. Do tego mam zaczas w punkcie 1 i w nim skoncyzc. Czy ktos potrafi powiedziec jakiego algorytmu uzyc konkretnie?
Dzieki za dotychczasowa pomoc, troche sie juz poczytalo :)

0

Ach sorry, nie zauwazylem, ze masz objechac wszystkie miejsca i ze startu do startu. To rzeczywiscie komiwojazer. @adf88 - zwracam honor :) I najbardziej skuteczny (oprocz klasycznego niewielomianowego) jest genetyczny z tego co wiem.

pozdrawiam
johny

0
johny_bravo napisał(a)

najbardziej skuteczny (oprocz klasycznego niewielomianowego) jest genetyczny.

I z tego co wiem nie do końca dokładny, więc jeżeli piszesz na jakiś konkurs to zostaje generowanie dróg brute forcem.

0

No tak, niedokladny - jedyny znany dajacy zawsze poprawna odpowiedz jest nieoptymalny - O(n!).

pozdrawiam
johny

1 użytkowników online, w tym zalogowanych: 0, gości: 1