Krowa, las i eksploracja terenu

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

Czy naprawdę trzeba tyle chodzić?

Krótka odpowiedź brzmi: tak, każdy algorytm dla krowy wymaga przejścia w najgorszym przypadku odległości dziewięciokrotnie przekraczającej początkową odległość krowy od pastwiska. Niestety pokazanie tego jest dość trudne i wykracza poza ramy tego artykułu. Spróbujmy jednak uspokoić swoje sumienie i pokazać, że krowa zawsze musi przejść co najmniej $ 5 X $.

W tym celu zauważmy, że jeśli krowa nie robi głupich wycieczek (takich jak na dwóch poprzednich rysunkach), to jej trasa to oddalanie się od punktu startowego na przemian w lewo i w prawo. Wyznacza to podział trasy krowy na kolejne fazy. Bez straty ogólności załóżmy, że na początku krowa idzie w lewo. Wtedy jej trasę można opisać liczbami $ f_1, f_2, f_3, f_4, ... $, gdzie $ f_j $ jest oddaleniem w fazie j. (W opisanym wcześniej algorytmie Smart-Cow $ f_j =
2^{j-1} $.)

Zauważmy teraz, że krowa stosuje taką samą trasę niezależnie od tego jaki jest X. Powyższe zdanie wydaje się oczywiste (jak trasa mogłaby od tego zależeć, skoro X poznajemy dopiero w momencie odnalezienia pastwiska, a wtedy już nigdzie nie lazimy), ale je warto przeczytać więcej niż jeden raz. Oznacza to, że dla danego wyboru trasy krowy (tj. liczb $ f_1, f_2,
f_3, f_4, ... $) wystarcza postawić bramkę na pastwisko w jakimś bardzo złośliwym miejscu.

Popatrzmy bliżej na ciąg $ f_1, f_2, f_3, f_4, ... $. Musi w nim istnieć jakaś kolejna para $ f_i $ i $ f_{i+1} $ taka że $ f_i \leq f_{i+1} $. Na powyższym rysunku jest to na przykład para $ f_4 $ i $ f_5 $. W przeciwnym wypadku ciąg $ f_i $ byłby ściśle malejący (a jest to dość kiepski pomysł, jeśli krowa zamierza znaleźć odległe pastwisko). Załóżmy, że krowa odległość $ f_i $ przechodzi w prawą stronę. Postawmy zatem bramkę kawałeczek dalej niż w odległości $ f_i $ po prawej stronie od punktu startowego, tj. $ X =
f_i + \epsilon $.

Wtedy krowa przechodzi co najmniej $ 2 \cdot f_i $ w lewo, następnie $ 2 \cdot
f_{i+1} $ w prawo, a następnie (pod warunkiem, że nie jest bezdennie głupia i $ f_{i+2} > f_i+\epsilon $) krowa dochodzi do pastwiska przechodząc X. Całkowita droga przebyta przez krowę to


\begin{equation*}
2 \cdot f_i + 2 \cdot
f_{i+1} + X \geq 4 \cdot f_i + X = 5 X - 4 \epsilon \enspace.
\end{equation*}

Ponieważ $ \epsilon $ możemy wybrać dowolnie małe i zaniedbywalne, krowa przechodzi praktycznie pięciokrotnie więcej niż wynosi $ X $.

Po co krowie pieniądze?

Jak można ułatwić życie naszej krowie? Na początku poprzedniego rozdziału powiedzieliśmy, że nie da się poprawić wyniku osiąganego przez algorytm Smart-Cow. Cóż, jest to tylko częściowa prawda. Nie można go poprawić, jeśli krowa chodzi deterministycznie. Możemy natomiast podarować jej monetę, którą może wspomóc się w w trudnych chwilach (i nie chodzi nam o to, żeby kupiła sobie za to mapę czy coś do jedzenia).

Wróćmy do algorytmu Smart-Cow. Załóżmy, że w momencie, który nazwaliśmy krytycznym, krowa rzuca monetą. Jeśli wypadnie orzeł idzie następne $ 2^{j+1} $ metrów w prawo, w przeciwnym przypadku w lewo. Dla ustalonej pozycji bramki na pastwisko krowa ma 1/2 szansy na to, że pójdzie w jej stronę. W takim przypadku części spaceru krowy (niebieski fragment na rysunku) o długości $ 2 \cdot 2^{j+1} $ w ogóle nie ma! Wtedy krowa przechodzi nie $ 9X $ a $ 5X $. W średnim przypadku przechodzi zatem $ 7 X $.

To obniża średnią liczbę metrów przebytą przez krowę, pod warunkiem że ... krowa wymyśli, że dany moment jest krytyczny! Okazuje się jednak, że wcale nie musi tego robić. Wystarczy, żeby monetą rzuciła wybierając kierunek na samym początku. Wtedy analiza jest dokładnie taka sama, a dodatkowo w momencie kiedy krowa znajdzie się już w punkcie krytycznym z prawdopodobieństwem 1/2 będzie szła w lewo a z prawdopodobieństwem 1/2 będzie szła w prawo.

Quo vadis, droga krowo

Powyższe rozważania to tylko czubek góry lodowej tematyki eksploracji terenu. Oprócz ,,prawdziwych'' zastosowań, istnieje jeszcze parę lepiej lub gorzej zbadanych podstawowych problemów. Przykładowo dociekliwy czytelnik może zastanowić się jaką strategię należy obrać, jeśli jesteśmy kapitanem, który odpłynął od brzegu i stracił orientację. Zakładamy, że linia brzegowa jest linią prostą i chcemy dopłynąć do jej dowolnego miejsca. Można wyobrazić sobie następujące warianty tego problemu:

  1. Wiadomo, że linia brzegowa jest oddalona o 1 km, ale nie wiadomo w którym kierunku.
  2. Mamy kompas i wiemy, że linia brzegowa przebiega albo z północy na południe albo z zachodu na wschód, nie znamy natomiast odległości od linii brzegowej. (Warto zauważyć, że jeśli wiedzielibyśmy, że linia brzegowa przebiega z północy na południe to jest to taki sam problem, jaki miała nasza krowa).
  3. Nic nie wiemy.

Temperować ołówki, siodłać krowy i do dzieła!

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com