ЗАДАЧА 11.13. Моделирование двумерного БСП методом Монте-Карло

а. Рассмотрите ББС на квадратной решетке. Удобно представить решетку в виде двумерного массива; этот массив используется для записи узлов, которые посещались. Выберите произвольный узел в качестве начального и предположите, что первый шаг делается на «север», поскольку блуждания, порождаемые тремя другими возможными начальными шагами, различаются только направлением. Заметим, что второй шаг можно сделать в трех возможных направлениях. Для получения несмещенных результатов мы генерируем случайное число (1, 2 или 3), которое н определяет выбор одного из трех направлений движения. Последующие шаги генерируются аналогичным образом.   К  сожалению,   обычно  при  таком   способе моделирования

блуждание не продолжается бесконечно. Рассмотрите N = 3-шаговое блуждание, показанное на рис. 11.7,а. Следующий шаг, показанный на рисунке, приводит к самопересечению и тем самым нарушает принятое ограничение. Для получения несмещенных результатов нам нужно, как обычно, сгенерировать случайное число (1. 2, 3). Если следующий шаг приводит к самопересечению, то блуждание прекращается и начинается новое блуждание нз начальной точки. Напишите программу, в которой реализуется этот алгоритм, н зарегистрируйте долю /(Л7) успешных попыток построения полимерных .цепочек, составленных нз всех Л7 звеньев (шагов). Какова качественная зависимость f(N) от Л7? Какое максимальное значение Л7 вы в состоянии еще рассмотреть? Вычислите R^ для нескольких значений N.

б. Недостатком приведенного выше метода моделирования является его неэффективность для длинных цепочек, т.е. доля успешных попыток уменьшается экспоненциально. Для преодоления этого недостатка было предложено несколько «улучшений» метода. Обсудим сначала относительно простую процедуру, предложенную М. Розенблатом и А. Розенблатом (1955), в которой каждому ^-шаговому блужданию соответствует весовая функция W^. Поскольку первый шаг на север всегда возможен, мы имеем W. = 1. Чтобы в равной степени учесть все допустимые при данном N конфигурации, веса WN для N > 1 определяются в соответствии со следующими возможностями:

Все трн допустимых шага нарушают условие самонепересечения (см., например, рнс. 11.7,6). Блуждание прекращается с весом WN = 0, и генерируется новое блуждание нз начальной точки.

Все трн шага допустимы, и WN = W'N_r

3. Допустимы только т шагов с 1 £ т < 3 (рис. 11.7, в). Тогда WN = (m/3)Wдг_1 и случайное число используется для выбора одного из т допустимых шагов.

2 2

Правильное значение <RN> получается умножением RN ., т.е. значения R^j, полученного в г-м испытании, на значение весовой функции WN, которое мы обозначим W^ (. Тогда получим

где суммирование производится по всем испытаниям. Включите процедуру Розенблата в свою программу метода Монте-Карло н вычислите Rx, для значений N = 4, 8, 16 и 32. Оцените показатель степени V из графика зависимости RN от N, построенного в дваждылогариф-мическом масштабе. Отличается ли найденная оценка V, от значения, полученного нз случайного блуждания V = 1/2?