Python 蒙特卡罗模拟循环

Question

我正在做一个简单的蒙特卡洛模拟脚本，之后会把它扩展到一个更大的项目。这个脚本是一个基本的爬虫，试图在一个网格中从点A移动到点B。点A的坐标是(1,1)（这是左上角），而点B的坐标是(n,n)（这是右下角，n是网格的大小）。

当爬虫开始移动时，它有四个选择，可以向左、向右、向上或向下移动（不允许斜着移动）。如果这四个选项中的任何一个满足以下条件：

1. 新点必须仍然在n x n网格的边界内
2. 新点之前没有被访问过

那么新点会在剩下的有效选项中随机选择（据我所知，Python使用梅森旋转算法来生成随机数）。

我想运行这个模拟1,000,000次（下面的代码只运行了100次），每次迭代应该在以下情况下结束：

1. 爬虫被卡住了（没有有效的移动选项）
2. 爬虫到达了网格的最终目的地(n,n)。

我以为我实现了算法，但显然有些地方出错了。无论我运行多少次模拟（100次或1,000,000次），我只得到1次成功的事件，爬虫成功到达了终点，其余的尝试（99次或999,999次）都失败了。

我敢打赌我遗漏了一些简单的东西，但不知道为什么看不出来。有什么想法吗？

非常感谢！

编辑：文本中的一些错别字已被更正。

import random

i = 1 # initial coordinate top left corner
j = 1 # initial coordinate top left corner
k = 0 # counter for number of simulations
n = 3 # Grid size

foundRoute = 0 # counter for number of cases where the final point is reached
gotStuck = 0 # counter for number of cases where no valid options found
coordList = [[i, j]]

while k < 100:
    while True:
        validOptions = []

        opt1 = [i - 1, j]
        opt2 = [i, j + 1]
        opt3 = [i + 1, j]
        opt4 = [i, j - 1]

        # Check 4 possible options out of bound and re-visited coordinates are
        # discarded:

        if opt1[0] != 0 and opt1[0] <= n and opt1[1] != 0 and opt1[1] <= n:
            if not opt1 in coordList:
                validOptions.append(opt1)

        if opt2[0] != 0 and opt2[0] <= n and opt2[1] != 0 and opt2[1] <= n:
            if not opt2 in coordList:
                validOptions.append(opt2)

        if opt3[0] != 0 and opt3[0] <= n and opt3[1] != 0 and opt3[1] <= n:
            if not opt3 in coordList:
                validOptions.append(opt3)

        if opt4[0] != 0 and opt4[0] <= n and opt4[1] != 0 and opt4[1] <= n:
            if not opt4 in coordList:
                validOptions.append(opt4)

        # Break loop if there are no valid options
        if len(validOptions) == 0:
            gotStuck = gotStuck + 1
            break

        # Get random coordinate among current valid options
        newCoord = random.choice(validOptions)

        # Append new coordinate to the list of grid points visited (to be used
        # for checks)
        coordList.append(newCoord)

        # Break loop if lower right corner of the grid is reached
        if newCoord == [n, n]:
            foundRoute = foundRoute + 1
            break

        # If the loop is not broken, assign new coordinates
        i = newCoord[0]
        j = newCoord[1]
    k = k + 1

print 'Route found %i times' % foundRoute
print 'Route not found %i times' % gotStuck

Answer 1

你的问题在于你从来没有清理过你访问过的位置。你需要修改一下那个跳出内层 while 循环的代码块，让它看起来像这样：

 if len(validOptions) == 0:
     gotStuck = gotStuck + 1
     coordList = [[1,1]]
     i,j = (1,1)
     break

你还需要修改一下你成功时的代码块：

if newCoord == [n, n]:
    foundRoute = foundRoute + 1
    coordList = [[1,1]]
    i,j = (1,1)
    break

另外，你也可以把这段代码直接放在内层 while 循环之前。这样你代码的开头就会变成：

k = 0 # counter for number of simulations
n = 3 # Grid size  
foundRoute = 0 # counter for number of cases where the final point is reached
gotStuck = 0 # counter for number of cases where no valid options found
while k < 100:
    i,j = (1,1) 
    coordList = [[i,j]]
    while True:
        #Everything else