Błądzenie losowe

11.07.2009 - Marek Szykuła
Trudność

Błądzenie jest w naszym świecie częstym zjawiskiem. Przykłady błądzenia mamy na co dzień: zgubiliśmy się, szukamy rzeczy, informacji w Internecie lub po prostu idziemy na spacer.

W takich sytuacjach można zadać pytania:

  • Gdzie dojdziemy idąc na oślep?
  • Jak szybko coś znajdziemy lub gdzieś dojdziemy?
  • W jakich miejscach najczęściej będziemy chodzić?
  • Czy uda się obejść wszystkie miejsca?

W tym artykule opowiemy jak w miarę możliwości odpowiadać na takie pytania, przenosząc się z błądzeniem w świat informatyki.

Spacery losowe

Wyobraźmy sobie park. Zwykle ludzie idą do parku się przejść i nie myślą o tym gdzie dokładnie dojdą. Jak zatem obierają swoją trasę?

Załóżmy, że spacerowicz nie zna parku, nie ma żadnej mapy, a wszystkie ścieżki wyglądają bardzo podobnie. Dlatego też, po dojściu do skrzyżowania wybiera jedną z dróg losowo. Aby nie chodzić tymi samymi drogami, nie wybiera tej drogi którą właśnie przyszedł - chyba, że to ślepa uliczka i nie ma innego wyboru.

Oto przykład takiego właśnie parku do którego ludzik (nasz spacerowicz), wybrał się na spacer:

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

W animacjach możesz przyspieszać i zwalniać czas używając rolki myszy.

Taki spacer, w którym decyzje o kierunku podejmowane są losowo, nazywamy spacerem losowym. Nasz spacer ma bardzo ważną własność: ludzik podejmując decyzje nie sugeruje się tym gdzie chodził wcześniej. Jeśli dojdzie powtórnie do tego samego miejsca, idąc w tym samym kierunku co poprzednio, to możemy uznać, że jego sytuacja staje się identyczna. Tę własność, kiedy decyzje wyboru drogi nie zależą od przeszłości nazywamy warunkiem Markowa, a sam spacer jest łańcuchem Markowa.

4.875
Twoja ocena: Brak Ocena: 4.9 (8 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com