Python中迷宫求解程序性能的改进

Question

各位程序员。我的一个项目需要帮助。我在做一个解决迷宫的程序。它读取一个图像文件，它必须是黑白的（黑色像素是墙，白色像素是路径），顶部只有一个像素是迷宫的入口，底部只有一个白色像素是出口。在

代码有三个主要部分：

1）程序首先在迷宫中创建节点，遵循一组规则。例如，这里有一个简单的迷宫：

所有节点都用红色绘制：

节点就像角落，十字路口，每个可以改变方向的点。还测量了每个节点到迷宫出口的距离。当它生成所有节点时，它将它们放在一个列表中。在

2）一旦生成所有节点，程序将遍历列表中的所有节点，并尝试在每个可能的方向搜索其他节点，以“链接”它们，建立可能的路径。例如，如果它检测到某个节点上方有一条路径，它将从该节点的坐标开始搜索一行中的每一个像素，然后再向上遍历所有节点列表，以查看另一个节点是否与这些坐标匹配。如果它在某个点找到一个，它会将它们链接起来，然后开始向右搜索（当然，如果有一条通向右侧的路径），等等，搜索每个方向。在

3）一旦所有的节点连接在一起，每个可能的路径都建立起来了，它将从迷宫的入口节点开始，运行我的A*算法实现来找出正确的路径，如果它走到了死胡同，它就会返回。如你所见，它解决迷宫没有困难。在

所以我的程序起作用了。那有什么问题吗？ 问题是节点连接部分。在小迷宫上，大约需要半秒钟。但是如果迷宫稍微大一点，那么节点的数量就会急剧增加。如果每个节点有600个节点，我可以想象它每迭代一次。。。这需要很长时间。在

所以这就是我请求帮助的原因：一种更好、更快的方式将节点连接在一起。 我已经在pastebin（https://pastebin.com/xtmTm7wb）上发布了整个代码，如果有点乱，很抱歉，当我编程时已经很晚了。节点连接部分从第133行开始，到第196行结束。在

以下是节点链接代码：

counter = 0
last = 0
for node in nodelist:
    a = node.pos[0]
    b = node.pos[1]
    if node.paths[0]:
        for i in range(b-1,0,-1):
            if mazepix[a,i] == blackpix:
                break
            if any(x.pos == (a,i) for x in nodelist):
                for iteration in nodelist:
                    if iteration.pos == (a,i):
                        indexofnodetolinkto = iteration.index
                        break
                node.connections.append(indexofnodetolinkto)
                # print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
                break

    if node.paths[1]:
        for i in range(a+1,maze.size[0]):
            if mazepix[i,b] == blackpix:
                break
            if any(x.pos == (i,b) for x in nodelist):
                for iteration in nodelist:
                    if iteration.pos == (i,b):
                        indexofnodetolinkto = iteration.index
                        break
                node.connections.append(indexofnodetolinkto)
                # print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
                break

    if node.paths[2]:
        for i in range(b+1,maze.size[1]):
            if mazepix[a,i] == blackpix:
                break
            if any(x.pos == (a,i) for x in nodelist):
                for iteration in nodelist:
                    if iteration.pos == (a,i):
                        indexofnodetolinkto = iteration.index
                        break
                node.connections.append(indexofnodetolinkto)
                # print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
                break

    if node.paths[3]:
        for i in range(a-1,0,-1):
            if mazepix[i,b] == blackpix:
                break
            if any(x.pos == (i,b) for x in nodelist):
                for iteration in nodelist:
                    if iteration.pos == (i,b):
                        indexofnodetolinkto = iteration.index
                        break
                node.connections.append(indexofnodetolinkto)
                # print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
                break

    counter += 1
    percent = (counter/nbrofnodes)*100
    if int(percent)%10 == 0 and int(percent) != last:
        print("Linking %d%% done..."%percent)
        last = int(percent)

print("All node linked.")

谢谢你，如果你读了所有这些，我知道这不是一个非常精确的问题，但我花了太多的时间试图使这个工作，现在，我真的被困在我可以改进它的方法上。在

Answer 1

你的程序非常慢，因为这一部分需要很长时间，而且你对每个节点都要做很多次：

            for iteration in nodelist:
                if iteration.pos == (i,b):
                    indexofnodetolinkto = iteration.index
                    break

