5996833061

Metoda taka mogłaby polegać na wygenerowaniu wszystkich dróg prowadzących do wyjścia i wybraniu najkrótszej. Dróg wyjścia może być jednak bardzo dużo, choć ich liczba jest skończona, a zatem najkrótsza droga zawsze istnieje.

Aby skonstruować algorytm według, którego z danego pola podążamy bezpośrednio do wyjścia, oprzemy się prostej obserwacji -każdy fragment najkrótszej drogi między dowolnymi jej punktami jest również najkrótszą drogą między tymi punktami.

Metoda znajdowania najkrótszej drogi z pola s :

-    generujemy pola odległe od i o jedno pole (pola przyległe)

-    generujemy pola odległe od i o dwa pola (które oddzielone są od s polem przyległym)

-    generujemy pola odległe od i o trzy pola etc., aż do osiągnięcia wyjścia

{metodę tą nazywamy bliższe najpierw, wynikiem jej działania jest labirynt wypełniony liczbami |

-    odczytujemy od strony wyjścia pola od ległe od s o L pól, później pole odległe o L-l, następnie L-2 etc. , postępujemy tak, aż do osiągnięcia pola 5

Aby zapisać algorytm musimy podać sposób zapamię-tywania kolejno odwiedzanych i przeglądanych pól.

Zakładamy, że na początku algorytmu wszystkie pola sąnie-odwiedzone.

Aby mieć pewność, że pola przechodzimy w kolejności ich odległości od umieszczamy je w kolejności osiągania, jedno po drugim w ciągu.

W tej samej kolejności opuszczają one ten ciąg. gdy przechodzimy na nowe pola, leżące o jedno pole dalej od i.