Krowa, las i eksploracja terenu

17.11.2009 - Marcin Bieńkowski
TrudnośćTrudnośćTrudność

Kilkanaście lat temu zgubiłem się w lesie. Nie na tyle, żeby sytuacja była beznadziejna: wiedziałem, że zostawiłem auto przy drodze, wszedłem do lasu, gdzie spędziłem jakiś czas chodząc, a następnie wróciłem do tej samej drogi. Dodatkowo podczas spaceru po lesie przeciąłem swoją drogę dostatecznie dużo razy, żeby nie mieć zielonego pojęcia, czy samochodu należy szukać idąc w lewą stronę czy w prawą. Ot mniej więcej tak jak na poniższym rysunku.

No dobrze, to jest zły rysunek. Tak naprawdę sytuacja wyglądała znacznie gorzej, a mianowicie tak:

To znaczy drzewa na tyle skutecznie zasłaniały drogę, że widoczność była praktycznie zerowa. Nie miałem szans zobaczyć samochodu z odległości, musiałem się na niego natknąć

Parę lat później (pomińmy chwilowo milczeniem to, ile się nałaziłem w drodze do samochodu) dowiedziałem się, że ktoś już wcześniej miał taki sam problem i zostało to dokładnie opisane w literaturze. A mianowicie ten sam problem miała pewna krowa.

Krowa jaka jest, każdy widzi

Krowa stoi przy prostym płocie, przy którym jest wejście na pastwisko. Wejście (które jest oddalone od krowy o co najmniej jeden metr) krowa zobaczy dopiero jak do niego dotrze. Co powinna zrobić krowa, żeby jak najszybciej móc rozpocząć zjadanie trawy? Problem ten jest jednym z najprostszych wariantów eksploracji terenu. Jak się okaże poniżej, prostym lecz nie trywialnym.

Postarajmy się wyrobić sobie podstawowe intuicje. W całym artykule przez X będziemy oznaczać początkową odległość w metrach od krowy do wejścia na pastwisko. Oczywiście absolutnie genialna krowa znająca mapę terenu potrafi dojść na pastwisko przechodząc X metrów. Co się dzieje, jeśli krowa jest trochę głupsza, czyli nie zna mapy, nie zna X, ale wie, że wejście na pastwisko jest z prawej strony? Oczywiście idąc uparcie w tym kierunku przejdzie też dokładnie X metrów.

A co ma zrobić krowa jeśli w jakiś sposób poznała wartość X (przykładowo, wie że od wymarzonego celu dzieli ją 10 metrów), ale nie wie, czy wejście jest z lewej czy z prawej? Może wtedy zastosować następujący algorytm z parametrem y = X.

Algorytm Go-And-Eat(y)
1. Idź y metrów w lewo.
2. Jeśli nie znajdziesz wejścia, zawróć do punktu startowego.
3. Idź y metrów w prawo.

Łatwo obliczyć, że w najgorszym przypadku (a tylko takie przypadki interesują biedne, pechowe krowy) krowa przejdzie 3X (czyli w naszym przykładzie trzydzieści) metrów. Uważny czytelnik zauważy, że to czy krowa idzie na początku w lewo czy w prawo nie ma w pewnym sensie ma znaczenia: jeśli krowa ma pecha, to wejście będzie i tak z drugiej strony niż ta którą wybierze.

Krowa głodna, to krowa zła

Prawdziwy problem krowy (który jest identyczny z moim poszukiwaniem samochodu) zaczyna się jednak wtedy, kiedy krowa nie zna ani wartości X, ani nie wie, z której strony jest wejście. Zamiast wyciągnąć gotowe rozwiązanie z kapelusza, zastanówmy się, co mogłoby pomóc krowie w tym zadaniu.

A gdyby krowa znała jakieś oszacowanie na X, na przykład jakieś znała pewną liczbę $ D \geq X $? Mogłaby uruchomić procedurę Go-And-Eat(D), tj. iść D metrów w lewo, wrócić do punktu wyjścia, a następnie iść w prawo. Przebyta droga w najgorszym przypadku wynosiłaby 2D + X. Czyli jeśli D byłoby ,,tylko trochę'' większe od X, to otrzymalibyśmy rozwiązanie niedużo gorsze niż w przypadku kiedy znamy X. No dobrze, ale jak znaleźć takie D? Pomoże nam w tym często stosowana w algorytmice metoda podwajania: uruchamiamy algorytm Go-And-Eat kolejno z wartościami 1,2,4,8,16,... Cieszą nas dwie własności:

  • Jeśli w końcu uruchomimy Go-And-Eat z potęgą liczby 2 większą od X, to krowa znajdzie pastwisko.
  • Sumaryczna droga przebyta podczas uruchamiania Go-And-Eat z za małymi wartościami parametru jest niezbyt długa. (Ten warunek dopiero pokażemy.)

Ale moment! — powinien krzyknąć uważny czytelnik. Przecież po uruchomieniu algorytmu Go-And-Eat(1), krowa znajdzie się o 1 metr od punktu wyjścia, a algorytm Go-and-Eat(2) ma szansę zadziałać pod warunkiem, że krowa znajduje się początkowo w punkcie startowym. Możemy ,,załatać'' algorytm dodając do niego dodatkowy krok:

4. Zawróć do punktu startowego.

5
Twoja ocena: Brak Ocena: 5 (14 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com