查看“︁自避行走”︁的源代码

{{refimprove|time=2020-02-10T07:09:43+00:00}}
{{Copyedit|time=2020-02-10T06:34:35+00:00}}
[[File:Self_avoiding_walk.svg|右|200x200像素]]
在[[数学]]中，'''自避行走（简称：SAW，Self-Avoiding Walk）'''是一种[[格点]]上的[[随机漫步]]，但是不能多次通過同一点。因此，SAW不是一种[[马尔可夫链]]， 但事實上，SAW模型在[[物理学]]、[[化学]]、生物学中有很多应用。
[[File:SAWwiki.jpg|缩略图|这是自避行走]]
[[File:NSAW.jpg|缩略图|这不是自避行走]]
[[File:Натурализация гамильтоновых циклов.jpg|缩略图|8x8网格图上的三个例子]]
<br />

== 应用 ==

* [[溶剂]]和[[聚合物]]
* [[蛋白质]]
*高分子
* [[纽结理论]]
* [[随机漫步]]
* [[保罗·弗洛里]]学了化学中的自避行走。<ref>{{Cite book|last=P. Flory|title=Principles of Polymer Chemistry|url=https://archive.org/details/dli.ernet.286013|year=1953|publisher=Cornell University Press|isbn=9780801401343|pages=[https://archive.org/details/dli.ernet.286013/page/672 672]|authorlink=Paul Flory}}</ref>
* [[网络理论]]<ref>{{Cite journal|title=Self-avoiding walks on scale-free networks|last=Carlos P. Herrero|journal=Phys. Rev. E|issue=3|doi=10.1103/PhysRevE.71.016103|year=2005|volume=71|pages=1728|arxiv=cond-mat/0412658|bibcode=2005PhRvE..71a6103H|pmid=15697654}}</ref> 
* Gompertz distribution<ref>{{Cite journal|title=The distribution of path lengths of self avoiding walks on Erdős–Rényi networks|last=Tishby|first=I.|last2=Biham|first2=O.|date=2016|journal=Journal of Physics A: Mathematical and Theoretical|issue=28|doi=10.1088/1751-8113/49/28/285002|volume=49|pages=285002|arxiv=1603.06613|bibcode=2016JPhA...49B5002T|last3=Katzav|first3=E.}}</ref>
* [[ER随机图]]
* 有数学家认为自避行走的[[缩放极限]]是一个{{Math|''κ'' {{=}} {{sfrac|8|3}}}}的[[Schramm-Loewner演变]]。<ref name=":0" />

== 介绍 ==
自避行走是一个[[分形]]。<ref>{{Cite journal|title=New approach to self-avoiding walks as a critical phenomenon|url=http://havlin.biu.ac.il/Publications.php?keyword=New+approach+to+self-avoiding+walks+as+a+critical+phenomenon&year=*&match=all|last=[[Shlomo Havlin|S. Havlin]], D. Ben-Avraham|journal=J. Phys. A|issue=6|doi=10.1088/0305-4470/15/6/013|year=1982|volume=15|pages=L321–L328|bibcode=1982JPhA...15L.321H|access-date=2020-02-10|archive-date=2020-09-22|archive-url=https://web.archive.org/web/20200922215351/http://havlin.biu.ac.il/Publications.php?keyword=New+approach+to+self-avoiding+walks+as+a+critical+phenomenon&year=*&match=all|dead-url=no}}</ref><ref>{{Cite journal|title=Theoretical and numerical study of fractal dimensionality in self-avoiding walks|url=http://havlin.biu.ac.il/Publications.php?keyword=Theoretical+and+numerical+study+of+fractal+dimensionality+in+self-avoiding+walks&year=*&match=all|last=[[Shlomo Havlin|S. Havlin]], D. Ben-Avraham|journal=Phys. Rev. A|issue=3|doi=10.1103/PhysRevA.26.1728|year=1982|volume=26|pages=1728–1734|bibcode=1982PhRvA..26.1728H|access-date=2020-02-10|archive-date=2018-11-12|archive-url=https://web.archive.org/web/20181112141454/http://havlin.biu.ac.il/Publications.php?keyword=Theoretical+and+numerical+study+of+fractal+dimensionality+in+self-avoiding+walks&year=*&match=all|dead-url=no}}</ref> 例如，<ref>{{Cite journal|title=The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion|last=A. Bucksch, [[Greg Turk|G. Turk]], J.S. Weitz|journal=PLOS ONE|issue=1|doi=10.1371/journal.pone.0085585|year=2014|volume=9|pages=e85585|arxiv=1304.3521|bibcode=2014PLoSO...985585B|pmc=3899046|pmid=24465607}}</ref>
{| class="wikitable"
|+
!维度d
![[分形维数]]
!
|-
|{{Math|''d'' {{=}} 2}}
|4/3
|
|-
|{{Math|''d'' {{=}} 3}}
|5/3
|
|-
|{{Math|''d'' ≥ 4}}
|2
|4是“upper critical dimension”（上面临界维度）
|}
没有已知的公式用於计算给予[[格子]]的SAW数。<ref>{{Cite journal|title=How to Avoid Yourself|url=http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-07-Hayes-self-avoidance.pdf|last=Hayes B|date=Jul–Aug 1998|journal=American Scientist|issue=4|doi=10.1511/1998.31.3301|volume=86|page=314|access-date=2020-02-10|archive-date=2020-09-28|archive-url=https://web.archive.org/web/20200928094817/http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-07-Hayes-self-avoidance.pdf|dead-url=no}}</ref><ref>{{Cite journal|title=The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes|last=Liśkiewicz M|last2=Ogihara M|date=July 2003|journal=Theoretical Computer Science|issue=1–3|doi=10.1016/S0304-3975(03)00080-X|volume=304|pages=129–56|last3=Toda S}}</ref>

{{Math|''m'' × ''n''}} 矩形点阵在只允許選擇減少[[曼哈頓距離]]的方向從一角往其對角行走的情況下有

:<math>{m+n \choose m, \ n}</math>

个SAW。

== 普遍性 ==
主要条目：[[普遍性 (物理学)]]

设<math>c_n</math>是SAW数。这满足<math>c_nc_m \leq c_{n+m}</math>因此<math>\log c_n</math>是[[次可加性|次可加]]的以及

<math>\mu = \lim_{n\to \infty} c_n^{1/n}</math>

存在。格点六角形（hexagonal lattice）的<math>\mu = \sqrt{2+\sqrt{2}}</math>。<ref name=":0">{{Cite journal|title=The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt2}$|url=http://arxiv.org/abs/1007.0575|last=Duminil-Copin|first=Hugo|last2=Smirnov|first2=Stanislav|date=2011-06-27|journal=arXiv:1007.0575 [math-ph]}}</ref>（[[斯坦尼斯拉夫·斯米尔诺夫]]）

某一猜想稱：当<math>n\to \infty</math>的时候

<math>c_n \approx \mu^n n^{11/32}</math>

上面的<math>\mu</math>依赖[[格点]]，但是11/32这个数是[[普遍性 (物理学)|普遍]]的。

== 参见 ==

* [[临界现象]]
* [[普遍性 (物理学)]]
* [[隨機漫步|随机走]]

== 参考文献 ==
{{Reflist}}

== 阅读 ==
{{ReflistH}}

# {{Cite book|last=Madras|first=N.|last2=Slade, G.|year=1996|title=The Self-Avoiding Walk|publisher=Birkhäuser|isbn=978-0-8176-3891-7}}
# {{Cite book|last=Lawler|first=G. F.|year=1991|title=Intersections of Random Walks|publisher=Birkhäuser|isbn=978-0-8176-3892-4}}
# {{Cite journal|title=The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk|last=Madras, N.|last2=Sokal, A. D.|journal=Journal of Statistical Physics|issue=1–2|doi=10.1007/bf01022990|year=1988|volume=50|pages=109–186|bibcode=1988JSP....50..109M}}
# {{Cite journal|title=Shape of a self-avoiding walk or polymer chain|url=|last=Fisher, M. E.|journal=Journal of Chemical Physics|issue=2|doi=10.1063/1.1726734|year=1966|volume=44|pages=616–622|bibcode=1966JChPh..44..616F}}

{{Stochastic processes}}

{{ReflistF}}
[[Category:计算化学]]
[[Category:计算物理学]]
[[Category:離散幾何]]
[[Category:多邊形]]
[[category:随机过程]]