Błądzenie losowe

11.07.2009 - Marek Szykuła
Trudność

Błądzenie losowe w grafach

W poprzedniej części przyjrzeliśmy się błądzeniu losowemu w parku. W informatyce zwykle rozważa się błądzenie w bardziej ogólnych przestrzeniach, np. w grafach.

Zobaczmy kilka przykładów prostych grafów, w których piłeczka wykonuje spacer losowy po wierzchołkach. Takie typowe grafy mają swoje własne nazwy. W każdym wierzchołku zaznaczone jest jak często piłeczka w nim bywa - im jaśniejszy kolor tym częściej.

W animacjach możesz przyspieszać i zwalniać czas używając rolki myszy. Klikając na graf możesz zacząć spacer od początku.

Linia:

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

Klika:

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

Krata:

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

Drzewo binarne:

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

W każdym typie grafu rozkład częstości wygląda trochę inaczej. Pomiar tego rozkładu stabilizuje się po pewnym czasie. Każdy graf ma taki swój własny rozkład częstości. Jeśli łańcuch Markowa w danym grafie nie jest okresowy to rozkład częstości mówi też o rozkładzie stacjonarnym.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com