🚀 go-pugleaf

On 8 Jan 1998 15:51:38 GMT, in pl.comp.lang.c Robert Maron
<robmar@domek.slodki.domek> wrote:

>Krzysztof: [pl.comp.lang.c: Wed, 07 Jan 1998 22:23:56 +0100]
>:>Nieprawda! Algorytm nierekurencyjny jest bardzo prosty! Oczywiście
>:>musi być to algorytm z powrotami, ale nie mysi być rekurencyjny.
>: Nie musi, niezbyt oszczędny pamięciowo i czasowo algorytm rozwiązywania
>: labiryntu, określany mianem "wypalania stepu" polega na stworzeniu tablicy
>
>no wlasnie, ten algorytm jest bardzo kosztowny...
>
>czas ma tragiczny (kwadrat zamiast liniowego - do powierzchni labiryntu);
>jesli labirynt jest np. 100x100 to zamiast 10tys krokow (pare sekund) masz
>100mln krokow (pare dni...)
 :-))). Można go bardzo drastycznie zoptymalizować tworząc dwie listy,
pierwsza w której będą właśnie sprawdzane pozycje na labiryncie, i druga do
której są zapisywane pozycje do sprawdzenia w następnym kroku. Rozmiar
żadnej z list nie przekroczy max ilości ścieżek. Algorytm zaczniemy
wpisaniem położenia wejścia do pierwszej listy i dalej lecimy tak jak
poprzednio opisałem, sądze że byłoby to szybsze od algorytmu z powrotami.
Choć nadal jest to kwestia tablicy, ale dla niedużych labiryntów
(powierzchnia poniżej 65530 :-) ) to i tak jest tylko troszkę więcej niż
potrzeba na przechowanie opisu labiryntu.

Przy tej wersji labiryntu warto przyjąc wejscie jako 0x0001.


Hobbit
>
>niech on zrobi ten wariant z kolejka... max rozmiar kolejki to obwod
>planszy;
A może lepiej nie :-)

Hobbit

--
-------------------------------------|
Krzysztof Swiatkowski - Lodz, Poland | replying cut bezspam from my address
e-Mail:  hobbit@dom.vr.pl.bezspam    | odpowiadajac usun bezspam z adresu

"Rzeczywistosc jest dla tych biedakow, ktorzy nie radza sobie z fikcja"