Krowa, las i eksploracja terenu
17.11.2009 - Marcin Bieńkowski
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 widziKrowa 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) Ł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łaPrawdziwy 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ę ? 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:
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. (14 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com