主題
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) 結束,並且僅由水平和垂直步組成。下表給出了對於小的 mn,此類遊走的頭幾個數字 R(m,n)。對於 m=n=1, 2, ... 的值是 2, 12, 184, 8512, 1262816, ... (OEIS A007764)。

m\n23456
22
3412
4838184
5161259768512
6324145382793841262816

有許多已知的公式用於計算小的 m,nR(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)。


另請參閱

格路, 隨機遊走, 自迴避多邊形, 自迴避遊走連線常數, 階梯多邊形, 三向選擇遊走

使用 探索

參考文獻

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, 和 A046171Whittington, S. G. 和 Guttman, A. J. "穿過正方形的自迴避遊走。" J. Phys. A 23, 5601-5609, 1990.

在 中引用

自迴避遊走

請引用為

韋斯坦因,埃裡克·W。 "自迴避遊走。" 來自 —— 資源。 https://mathworld.tw/Self-AvoidingWalk.html

主題分類