有很多方法可以让它更快。在

您可以使用位置作为键将节点放入字典中，因此您只需查找一个位置即可找到其中的节点。在

更好的是，可以将节点放入行列表和列列表中，按位置排序，然后只尝试连接列表中的相邻节点。在

但最好的做法是完全忘记这些节点，直接在位图上进行BFS搜索。在

因为这是一个有趣的问题，我用一个简单的BFS编写了一个快速版本。我不想毁了你所有的乐趣，所以这里只是BFS部分，这样你就可以明白我直接在图像上做BFS是什么意思：

^{pr2}$

我们没有使用单独的对象和链接集来记住路径，而是将像素标记为直接在图像中访问过的像素。我们不需要使用任何类型的实际链接来链接一个像素到另一个像素，我们只需要检查所有4个方向，寻找相邻的白色像素。在

这是一个逐级的BFS，所以我们总是知道新像素离入口有多远，我们标记一个访问过的像素的颜色表示它与入口的距离（mod 3）。这使得我们在找到出口时可以重建最短路径。在

编辑：很长一段时间了，OP玩得很开心，下面是完整的python解算器：

^{3}$

Answer 2

你的迷宫只有301x301像素，所以在我看来0.5秒对于解决这个问题来说时间太长了。当我使用光栅A*方法时：

• How to speed up A* algorithm at large spatial scales?

整个解决方案只需要~1.873ms，这与你的~500ms有很大的不同。粗图a*有较大的开销，所以我很好奇，想测试它，所以我用上面的链接中的代码和“强”> C++ + <强>编码我的版本，结果是从图像获取的图形占到{{CD3}}，图a*占到^ {CD4}}，所以与你的（+ /计算机设置差）仍然有很大的不同。在

那么首先要检查什么？

我不是python程序员，但我在您的代码中看不到任何图像访问。您应该检查您的图像访问是否快速。这是新手经常犯的错误

GetPixel/PutPixel
Pixels[][]

这些通常是痛苦的缓慢（以我在GDI Win32上的经验，比直接像素访问慢1000-10000倍），如果更正，会有很大的不同。有关详细信息，请参阅：

• Display an array of color in C

列表用法的另一个常见错误是在没有预先分配的情况下递增地向列表添加元素。对于小列表来说，这不是问题，但是对于大量的元素，在添加元素的情况下重新分配会通过一次又一次地复制内容来减慢速度。在列表中插入和删除元素也是如此。改进列表访问会产生巨大的影响，特别是对于像O(n^2)这样的多项式复杂性和较慢的。。。在

算法

算法上的微小变化会产生巨大的影响。在您的例子中，我结合使用了DIP边缘检测技术和加速结构来进行拓扑排序的边缘。它将O(n)或O(n^2)搜索更改为简单的O(1)操作。其思想是将迷宫的所有顶点按xy和yx排序。如果每个顶点知道它在这种结构中的索引，就可以很容易地得到它的相邻顶点。。。在

堆栈/堆垃圾处理

这会让事情慢很多。尤其是递归函数。递归级别和操作数大小越大，效果越差。在

<强>这里基于上面的链接

的简单C++示例 ^{pr2}$

和用法：

^{3}$

代码基于VCL（使用第二个链接中描述的位图），我还使用了我的动态列表模板，因此：

List<double> xxx;与double xxx[];相同
xxx.add(5);将5添加到列表的末尾
xxx[7]访问数组元素（安全）
xxx.dat[7]访问数组元素（不安全但快速的直接访问）
xxx.num是数组的实际使用大小
xxx.reset()清除数组并设置xxx.num=0
xxx.allocate(100)为100项预先分配空间

抱歉不是一个python代码编写者，但认为代码足够直接。。。所以我希望你能适应你的环境。在

此处输出：

看起来像是模仿你的。。。代码仍然没有优化，可以进一步改进。。。我认为您应该仔细看看mx,my和{}变量。这些是拓扑索引排序顶点，使你的代码有巨大的加速。。。在

[Edit1]

我更新了A*搜索代码（thx改为Matt Timmermans），因此以下是更新结果：