wefhy Temat założony przez niniejszego użytkownika |
Szukam algorytmu najkrótszej drogi między końcami wielu odcinków » 2015-08-27 22:02:11 Szukam czegoś, co naprowadzi mnie na algorytm znalezienia najkrótszej drogi między końcami kilku(-nastu/-dziesięciu) odcinków. Problem wygląda następująco: Mam zbiór n odcinków(max 50-60). Każdy odcinek ma swój początek i koniec zapisany współrzędnymi. Można go przebyć w obie strony. Celem jest przebycie każdego odcinka w jedną ze stron oraz drogi między tymi wierzchołkami w jak najkrótszym czasie. W praktyce każdaz możliwych dróg zawiera w sobie długość odcinków, więc jest ona pomijalna, a liczy się odległość między kolejnymi odcinkami. Jedna z dróg np: Każdy odcinek ma końce A i B. Zaczynamy od punktu A pierwszego odcinka. Następnie z punktu B pierwszego odcinka musimy dotrzeć do punktu B drugiego odcinka, z punktu A drugiego odcinka do punktu B czwartego, a z punktu A czwartego do punktu A trzeciego itd. Nie mam pomysłu na znalezienie najkrótszej z tych dróg poza starą, dobrą metodą Brute force. Tyle że tych kombinacji jest sporo i o ile przy 10 odcinkach nie robi to problemu, to przy 30-u już jest gorzej i z każdym kolejnym odcinkiem czas się zwielokratnia. {{x1,y1},{x2,y2}} Tablica[ 5 ][ 2 ][ 2 ] = {
{ { 40, 0 }, { 40, 20 } },
{ { 40, 10 }, { 60, 10 } },
{ { 40, 10 }, { 65, 20 } },
{ { 65, 15 }, { 90, 15 } },
{ { 80, 0 }, { 80, 20 } }
}; Myślałem nad tym, czy nie da się użyć faktu, że 0<Y<20(wszystkie odcinki mieszczą się w pewnym obszarze...), a |X2-X1|<30(...i nie są zbyt długie) i w ten sposób ustalić jako taką kolejność odcinków, co umożliwiło by podzielenie ich na grupy, ale... wierzę, że da się jakoś wydajniej i dokładniej. Jedyny algorytm, którego umiem używać to flood fill, tu bezużyteczny, bo trzeba zaliczyć wszystkie punkty w dowolnej kolejności. Strzelam, że powinienem szukać gdzieś wśród algorytmów rozwiązywania grafów, ale kilka przeanalizowałem i nie widzę możliwości ich implementacji(nawet nie wiem, jakiego rodzaju graf mam). |
|
darko202 |
» 2015-08-28 10:37:06 |
|
wefhy Temat założony przez niniejszego użytkownika |
» 2015-08-28 12:37:17 Dzięki, trochę popatrzyłem, ale nie idzie mi. Wszystko co opisywane pokazuje możliwość znalezienia jakiejkolwiek najkrótszej drogi, a mnie interesuje ta, ktora przebiega przez wszystkie odcinki. Jednak kierując się wskazówkami i logiką udało mi się przekształcić mój problem na graf. Uznałem, że droga 1A->2B->3B to droga między punktami: 1A->1B->2B->2A->3B->3A, czyli między kolejnymi odcinkami oznaczeniem jest jego PIERWSZY punkt. Ogólnie... nie ma znaczenia, jak, ważne, że umiem to zastosować do dowolnej liczby odcinków ;) W rezultacie wyszedł mi graf, w którym mam podaną drogę w każdą stronę z każdego punktu do każdego. Celem jest przejechanie przez punkt (1A lub 1B) oraz (2A lub 2B) oraz (3A lub 3B) http://snag.gy/kG7RP.jpg[/img] [url]http://snag.gy/kG7RP.jpg[/url] I ewentualnie przed chwilą przyszło mi do głowy inne, być może prostsze zobrazowanie. W tym wypadku punktów jest o 50% więcej, ale należy przejść przez wszystkie i droga w obie strony ma tą samą wartość.: http://snag.gy/CyCX0.jpg[/img] [url]http://snag.gy/CyCX0.jpg[/url] Przepraszam, chyba nie umiem na tym forum wstawić grafiki |
|
darko202 |
» 2015-08-28 13:38:09 |
|
wefhy Temat założony przez niniejszego użytkownika |
» 2015-08-28 21:41:51 Hamiltonowskie chyba rozwiązują sprawę. A właściwie całkowicie nie rozwiązują, bo z tego co widzę, jedyną metodą jest brutalne sprawdzenie wszystkich możliwych dróg(przynajmniej wiem, że nic lepszego nie wymyślę :D). Wychodzi na to, że nie wyrobię się z obliczeniami w rozsądnym czasie i będę musiał samemu pomyśleć, jak rozbić algorytm na fragmenty i znaleźć "prawie" optymalną drogę korzystając po części z podpowiedzi.
Niezależnie od rezultatu, wiele z tego co przeczytałem na pewno się kiedyś przyda, a pewnie i teraz pomoże mi zrobić znacznie wydajniejszy kod.
Tak, czy inaczej dzięki za pomoc. Jak uda mi się zrobić coś, co będzie działało zaskakująco dobrze, to się podzielę wynikami ;)
PS Link nie działa, wstawiam w poprawnej formie, żeby nie trzeba było potem szukać: http://www.kaims.pl/~deren/gms/wyklady/04_kom_opt.pdf |
|
| « 1 » |