Problem z algorytmem w labiryncie

Otóż mam labirynt. Załóżmy że ten labirynt to 2-wymiarowa tablica Integerów. 0 - Puste pole; 1, 2 - Zajęte; 3 - Punkt A; 4 - Punkt B; (Przy okazji Punkty A i B nie leżą na ścianach labiryntu tylko gdzieś wewnątrz).

Noi przez cały dzień próbowałem wymyślić algorytm szukający najkrótszej drogi między punktami A i B, omijając Zajęte miejsca. Mógłby ktoś poradzić?

W tagu jest komiwojażer, bo czytałem artykuł w którym punktem A był komiwojażer, który chciał dojść do Wyjścia, którym jest punkt B. Niestety to było tylko dla labiryntów 10x10 które mają dokładnie jedno wyjście i jedno wejście.
A mi takie coś nie pasuje.

Ps; Wolałbym uniknąć chodzenia na skosy, tylko góra-dół, lewo-prawo.

Jest algorytm "zalewowy" - z punktów A i B wypuszczasz "macki", które rekurencyjnie się rozrastają i ich pierwsze spotkanie wyznacza najkrótszą drogę.

A to nie dałoby się zrobić po prostu BFS-a z punktem startu w A? W punkcie A zapisujesz, że potrzeba 0 kroków, by dojść do tego punktu; potem szukasz wolnych pól - w tych wolnych polach zapisujesz wartość 1 krok, potem dla tych nowo zajętych szukasz znowu wolnych pól i zapisujesz, że potrzeba 2 kroków itd. Gdy trafisz na punkt B, to masz wynik.

W załączniku pokazuję swój pomysł na rozwiązanie tego problemu.
Wadą mojego programu jest dość duża złożoność pamięciowa (nie jestem pewien, czy jakiś wredny test nie ukradłby kilkunastu-kilkudziesięciu mega RAM-u).
Tymczasem rozwiązanie poprzednika charakteryzuje wręcz kosmiczna złożoność (np. dla rozmiaru tablicy 5x5, jak policzyłem programem, potrzeba ponad 150 000 wywołań rekurencyjnych, dla 6x6 prawie 32 000 000, dla 7x7 działa mi już od ponad 5 minut i wciąż nic). Ewentualnie jest też możliwość, że jakoś pomyliłem algorytm naiwny ze zmodyfikowanym DFS-em.

Być może istnieje jakiś prostszy sposób - jakby co, na razie go nie znam.

Edit: jak ktoś chce wiedzieć: dla 7x7 liczba wywołań rekurencyjnych wynosi 19 012 099 005.

Popatrz na to: http://www.rafalnowak.pl/wiki/images/e/e6/MajowkaRNO_graphs.pdf ; jedyna różnica jest taka, że oprócz odległości musisz przechowywać opis ścieżki. W C++ możesz użyć STL-ów, m.in. kolejki (queue):

#include <queue>
/* ... */
std::queue<int> odleglosci;
std::queue<std::string> sciezki;

I jeśli masz zgodnie z instrukcją coś wrzucić na kolejkę, to wrzucasz do odleglosci odległość, a do sciezki ścieżkę.

Nie ma sensu przechowywać ścieżek, gdyż może być ich duża liczba. Pierw znajdź sobie minimalną długość ścieżki, a potem ją (lub je) odtwórz.

Algorytmy znajdywania najkrótszej ścieżki są znane od lat i bardzo dobrze opisane.

Jeżeli chcesz wynik dokładny to korzystasz z algorytmó grafowych podobnych do algorytmu dijkstry.
Jeżeli masz duży labirynt i nie możesz sobie pozwolić na tak wiele obiczeń to korzystasz:

• algorytmu heurystycznego, np. algorytm A*
• algorytmu genetycznego

Kierunek chodzenia po labiryncie to już sobie sam ustawiasz. Możesz nawet zrobić chodzenie tylko w przód i lewo... :-)

Opolski Portal Programistyczny
http://programowanie.opole.pl

To mógłby ktoś podać to czarno na białym?

Mam dobry humor więc podam. Potrzebujesz tablicy (T1) o wielkości równej labiryntowi, wypełnionej dużymi liczbami (powiedzmy INT_MAX) oraz kolejki (Q) położeń w tablicy. T1 ogólnie ma przechowywać najkrótszą odległość od danego punktu do punktu początkowego. Na początku dodajesz do Q punkt początkowy i wpisujesz w T1 w to miejsce 0. Następnie bierzesz dopóki nie określiliśmy odległości punktu końcowego oraz Q nie jest pusta, kolejnę wartość z Q i dla wszystkich możliwych sąsiadów sprawdzamy czy wartość w T1 jest mniejsza od wartości z T1 dla pobranego punktu zwiększonej o jeden. Jeżeli tak to przypisujemy tę odległość do punktu i dodajemy go do kolejki. W celu poznania drogi wychodząc z punktu końcowego idziesz po T1 po najmniejszych wartościach.

Wypełniasz tablicę zerami, w polu początkowym jest 1. Jedynkę otaczasz dwójkami, dwójki trójkami, itd. (tzn. pola które jeszcze nie zostały oznaczone). Tylko bez żadnej rekurencji, bo zbędna.