Najkrótsza droga wyjścia z labiryntu.

takeshi2318 · Dołączył: 28 Gru 2011 Posty: 6

Witam mam takie zadanie o następującej treści: treść posta przeniesiona do posta przez moderatora,
i chciałby się zapytać z czego najlepiej w nim skorzystać gdyż napisałem już 2 programy z własnym algorytmem ale żaden z nich nie chciał działać, z góry dzięki za pomoc.

Treść posta przeniesiona do posta przez moderatora. Po co rozbijasz treść posta na kilka serwisów!? marcin_an

hurgadion · Dołączył: 06 Kwi 2011 Posty: 143 Skąd: Kraków

Witam,
niedawno był poruszany tutaj na forum problem perkolacji, w którym podjąłem próbę rozwiązania podobnego problemiku do Twojego (niestety nie w C++): http://www.coderscity.pl/ftopic41385.html?sid=02e1ee237572aaf65793cb36bb1a50dd Wydaje mi się, że metoda losowego błądzenia po kracie powinna rozwiązywać Twój problemik (po dołożeniu odpowiedniego warunku, zmodyfikowaniu kodu i przełożeniu go na C++), jednak może to być metoda czasochłonna... Możliwe, że istnieją bardziej optymalne metody wyszukiwania drogi w labiryncie... Chętnie bym się dowiedział, jak ten problemik można inaczej ugryźć... Pozdrawiam.

takeshi2318 · Dołączył: 28 Gru 2011 Posty: 6

Myślałem osobiści o algorytmach wyszukiwania ścieżki typu A-star albo Dijkstra, ale niestety są one trudne w implementacji...

hurgadion · Dołączył: 06 Kwi 2011 Posty: 143 Skąd: Kraków

Zastanów się czy wspomniane przez Ciebie algorytmy nadają się do Twojego problemu, wydaje mi się, że są to typowe algorytmy przeznaczone do wyszukiwania minimalnych ścieżek na grafie, a Twój problemik jest chyba zupełnie innego typu, pzdr.

izaw · Dołączył: 12 Wrz 2008 Posty: 2003 Skąd: Łódź

Klasyczne przeszukiwanie wszerz. Na każdym poziomie masz wszystkie pola o danej odległości.

Hashedone · Dołączył: 23 Sie 2008 Posty: 853

hurgadion · Dołączył: 06 Kwi 2011 Posty: 143 Skąd: Kraków

Chyba rozumiem... W takim razie problem perkolacji także sprowadza się do klasycznego problemu :)

takeshi2318 · Dołączył: 28 Gru 2011 Posty: 6

A czy mógłby ktoś, napisać mi (możebyć w pseudo kodzie) jak mniej wiecej ma wyglądać ta cheurystyka? Bo w teorii działanie tych algorytmów rozumiem ale jak otworzyłem kod A* to zgłupiałem...

izaw · Dołączył: 12 Wrz 2008 Posty: 2003 Skąd: Łódź

Zacznij od napisania klasycznego przeszukiwania wszerz. W twoim problemie pewnie to wystarczy.

Jeżeli będziesz potrzebował optymalizacji to dodasz A*. Zacznij od wikipedii.

marcin_an · Wysłany: Sro Gru 28, 2011 5:24 pm Temat postu:

Ciekawi mnie, czy można - skoro zakazano używać znaku [ - skorzystać z ciągu znaków <:

;P

Dla osób, które widziały wcześniejszą, już usuniętą wersję posta: oczywiście mój błąd - nie będzie prostszy w implementacji. Dlatego też usunąłem tę część wypowiedzi.