Pomocy! Implementacja algorytmu A*!

Pomocy! Implementacja algorytmu A*!
FJack
FJ
FJack
FJ
  • Rejestracja:ponad 8 lat
  • Ostatnio:prawie 8 lat
  • Postów:6
0

Mam problem otóż napisałem już dużo prób implementacji, jednak żadna nie działała poprawnie, główny problem mam z tym że np jeżeli jest taka sytuacja:
[ ] - pojedyncze pole
[S] - start
[M] - meta
[B] - blokada

[ ][ ][ ][ ][B][ ][ ][ ]
[S][ ][ ][ ][B][ ][ ][M]
[ ][ ][ ][ ][B][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

to mój skrypt pójdzie tak:

[ ][ ][ ][ ][B][ ][ ][ ]
[S][>][>][>][B][ ][>][M]
[ ][ ][ ][/][B][>][ ][ ]
[ ][ ][ ][ ][>][ ][ ][ ]

co nie jest najkrótszą drogą :(
powinien odświeżyć ścieżkę i znaleźć krótszą, ale nie wiem jak to zrobić. Proszę o pomoc, jeżeli ktoś mógłby to prosiłbym o jakiś prosty konsolowy przykład prawidłowego zaimplementowania algorytmu.
Dziękuję!

krzysiek050
Pokaż swoją implementację
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
FJack
FJ
FJack
FJ
  • Rejestracja:ponad 8 lat
  • Ostatnio:prawie 8 lat
  • Postów:6
0

http://pastebin.com/1a7s14Y0
To najnowsza i zarazem najgorsza. Nie działa wcale..

https://zapodaj.net/d730d2973c2d3.png.html
To stara implementacja w Unity, jak widać też nie działa dobrze.

edytowany 1x, ostatnio: FJack
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
topik92
T9
topik92
T9
  • Rejestracja:około 10 lat
  • Ostatnio:prawie 6 lat
  • Postów:329
2

masz zagnieżdżone 13 warunków(if/while/ for) nie dziwie się ze nie działa, podziel ten kod na mniejsze metody i pewnie sam odkryjesz co jest nie tak :).

edytowany 1x, ostatnio: topik92
FJ
Już z miesiąc się męczę z tą implementacją, proszę o pomoc...
T9
No i CI pomagam. Masz 13 zagnieżdżonych warunków a licząc &&(bo to w sumie to samo) to 20. Jak masz 1 warunek to masz dwie możliwości do rozpatrzenia, jak masz 2 zagnieżdżone warunki to masz cztery możliwości, jak masz 3 zagnieżdżone to osiem, a dla 20 masz MILION możliwych ścieżek egzekucji do rozpatrzenia. Człowiek potrafi ogarnąć 6-10 rzeczy naraz, w tej postaci za wiele nie wskórasz. Musisz robić tak ten kod rozbić by(poza trywialnymi przypadkami) nie było więcej niż 3 niezagnieżdżone if'y, w metodzie, tyle można w głowie ogarnąć.
T9
przy okazji ogarnij co robią skróty ctrl r,r; ctrl r,m; ctrl + shift + "-" ; ctrl + "-" ; f12; ctrl + tab ; ctrl + shift + tab; alt + tab będziesz miał 100% do produktywności
FJ
Chyba działa ale nie jestem pewien, jest jakiś ostateczny test sprawdzający poprawność kodu? kod: http://pastebin.com/W89nUTu6 zdj: https://zapodaj.net/49a9ed11ddf10.png.html
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
topik92
T9
topik92
T9
  • Rejestracja:około 10 lat
  • Ostatnio:prawie 6 lat
  • Postów:329
1

Do komentarzy wyżej, to że przerobiłeś

Kopiuj
 while(w1){ if(w1){ if(w3) { if(w4) itd. }}}

na while(w1){if(!w2)continue; if(!w3) continue; itd.. }

Kopiuj
 jest o niebo lepsze, zwłaszcza że te continu'y są jedne pod drugim na początku while'a ale to trochę tak zamiatanie śmieci pod dywan. Jest czyściej ale nie o to chodziło ;)

Twój algorytm działa dobrze, A* nie znajduje najkrótszej drogi to robi algorytm dijkstry, tylko drogę o najniższym przewidywanym koszcie. Twoja funkcja h jest jaka jest i taki masz wynik. Swoją drogą to że w funkcji H liczącej pozostała odległość iteracyjnie znajdujesz "wyjście" z labiryntu totalnie mi ja się z celem.

Ps. nie  pisze się warunków i tego co one robią w jednej linii. zwłaszcza jak Ci się to na monitorze nie mieści...
edytowany 3x, ostatnio: topik92
Zobacz pozostałe 4 komentarze
FJ
Nie, wytłumacz proszę, i powiedz jak inaczej mogę to napisać.
T9
Generalnie chodzi o to że jeśli a interesuje nas tylko wynik, to A* wykonuje mniej obliczeń, niż BFS, lub dijkstry. Wyobraź sobie taką sytuacje masz pustą mape i chcesz dość do wyjścia w odległości r = 1000. Najlepsza opcja dla A*, powinieneś wykonać tylko 1000 operacji bo idziesz prosto do celu. Ale szukając drogi inferencyjnie robisz coś takiego: wykonujesz r 1000 operacji by obliczyć odlełość do wyjścia i robisz jeden krok, potem 999 opreracji by odnaleźć wyjście i robisz kolejny krok itd. tysiąć razy i zamiast 1000, wykonujesz 500 tysiecy operacji.
T9
czyli mijasz się kompletnie z celem. Tak samo jak co iteracje robisz allNodes.Find(...) by sprawdzić czy nie wyszedłeś za tablice... to tak na prawde sprawdzasz wszystkie elementy tej tablicy czyli jak towoje r = 1000 , to kosztuje cie conajmniej 1 000 0000 operacji, a że robisz to 1000 razy to wychodzi 1 000 000 000, czyli z tysiąca zrobił się miliard, czyli jesteś milion razy wolniejszy. Jak sortujesz liste i robisz removeAt(0). Każde sortowanie to~10 000, removeAt(ostani) kosztuje 1, ale removeAt(0) kosztuje ~1000
T9
w tej książce w rozdziałach 16,17,18,19 masz ładnie opisane te zagadnienia, przeczytaj je i koniecznie zrób wszytskie zadania http://www.introprogramming.info/wp-content/uploads/2013/07/Books/CSharpEn/Fundamentals-of-Computer-Programming-with-CSharp-Nakov-eBook-v2013.pdf Ps tu masz implementacje A* z mapą i klasą node jak u Ciebie w kodzie. koledzy mnie pewnie zjedzą bo można to zrobic lepiej ale raz sie zyje :P http://pastebin.com/WpcbXNSF szyba nawet dziala ;P
FJ
Wielkie dzięki!
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.

Utwórz konto