Python 中的迷宫求解

Question

我不知疲倦地尝试在 python 中制作迷宫解算器。我已经使用了我所有的资源，比如朋友、互联网和堆栈。我已经根据我之前的堆栈问题对我的代码进行了很多调整，但即使完全复制代码（我不喜欢这样做）仍然无法得出答案。

maze/input 文件（嵌套列表）：

    [['*', '*', '*', '*', '*'],
    ['*', ' ', '*', ' ', '*'],
    ['*', ' ', ' ', ' ', '*'],
    ['*', ' ', '*', ' ', 'E'],
    ['*', 'S', '*', '*', '*']]

此函数不断循环迷宫中的相同点。我的起点 "S" 是 (4,1)，输出：

(4,1)
(4,0)
(3,1)

以上输出来自我用来调试函数的打印语句。它只是按顺序打印上面的内容，直到遇到递归 limit.Below 是我的求解函数：

already_visited=[]
def solve(x,y):
    global already_visited
    matrix = draw(load())
    print (x,y)

    #base cases
    if matrix[x][y] == "E":
        for row in matrix:
            row = str(row)[1:-1]
            print row
        return True
    if matrix[x][y] == "*":
        return False
    if matrix[x][y] == "x":
        return False

    matrix[x][y] = "x"

    #---------------------
    if (x,y) in already_visited: #check if we have already been here
        return False

    already_visited.append((x,y)) #add position to list
    #---------------------


    # recursive cases (matrix traversal)
    if (x < len(matrix)-1 and solve1(x+1,y)):
        return True
    elif (y > 0 and solve1(x,y-1)):
        return True
    elif (x > 0 and solve1(x-1,y)):
        return True
    elif (y < len(matrix)-1 and solve1(x,y+1)):
        return True
    else:
        return False

我进入 x 和 y 函数的所有内容都是起始索引 S，如上面贴出的迷宫所示。非常感谢任何帮助！

Answer 1

此处的代码无效：

if (x < len(matrix)-1 and solve1(x+1,y)):
        return True
    elif (y > 0 and solve1(x,y-1)):
        return True
    elif (x > 0 and solve1(x-1,y)):
        return True
    elif (y < len(matrix)-1 and solve1(x,y+1)):
        return True
    else:
        return False

问题在于递归。您的程序所做的是：

可能的话往右走
如果没有尝试
如果不行试试左边
不行的话往下试试

因为你是递归的，所以你的程序会一直运行直到碰壁，

然后往上爬，直到撞墙，

然后离开，

然后往下

这使得运行圈子变得非常容易。

据我所知，您有两种简单的可能性：

记住如果您访问过某个位置并且在递归中总是 return False 如果您已经来过这里
运行随机

1 号看起来像这样：

already_visited=[]
def solve1(x,y):
    global already_visited
    matrix = draw(load())
    print (x,y)

    #base cases
    if matrix[x][y] == "E":
        for row in matrix:
            row = str(row)[1:-1]
            print row
        return True
    if matrix[x][y] == "*":
        return False
    if matrix[x][y] == "x":
        return False

    matrix[x][y] = "x"

    #---------------------
    if (x,y) in already_visited: #check if we have already been here
        return False

    already_visited.append((x,y)) #add position to list
    #---------------------


    # recursive cases (matrix traversal)
    if (x < len(matrix)-1 and solve1(x+1,y)):
        return True
    elif (y > 0 and solve1(x,y-1)):
        return True
    elif (x > 0 and solve1(x-1,y)):
        return True
    elif (y < len(matrix)-1 and solve1(x,y+1)):
        return True
    else:
        return False

Answer 2

用正确的约束检查替换你的函数的开始使其在没有运行进入 IndexError 的情况下工作。首先，您需要确保 x 在您的矩阵行数范围内。然后你需要检查相同的列数。这里len()给出的值是第一个超出范围的。

此外，您在每次调用求解器时都会重新加载矩阵。您应该只对一个矩阵进行操作以进行持久更改。为此，将其添加为函数的参数：

def solve2(matrix,x,y):
    print (x,y)
    if x >= len(matrix) or y >= len(matrix[x]):
        return False
    [...]

然后在第一个运行上像 solve2(draw(load()),4,1) 一样调用它，并用 solve2(matrix,x,y-1)) 的等效项替换每个递归调用。同样适用于 solve1()。

Answer 3

制作迷宫很容易。你先做个网格。

import networkx as nx
import numpy as np

G = nx.Graph()
for i in range(5):
    for j in range(5):
        G.add_node((i,j))
        if i >0:
            G.add_edge((i-1,j),(i,j))
        if j>0:
            G.add_edge((i,j),(i,j-1))

然后删除留下路径节点的墙。

a = np.array([['*', '*', '*', '*', '*'],
       ['*', ' ', '*', ' ', '*'],
       ['*', ' ', ' ', ' ', '*'],
       ['*', ' ', '*', ' ', 'E'],
       ['*', 'S', '*', '*', '*']])

for i in range(5):
    for j in range(5):
        if a[i][j]=='*':
            G.remove_node((i,j))

我在作弊，开始和结束位置。但是后来我让 NetworkX 找到了从头到尾的路径。

for point in nx.algorithms.astar_path(G,(4,1),(3,4)):
    print(point)

Python 中的迷宫求解

Maze Solving in Python

python

maze

solver