计算科学 - 估计自动回避步行的次数nn - 吾爱随笔录

估计自动回避步行的次数nn

计算科学可能性组合学

2021-12-17 19:32:40

在过去的几天里，我一直在思考并在网上搜索一种能够估计自我避免步行（SAW）长度的算法 $n$ 在 $\mathbb{Z}^2$ . 有一种非常简单的方法可以通过简单地生成所有长度的随机游走 $n$ 然后检查每个人是否在自我回避。这适用于非常小的值 $n$ 但只要 $n\ge 10$ ，由于指数复杂性，这种方法变得完全过时了。我能够在 Python 中创建一个能够生成自动回避路径的函数 $n$ 使用以下算法：

$1)$ 从任意长度的 SAW 开始 $n$ （很容易选择长度的步行 $n$ 这只是上升 $y$ 轴例如）。

$2)$ 在 SAW 中选择一个随机点而不是它的末端，并让这个点作为枢轴，然后从 $\pi$ , $\frac\pi2$ 和 $-\frac\pi2$ .

$3)$ 对于 SAW 中严格放置在枢轴之后的每个点，以选定的旋转角度将其围绕枢轴旋转。

$4)$ 如果新获得的随机游走是自我避免的，那么我们保留它，否则重复步骤 $2)$ 和 $3)$ 直到你找到一对有效的。您可以根据需要多次重复这些步骤，以生成与我们开始时看似无关的 SAW。

问题是这种方法给出了一个长度的 SAW $n$ 并且不完全有助于估计长度 SAW 的数量 $n$ . 因此可以使用什么算法来估计长度为 SAW 的数量 $n$ 以及如何在 Python 中实现它？

1个回答

背景

正方形格子上长度为 N 的自回避游走数为：

0   1 
1   4 
2   12 
3   36 
4   100 
5   284 
6   780 
7   2172 
8   5916 
9   16268 
10   44100 
11   120292 
12   324932 
13   881500 
14   2374444 
15   6416596 
16   17245332 
17   46466676 
18   124658732 
19   335116620 
20   897697164 
21   2408806028 
22   6444560484 
23   17266613812 
24   46146397316 
25   123481354908 
26   329712786220 
27   881317491628 
28   2351378582244 
29   6279396229332 
30   16741957935348 
31   44673816630956 
32   119034997913020 
33   317406598267076 
34   845279074648708 
35   2252534077759844 
36   5995740499124412 
37   15968852281708724 
38   42486750758210044 
39   113101676587853932 
40   300798249248474268 
41   800381032599158340 
42   2127870238872271828 
43   5659667057165209612 
44   15041631638016155884 
45   39992704986620915140 
46   106255762193816523332 
47   282417882500511560972 
48   750139547395987948108 
49   1993185460468062845836 
50   5292794668724837206644 
51   14059415980606050644844 
52   37325046962536847970116 
53   99121668912462180162908 
54   263090298246050489804708 
55   698501700277581954674604 
56   1853589151789474253830500 
57   4920146075313000860596140 
58   13053884641516572778155044 
59   34642792634590824499672196 
60   91895836025056214634047716 
61   243828023293849420839513468 
62   646684752476890688940276172 
63   1715538780705298093042635884 
64   4549252727304405545665901684 
65   12066271136346725726547810652 
66   31992427160420423715150496804 
67   84841788997462209800131419244 
68   224916973773967421352838735684 
69   596373847126147985434982575724 
70   1580784678250571882017480243636 
71   4190893020903935054619120005916

这取自 Iwan Jensen 的 2013 年论文A new transfer-matrix algorithm for exact enumerations: self-avoiding walks on the square lattice。

SAW 行走的次数被认为可以通过方程来近似，其中。这些值在Jensen (2013)中进行了估计。至少从Nienhuis (1984, “Critical behavior of two-dimensional spin models and charge asymmetry in the Coulomb gas”)起，γ 的值就已经为人所知。

c_{n} \sim A µ^{n} n^{γ - 1}

$c_n \sim Aµ^n n^{γ−1}$

γ = 43 / 32, µ \sim 2.638, A \sim 1.17704242

$\gamma=43/32, µ\sim2.638, A\sim1.17704242$

上面的整数序列在整数序列在线百科全书中也被称为A001411。

Jensen (2013) 算法使用约 16,500 CPU 小时来枚举长度为 79 的自我回避行走。Zbarsky (2019)提出了一种渐近更快的算法，但不确定它是否会比 Jensen (2013) 算法更快。N的小值。

Nathan Clisby 的 2021 年论文Enumerative Combinatorics of Lattice Polymers并未专门处理 2D 步行，但似乎很好地概述了自动回避步行和邻近区域的更广泛用途。

算法

您的算法随机生成路径。这使得它不适合枚举，因为：

它可能会多次生成相同的路径。
因此，探索整个空间需要很长时间。

一个好的算法应该通过只访问每条路径一次来彻底探索空间。

实现这一点的最简单方法是使用递归回溯。我在下面实现了一个算法：

from typing import Final, List, Set, Tuple

def walk(n_max: int, n: int, x: int, y: int, used: Set[Tuple[int, int]]) -> int:
  """
  Recursive function to calculate the number of self-avoiding walks

  Our strategy here is to build a function that generates self-avoiding walks in
  a depth-first manner using backtracking to avoid duplication and a hash-set to
  avoid overlaps.

  Args:
    n_max   - Length of the walk
    n       - How far we are into the walk
    x       - Current x location
    y       - Current y location

  Returns:
    The number of self-avoiding walks of length `n_max`
  """
  # Possible displacement values on a square lattice
  dr_vals: Final[List[Tuple[int, int]]] = [(-1, 0), (1, 0), (0, 1), (0, -1)]

  # End recursion. We have discovered 1 walk!
  if n==n_max:
    return 1

  # Make a note that we're now at location (x,y) so it is unavailable
  used.add((x,y))

  # Body of recursion: we will count the walks leading away from (x,y)
  walks = 0

  # Look at all the possible directions we can go from here
  for dr in dr_vals:
    # Determine next coordinates given the displacement
    nx = x + dr[0]
    ny = y + dr[1]
    # Don't visit the neighbouring square twice!
    if (nx, ny) in used:
      continue
    # Visit the neighbouring square and count how many walks it has
    walks += walk(n_max, n + 1, nx, ny, used)

  # We've finished the body of the recursion, we now go back up the stack

  # Since we're going back up the stack we no longer occupy (x,y)
  used.remove((x,y))

  return walks

def main():
  # Make a table of how many walks of length n there are
  # Given the exponential increase the cost of computation and simplicity of this
  # algorithm, this will probably run forever
  for n in range(30):
    used: Set[Tuple[int, int]] = set([(1000, 1000)])
    print(n, walk(n, 0, 0, 0, used))

main()

其它你可能感兴趣的问题

上一篇如果我有一个函数而不是矩阵，是否可以使用 BLAS？下一篇如何正确计算 CPU 和 GPU FLOPS 性能？