2 като функция на n, където:
(1)
Общият вид на алгоритъма написан в псевдокод е следния:
do sample:=1 to К
begin
х:=0; y:=0;
do step:=1 to n
begin
ir: = random(1, 2, 3, 4) //генерирайте едно случайно число 0, 1, 2 или 3
case ir
0: x:=x+1.0;
1: y:=y + 1.0;
2: x:=x – 1.0;
3: y:=y – 1.0;
end
end
accumulate results //изчислете нужните величини съгласно
//указаните формули
end
-
Ако вашия пешеходец прави n стъпки в една разходка, реализирайте К≈√n разходки, всяка от n стъпки и с различен зародиш (seed).
-
Проверете графично дали се изпълнява зависимоста R √n за една разходка, както и за средната стойност от К разходки <R> √n.
-
Направете графика на <R> като функция на √n. Забележете колко стъпки са необходими докато почне да се изпълнява Гаусова статистика т.е. докато се изпълни зависимоста <R>≈√n
-
Направете scatterplot на координатите на крайната точка в разходките, като винаги се тръгва от (0,0). Ако вашата разходка е случайна не трябва да има предпочитано направление.
2) Необратимо обхождане
Фиг.3 НЕОБРАТИМО ОБХОЖДАНЕ: Липсват повтарящи се отсечки в маршрута но се
срещат пресечни точки. Забранени са
преходите обратно в точката откъдето си
дошъл.
При необратимото обхождане броят на възможните маршрути от n стъпки е: Nn = 4x3n, което клони към Nn = 3n. Съответно отдалечаването от началото (средноквадратичното отместване) е по-голямо в сравнение с простото обхождане: <R2n>= 2n.
. Алгоритъмът за числово моделиране на необратимото случайно обхождане не се отличава съществено от разгледания алгоритъм за просто обхождане като трябва да се включи код за наложеното ограничение, а именно стъпка назад е забранена.
Една възможност е да запазим равна вероятност за 4-те посоки и да игнорираме пробната стъпката ако тя е назад и да направим нов опит докато стъпката е разрешена. Например нека имаме 4 възможни стъпки 0, 1, 2, 3 .
1 Ако се падне посока 0, т. е.
2 0 връщане към последната посетена
3 позиция, се прави нов опит докато се
падне посока 1, 2, или 3.
Друга възможност е да помним откъде сме дошли и да избираме с вероятност 1/3 само между разрешените посоки. При този подход трябва да се идентифицират съседите и да се направи списък на разрешените 3 стъпки и тогава да се тегли жребии между тях.
Ние ще изберем първия, по-глупав но по-прост подход да се опитваме евентуално няколко пъти да влезем през затворена врата. Този подход изисква съсвсем малка модификация на предишния код. Ще въведем нови променливи хpre и ypre, които да обозначават предишната позиция така че да можем да проверим дали пробната стъпка съвпада с предишната позиция. Ако това се случи опитваме отново докато пробната стъпка е различна от предишната позиция. Модифицираният код е показа по-долу:
do sample:=1 to n_of_samples
begin
х:=0; y:=0;
хpre =0; ypre =0;
do step:=1 to n
begin
repeat
хtemp := x; ytemp := y;
generate_one_step(x,y);
until((xpre x) or (ypre : y));
хpre := xtemp;
уpre := ytemp;
end
Зад. 2 Като използвате горния алгоритъм напишете програма за моделиране на необратимо обхождане. Изчислете същите величини като в предишната програма като променяте броя на стъпките и броя на разходките.
3. Обхождане без застъпване
Фиг.4 ОБХОЖДАНЕ БЕЗ ЗАСТЪПВАНЕ: В маршрута не се срещат нито повтарящи се отсечки нито пресечни точки. Използва се за моделиране на полимери.
За разлика от простото случайно обхождане което може да продължи до безкрайност обхождането без застъпване често може да се прекрати поради липса на свободни, непосетени съседи. В такъв случай няма повече възможности за напредване, което се определя от условието за незастъпване. При безкрайна решетка вероятноста за блокиране е под 1% , но при дълго продължаващо блуждаене е сигурно че може да се стигне до глуха улица. Поради тази причина обхождането без застъпване е по-различно от другите две, то трябва да се бори за оцеляване. Поради тази причина също е по трудно да се определи точно броя на маршрутите за които се знае само че са в интервала: 2n < Nn < 3n. Средноквадратичното отместване също не е определено теоретично въпреки че експерименталните изследвания показват наличието на зависимост от вида: <R2n>= n3/2.
Съществува и четвърти вид случайна разходка наречено плъзгаща се змия (slithering snake). В дадена верига с фиксиран размер се освобождава връзката на единия от двата края (случайно избран) и се добавя нова връзка на другия край.
Моделирането на случайно обхождане без застъпване изисква
по-сложен алгоритъм отколкото за просто или необратимо блуждаене. При обхождането без застъпване има две ограничения:
-
Не е разрешено да пресичаш пътя по който си минал
-
Не е разрешено да се връщаш към предишната позиция
Очевидно при такива ограничения може да възникне ситуация когато
няма повече разрешени позиции за да продължи пътя т.е. дължината може да е по-малка от заложения брой стъпки N. Цикълът може да свърши в два случаяя: ако броя стъпки стане равен на N или ако няма повече разрешени стъпки. Ще отразим тази ситуация в един общ алгоритъм, който по-късно ще конкретизираме:
do sample:=1 to n_of_samples
begin
step:=0;
repeat
generate_one_step;
step:=step + 1;
until (step_invalid or step = n)
accumulate results
end
Възниква въпроса как да проверим дали една стъпка е валидна? Нека на всеки пешеходец припишем един уникален етикет, примерно първия пешеходец ще идентифицираме с 1, втория с 2 и т.н.Тази номерация може да се извършва автоматично от някакъв цикъл. При обхождането всеки пешеходец маркира посетените позиции със собствения си етикет.
Сега е просто всеки пешеходец да установи дали следващата стъпка е в позиция посещавана от него (забранена позиция) или не е посещавана от него (разрешена позиция).
Тук отново сме на кръстопът. Трябва да решим как да генерираме произволна стъпка т.е. дали сляпо да пробваме във всички посоки или да идентифицираме разрешените посоки и изборът да се разделя само между тях. Техниката с етикетите не позволява да отличим дали посетената позиция е предишната или е по-рано посетена. Етикетите обаче позволяват да се определи дали пробната стъпка е валидна или не. Можем да увеличим временно етикета на предишната позиция с едно. Така ако позицията на пробната стъпка има етикета на същия пешеходец това значи че имаме пресичане и разходката е свършила. Ако етикета е с едно по-голям значи имаме връщане назад и се прави нов опит.
Техниката с етикетите е удобно да се реализира с въвеждането на масив (array). За пълна разходка от n стъпки върху двумерна решетка трябва да въведем масив за решетката с размерност (n, n): integer lattice(-n: n, -n: n)
Общия вид на алгоритъма за непресичащо се случайно обхождане изглежда така:
integer lattice(-n: n, -n: n) //масив съдържащ информация за етикетите на
//всяка позиция от решетката
do sample:=1 to n_of_samples
begin
step:=0;
x:=0; y:= 0;//координати на позиция от решетката
xc:=0; yc:= 0;//актуални координати
repeat
generate_one_step(xnew , ynew);
until lattice(xnew , ynew) sample + 1;
if lattice(xnew , ynew) = sample then
terminate:= true
else
begin
lattice(x,y):=sample;
x = xc; y = yc;
lattice(x,y):=sample +1;
xc := xnew; yc := ynew;
step :=step+1;
end
until (terminate or step = n);
accumulate results
end
Зад.3 Използвайте горния алгоритъм и напишете програма за случайно обхождане без застъпване като извеждате дължината (в брой стъпки ) на всяка разходка. Направете графика на броя на разходките като функция на дължината им n. Изчислете също ентропията S чрез вероятноста (честотата) на успешни опити W(n) като използвате зависимоста S – S0 = ln[W(n)], където S0 =0 е резултата за просто обхождане. Изчислете също пътищата на разходките от начална до крайна стъпка отделно по координатите x и по у. Изчислете флуктуациите на тези пътища.