|
TwojePC.pl © 2001 - 2025
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
[OT} Optymalny algorytm wyszukiwania ścieżek w zróżnicowanym terenie , Mcmumin 20/04/10 00:29
Męczę się z tym cały dzisiejszy dzień. Przejrzałem sporo zasobów internetowych na ten temat i jakoś nie znalazłem optymalnego algorytmu. Najczęściej wykorzystywany jest algorytm A* (wariacja algorytmu Dijkstry - Best-First-Search z heurystyką). Sprawdza się dobrze w bardzo uproszczonych sytuacjach. Np:
gdzie pola o są otwarte, X jest przeszkodą, S - start, E - koniec trasy
ooooooooooooooo
ooooooooooooooo
oooooooXXoooooo
SooooooXXoooooo
oooooooXXoooooo
oooooooXXoooooE
oooooooXXoooooo
ooooooooooooooo
gorzej sytuacja wygląda w chwili, gdy przemieszczanie się po polach mapy "kosztuje" określoną i zmienną ilość punktów ruchu. Np:
S - start, E - punkt końcowy, a poszczególne cyfry oznaczają koszt ruchu
S86E
3863
3863
3863
3863
3863
3863
3333
Sama heurystyka jest dość prosta - każdy punkt do którego docieramy przeliczną ma wartość F = koszt dotarcia z punktu S + odległość do punktu końcowego w linii prostej. Eliminujemy pola o większym koszcie ruchu, jeżeli do określonego pola docieramy ponownie, wybieramy ścieżkę o mniejszym współczynniku F.
W tej sytuacji pola w 2 i 3 kolumnie są eliminowane przy początkowej kalkulacji przez algorytm i jednostka zmierza do celu po "najmniejszej linii oporu" czyli po polach o wartości 3, co z przyczyn oczywistych nie jest najbardziej optymalną ścieżką. Alternatywą jest przeszukiwanie wszystkich pól sąsiednich dla aktualnej pozycji, ale jest do dość kosztowny algorytm, szczególnie w sytuacji gdy kod pisany jest w JavaScripcie :)- Yyy... , Bergerac 20/04/10 00:33
Que?
...
Hmm...
...
Generalnie... w zróżnicowanym terenie poruszam się przy pomocy mapy, o ile jestem tam po raz pierwszy.
Czekaj, czekaj... Był taki wątek o grze strategicznej a la Panzer Cośtam. To o to chodzi?Barbossa: You're supposed to be dead!
Jack Sparrow: Am I not? - Dokładnie :) Jak będę wybierał się w beskidy, to zapytam , Mcmumin 20/04/10 00:48
najwyżej o dobry punkt S z wygodnymi łóżkami i dostępnym prysznicem :)- Tylko pojedź w dobrym czasie , Bergerac 20/04/10 03:00
żeby nie trafić na same X :)Barbossa: You're supposed to be dead!
Jack Sparrow: Am I not?
- jaka heurystyka , myszon 20/04/10 08:33
taka szybkość algorytmu. Jak masz bardzo skomplikowany teren to właśnie heurystyka może Cię w kozi róg zaprowadzić (np. jak musisz iść po trasie w kształcie "S"). Aaaa nie zakładaj, że algorytm od razu zacznie iść w prawo. On musi sobie trochę poszukać, żeby dojść do końca. Najpierw zaimplementuj sobie klasycznego Dijkstrę i zobacz ile mu się zejdzie. Potem dodaj heurystykę. Możesz próbować F = koszt dotarcia z punktu S + odległość do punktu końcowego w linii prostej/2 i tym podobne warianty. Może da się to jakoś rozbić na mniejsze zadania i potem posklejać.- !!! odpowiednie dobranie wag (/2, /3, /4) w zależności od finalnej odległości , Mcmumin 20/04/10 18:05
i ścieżka ładna i... Średnio 200x szybciej niż przy badaniu wszystkich kombinacji!
- a mi sie , kerad555 20/04/10 09:22
to kojarzy z ,,problemem komiwojażera,,Pozdrawiam,
( K | e | r | a | d | 5 | 5 | 5 ) - oczywiscie , kerad555 20/04/10 09:29
odpowiednio zmodyfikowany - tworzysz odpowiedni graf w węzłach masz koszt i szukasz najkrótszej ścieżki z S do EPozdrawiam,
( K | e | r | a | d | 5 | 5 | 5 ) - hmm , recydywista 20/04/10 21:18
Nie bardzo, przecież w problemie komiwojażera masz odwiedzić wszystkie wierzchołki. Tutaj jest klasyczne poszukiwanie najkótszej ścieżki.
Funkcja heurystyczna tutaj to podstawa (niekoniecznie musi to być wprost odległość od punktu końcowego), także istotne jest początkowe dobranie wag krawędzi.Computers are useless. They can only
give you
answers.
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2025, TwojePC.PL |
 |
|
|
|
