Лекция 10. Видове случайни разходки. Просто обхождане. Необратимо



Дата31.03.2018
Размер74.29 Kb.




Лекция 10. Видове случайни разходки. Просто обхождане. Необратимо

обхождане. Обхождане без застъпване.

В предишните лекции видяхме че при стохастическите извадки за оценка на интеграли използваме или прости извадки с равномерно разпределение на вероятността или извадки по важност, с теглова функция различна от единица. Като пример за прости извадки ще разгледаме различните видове случайни разходки върху 2-мерна квадратна решетка. Случайните разходки намират приложение при симулиране на брауново движение, транспорт на електрони през метал или за моделиране свойствата на макромолекули и полимери. Нека имаме един атом на парфюм, който се удря с други атоми във въздуха. Въпросът е колко удара средно трябва да претърпи белязания атом за да се отдалечи на разстояние R от мястото на тръгване.

Ще разгледаме трите вида случайни разходки върху квадратна решетка. Във всяка точка са възможни четири вида вектори, които отвеждат в една от съседните точки: v(1)=(1,0); v(2)=(0,1); v(3)=(-1,0); v(4)=(0,-1).

1) Просто обхождане

Фиг.1 ПРОСТО ОБХОЖДАНЕ: Преходът във всяка съседна точка е разрешен с еднаква вероятност равна на ¼ . В маршрута се срещат както повторения (отсечки преминати повече от веднъж) така и пресечни точки.

Възниква въпроса колко различни маршрута Nn са възможни при n стъпки? В случая на просто обхождане те лесно се пресмятат: Nn = 4n . Друг интересен въпрос е дали пешеходеца някога ще се върне в изходна позиция. Показано е че отговорът зависи от размерноста на решетката. За едно или двумерна решетка е сигурно че ако случайната разходка продължи достатъчно дълго пешеходецът ще се върне в изходна позиция. При по-високи размерности на решетката възможноста да се загубиш е по-голяма и няма гаранция за връщане в началото. Една важна мярка за случайната разходка е квадрата на разстоянието от началната до крайната точка на разходката.


Фиг.2 Отдалечаване от началото

За просто обхождане от n стъпки с дължина единица средноквадратичното отдалечаване от началото е: <R2n>= n

Ще симулираме простото случайно обхождане с помощта на генератор на случайни числа. Ще изчисляваме средното разстояние между началната и крайната точка като функция на броя стъпки. За алгоритъма са необходими два входни параметъра. Първият параметър е броя стъпки n в една разходка. Вторият параметър е броя на разходките, който ще означаваме с К.



Зад. 1 Ако ri =sqrt(x2 + y2) е разстоянието от началнатa до крайната точка при i-та разходка , изчислете средното разстояние , средното от квадрата 2> и флуктуациите на тази величина 2> - 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). В дадена верига с фиксиран размер се освобождава връзката на единия от двата края (случайно избран) и се добавя нова връзка на другия край.

Моделирането на случайно обхождане без застъпване изисква

по-сложен алгоритъм отколкото за просто или необратимо блуждаене. При обхождането без застъпване има две ограничения:


  1. Не е разрешено да пресичаш пътя по който си минал

  2. Не е разрешено да се връщаш към предишната позиция

Очевидно при такива ограничения може да възникне ситуация когато

няма повече разрешени позиции за да продължи пътя т.е. дължината може да е по-малка от заложения брой стъпки 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) като използвате зависимоста SS0 = ln[W(n)], където S0 =0 е резултата за просто обхождане. Изчислете също пътищата на разходките от начална до крайна стъпка отделно по координатите x и по у. Изчислете флуктуациите на тези пътища.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница