Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Само избегание walk.svg

В математике , А самоизбегающая ходьба ( ПАВ ) представляет собой последовательность ходов на решетке (а решетка путь ) , который не посещает ту же точку более чем один раз. Это частный случай понятия пути из теории графов . Самоизбегающий многоугольник ( SAP ) является закрытой самоизбегающих ходьбой на решетке. С математической точки зрения о самопроизвольном беге точно известно очень мало, хотя физики выдвинули множество предположений, которые считаются верными и полностью подтверждаются численным моделированием.

В вычислительной физике прогулка с самоизбеганием представляет собой цепочку в R 2 или R 3 с определенным количеством узлов, обычно с фиксированной длиной шага и тем свойством, что она не пересекает себя или другую прогулку. Система ПАВ удовлетворяет так называемому условию исключенного объема . Считается, что в более высоких измерениях ПАВ ведет себя так же, как обычное случайное блуждание .

SAW и SAP играют центральную роль в моделировании топологического и теоретико-узлового поведения нитевидных и петлевых молекул, таких как белки . Действительно, ПАВ, возможно, впервые были введены химиком Полом Флори [1] [ сомнительно - обсудить ] для моделирования реального поведения цепочечных объектов, таких как растворители и полимеры , физический объем которых запрещает многократное использование одного и того же пространственная точка.

SAW - это фракталы . [2] [3] Например, в г = 2 фрактальной размерности 4/3, для г = 3 она близка к 5/3 , а для D ≥ 4 фрактальной размерности 2 . Размер называется верхним критическим размером, выше которого исключенный объем незначителен. ПАВ, которая не удовлетворяет условию исключенного объема, недавно была исследована для моделирования явной геометрии поверхности в результате расширения ПАВ. [4]

Свойства ПАВ нельзя рассчитать аналитически, поэтому используется численное моделирование . Алгоритм поворота является распространенным методом цепь Маркова Монте - Карло моделирования для равномерной меры по п -шагового самоизбегающих прогулок. Алгоритм поворота работает, совершая обход и случайным образом выбирая точку на этом обходе, а затем применяя симметричные преобразования (вращения и отражения) к обходу после n- го шага для создания нового обхода.

Вычисление количества блужданий с самоизбеганием в любой заданной решетке - это обычная вычислительная проблема . В настоящее время нет известной формулы, хотя существуют строгие методы приближения. [5] [6]

Для самостоятельных прогулок от одного конца диагонали до другого с движениями только в положительном направлении есть ровно

пути для прямоугольной решетки m × n .

Универсальность [ править ]

Одним из явлений, связанных с самопроизвольными прогулками и моделями статистической физики в целом, является понятие универсальности , то есть независимости макроскопических наблюдаемых от микроскопических деталей, таких как выбор решетки. Одна важная величина, которая появляется в предположениях универсальных законов, - это константа связки , определяемая следующим образом. Обозначим через c n количество n -ступенчатых блужданий без исключения. Поскольку каждый ( n + m ) -шаговый обход с самопроизвольным уходом можно разложить на n- шаговый обход с само-избеганием и m- шаговый обход с самоизбеганием, отсюда следует, что c n+ m ≤ c n c m . Поэтому последовательность {лог с п } является субаддитивным и мы можем применить лемму Фекета , чтобы показатьчто существует предел

μ называется константой связки , поскольку c n зависит от конкретной решетки, выбранной для блуждания, так же как и μ . Точное значение μ известно только для гексагональной решетки, где оно равно: [7]

Для других решеток μ было вычислено только численно и, как полагают, даже не является алгебраическим числом . Предполагается, что [ необходима цитата ]

при n → ∞ , где μ зависит от решетки, а степенная поправка - нет; Другими словами, этот закон считается универсальным.

В сетях [ править ]

Прогулки с самоизбеганием также изучались в контексте теории сетей . [8] В этом контексте принято рассматривать SAW как динамический процесс, так что на каждом временном шаге ходунок случайным образом переключается между соседними узлами сети. Обход заканчивается, когда обходчик достигает тупикового состояния, так что он больше не может переходить к новым непосещенным узлам. Недавно было обнаружено, что в сетях Эрдеша – Реньи распределение длин путей таких динамически выращиваемых ПАВ может быть вычислено аналитически и следует распределению Гомперца . [9]

Лимиты [ править ]

Рассмотрим единообразную меру на n -шаговых прогулках с самоизбеганием в полной плоскости. В настоящее время неизвестно, индуцирует ли предел равномерной меры при n → ∞ меру на бесконечных блужданиях по всей плоскости. Однако Гарри Кестен показал, что такая мера существует для самопроизвольных прогулок в полуплоскости. Одним из важных вопросов, связанных с самоизбеганием блужданий, является существование и конформная инвариантность масштабного предела , то есть предела, когда длина блуждания стремится к бесконечности, а сетка решетки стремится к нулю. Предполагается, что масштабный предел самопереходного блуждания описывается эволюцией Шрамма – Лёвнера с параметром κ =8/3.

См. Также [ править ]

  • Критические явления
  • Универсальность (динамические системы)
  • Случайная прогулка
  • Гамильтонов путь
  • Змея (жанр видеоигр)

Ссылки [ править ]

  1. ↑ П. Флори (1953). Основы химии полимеров . Издательство Корнельского университета. п. 672. ISBN. 9780801401343.
  2. ^ С. Хэвлин ; Д. Бен-Авраам (1982). «Новый подход к самопроизвольным прогулкам как критическое явление» . J. Phys. . 15 (6): L321 – L328. Bibcode : 1982JPhA ... 15L.321H . DOI : 10.1088 / 0305-4470 / 15/6/013 .
  3. ^ С. Хэвлин ; Д. Бен-Авраам (1982). «Теоретическое и численное исследование фрактальной размерности в прогулках с самоизбежанием» . Phys. Rev. A . 26 (3): 1728–1734. Bibcode : 1982PhRvA..26.1728H . DOI : 10.1103 / PhysRevA.26.1728 .
  4. ^ А. Бакш; Г. Тюрк ; Дж. С. Вайц (2014). «Волоконная прогулка: модель роста, управляемого кончиками с боковым расширением» . PLOS ONE . 9 (1): e85585. arXiv : 1304,3521 . Bibcode : 2014PLoSO ... 985585B . DOI : 10.1371 / journal.pone.0085585 . PMC 3899046 . PMID 24465607 .  
  5. ↑ Hayes B (июль – август 1998 г.). «Как избежать себя» (PDF) . Американский ученый . 86 (4): 314. DOI : 10,1511 / 1998.31.3301 .
  6. ^ Liśkiewicz M; Огихара М; Тода S (июль 2003 г.). «Сложность подсчета самоизбегающих блужданий в подграфах двумерных сеток и гиперкубов». Теоретическая информатика . 304 (1–3): 129–56. DOI : 10.1016 / S0304-3975 (03) 00080-X .
  7. ^ Думинил-Копен, Гюго; Смирнов, Станислав (1 мая 2012 г.). «Связующая константа сотовой решетки равна sqrt (2 + sqrt 2)». Анналы математики . 175 (3): 1653–1665. arXiv : 1007,0575 . DOI : 10.4007 / annals.2012.175.3.14 .
  8. ^ Карлос П. Эрреро (2005). «Самоизбегающие прогулки по безмасштабным сетям». Phys. Rev. E . 71 (3): 1728. arXiv : cond-mat / 0412658 . Bibcode : 2005PhRvE..71a6103H . DOI : 10.1103 / PhysRevE.71.016103 . PMID 15697654 . 
  9. ^ Тишби, I .; Biham, O .; Кацав, Э. (2016). «Распределение длин пути самопроизвольных прогулок по сетям Эрдеша – Реньи». Журнал физики A: математический и теоретический . 49 (28): 285002. arXiv : 1603.06613 . Bibcode : 2016JPhA ... 49B5002T . DOI : 10.1088 / 1751-8113 / 49/28/285002 .

Дальнейшее чтение [ править ]

  1. Madras, N .; Слэйд, Г. (1996). Самоуничтожающаяся прогулка . Birkhäuser. ISBN 978-0-8176-3891-7.
  2. Лоулер, GF (1991). Пересечения случайных блужданий . Birkhäuser. ISBN 978-0-8176-3892-4.
  3. Madras, N .; Сокал, А.Д. (1988). «Алгоритм поворота - высокоэффективный метод Монте-Карло для самоизбегающей прогулки». Журнал статистической физики . 50 (1–2): 109–186. Bibcode : 1988JSP .... 50..109M . DOI : 10.1007 / bf01022990 .
  4. Фишер, ME (1966). «Форма самоустраивающейся прогулки или полимерной цепи». Журнал химической физики . 44 (2): 616–622. Bibcode : 1966JChPh..44..616F . DOI : 10.1063 / 1.1726734 .

Внешние ссылки [ править ]

  • Последовательность OEIS A007764 (количество непересекающихся (или самопересекающихся) ладейных путей, соединяющих противоположные углы сетки n X n) - количество путей самоизбегания, соединяющих противоположные углы сетки N × N , для N от 0 до 12. Также включает расширенный список до N = 21.
  • Вайсштейн, Эрик В. «Самопроизвольная прогулка» . MathWorld .
  • Java-апплет двумерной прогулки с самоизбеганием
  • Общая реализация Python для имитации SAW и расширения FiberWalks на квадратной решетке в n-мерном пространстве.
  • Программное обеспечение Norris для создания SAW на алмазном кубе .