: Home / inne tematy / algorytmy / Rundom Walk
Rundom Walk
Ocena użytkowników: / 0
SłabyŚwietny 
Wpisany przez Patryk yarpo Jar   
poniedziałek, 15 lutego 2010 18:58

Błądzenie losowe [ang. random walk] to proces polegający na  podejmowaniu kolejnych kroków, każdy w losowo wybranym kierunku.

W tym wypadku mieliśmy sprawdzić, czy prawdziwe jest twierdzenie, że liczbka kroków agenta błądzącego losowo po nieskierowanym grafie spójnym po podstawieniu do odpowiedniego wzoru jest równa rezystancji zastępczej układu elektrycznego zbudowanego na podstawie grafu (z założeniem, że na każdej krawędzi kładziemy opornik o oporze 1Ω). Wyniki są zaskakujące.

 

Prezentacja pokazuje wyniki testów jakie wykonalismy razem z Piotrkiem Grotą jako projekt na studia.

 

Pliki do pobrania

Pobierz pliki (projekt Visual Studio, skrypt php).

Do wyliczania średnich używałem jesdzcze jednego prostego skryptu PHP. Do wykresów wykorzystałem Open Office Calc.

 

Krótki manual do programów

Program odpala się z wiersza poleceń. Na wejście podaje się:

liczba krawedzi
liczba wierzcholkow
wierzcholek startowy
wiercholek celu
liczba testow (pozniej w programie zrobilem jeszcze te liczbe x 100)
v x - numery wierzchoków [numerowane od 0]
v u
...

Czyli np.:

28
20
1
19
100
0 1
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
0 2
2 4
4 6
6 8
8 10
10 12
12 14
14 16
16 18

Uwaga: Bardzo ważny jest format. Między numerami wierzchołków musi być spacja. Kolejne krawędzie musi oddzielać enter, itp. Wejście musi być sformatowane jak powyższe. Nie chciało mi się bawić w scanfy w c# :) Wczytywanie danych jest bardzo uproszczone.

 

 

Dodaj komentarz


Kod antysapmowy
Odśwież