pytanie jaki algptytm zastosowac - najkrotsza droga

Odpowiedz Nowy wątek
2006-10-21 23:59
ktos kto nie wie
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

Pozostało 580 znaków

2006-10-22 00:24
0

Np. tu http://www.algorytm.org/index[...]=view&id=91&Itemid=28

pozdrawiam
johny


You need to learn how to walk
before you can run

Pozostało 580 znaków

2006-10-22 09:30
0

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

Pozostało 580 znaków

2006-10-22 10:06
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


You need to learn how to walk
before you can run

Pozostało 580 znaków

2006-10-22 11:48
ktos kto nie wie
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 :)

Pozostało 580 znaków

2006-10-22 12:45
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


You need to learn how to walk
before you can run

Pozostało 580 znaków

2006-10-22 13:21
abcde
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.

Pozostało 580 znaków

2006-10-22 13:26
0

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

pozdrawiam
johny


You need to learn how to walk
before you can run

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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