主题
Search

自回避游走

自回避游走是指从一个点到另一个点且永不 相交 的路径。这类路径通常被认为发生在格子上，因此步长仅允许在离散数量的方向上和特定的长度上。

SelfAvoidingWalkPositive

考虑一个二维 n×n 方格网格上的自回避游走（即永不访问同一格点的格路），它从原点开始，第一步沿正水平方向，并且仅限于非负格点。步数为 n=1, 2, ... 的此类路径的数量为 1, 2, 5, 12, 30, 73, 183, 456, 1151, ... (OEIS A046170)。

SelfAvoidingWalk

类似地，考虑一个自回避游走，它从原点开始，第一步沿正水平方向，不限于非负格点，但限制为在采取第一个向下步之前采取向上步。步数为 n=1, 2, ... 的此类路径的数量为 1, 2, 5, 13, 36, 98, 272, 740, 2034, ... (OEIS A046171)。

SelfAvoidingRookWalks

自回避车游走是在 m×n 网格上的游走，它从 (0,0) 开始，在 (m,n) 结束，并且仅由水平和垂直步组成。下表给出了对于小的 m 和 n，此类游走的头几个数字 R(m,n)。对于 m=n=1, 2, ... 的值是 2, 12, 184, 8512, 1262816, ... (OEIS A007764)。

m\n23456
22
3412
4838184
5161259768512
6324145382793841262816

有许多已知的公式用于计算小的 m,n 的 R(m,n)。例如，

R(m,2)=2^(m-1).
(1)

对于 R(m,3) 存在递推关系，由 R(1,3)=1, R(2,3)=4, R(3,3)=12, R(4,3)=38 给出，并且

R(m,3)=4R(m-1,3)-3R(m-2,3)+2R(m-3,3)+R(m-3,4)
(2)

对于 m>=5，以及生成函数

R(m,3)=1/((m-1)!)(d^(m-1))/(dx^(m-1))((x-1)(x+1))/((x^2+3x-1)(x^2-x+1))|_(x=0)
(3)

(Abbott 和 Hanson 1978, Finch 2003)。

一个相关的序列是可以由在平面中弯曲长度为 n 的一段金属丝形成的形状的数量，其中弯曲为 0 或 +/-90 degrees 度，金属丝可以直角交叉但不能越过自身。长度为 1, 2, ... 的金属丝的形状数量为 1, 2, 4, 10, 24, 66, 176, 493, ... (OEIS A001997)。

SelfAvoidingZigZagWalks

考虑一个二维 n×n 方格网格上的自回避游走，从一个角到另一个角，使得没有两个连续的步长方向相同。对于 n=1, 2, ...，此类路径的数量为 1, 2, 2, 4, 10, 36, 188, ... (OEIS A034165；将 1×1 点“格子”上的路径数计为 1)，这些路径的最大长度为 0, 2, 4, 10, 12, 26, 36, ... (OEIS A034166)。

另请参阅

格路, 随机游走, 自回避多边形, 自回避游走连接常数, 阶梯多边形, 三向选择游走

使用 Wolfram|Alpha 探索

参考文献

Abbott, H. L. 和 Hanson, D. "一个格路问题。" Ars Combinatoria 6, 163-178, 1978.Alm, S. E. "自回避游走连接常数的上限。" Combin. Prob. Comput. 2, 115-136, 1993.Domb, C. "关于随机游走问题中的多次返回。" Proc. Cambridge Philos. Soc. 50, 586-591, 1954.Domb, C. "格子上的自回避游走。" Adv. Chem. Phys. 15, 229-259, 1969.Finch, S. R. "自回避游走常数。" §5.10 in 数学常数。 Cambridge, England: Cambridge University Press, pp. 331-339, 2003.Hayes, B. "如何避免自己。" Amer. Sci. 86, 314-319, 1998.Kesten, H. "关于自回避游走的数量。" J. Math. Phys. 4, 960-969, 1963.Lawler, G. F. 随机游走的交点。 Boston, MA: Birkhäuser, 1991.Sloane, N. J. A. “整数序列在线百科全书”中的序列 A001997/M1206, A007764, A034165, A034166, A046170, 和 A046171。Whittington, S. G. 和 Guttman, A. J. "穿过正方形的自回避游走。" J. Phys. A 23, 5601-5609, 1990.

在 Wolfram|Alpha 中引用

自回避游走

请引用为

韦斯坦因，埃里克·W。 "自回避游走。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/Self-AvoidingWalk.html

主题分类