在Python中改进迷宫解决程序的性能-Java 学习之路

其他程序员 . 我的一个项目需要帮助 . 我正在制作迷宫解决方案 . 它读取的图像文件必须是黑白的（黑色像素是墙，白色像素是路径），顶部只有一个像素是迷宫的入口，底部只有一个白色像素，出口 .

代码有三个主要部分：

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

(well, "simple"...

这里是所有以红色绘制的节点：

enter image description here

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

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

3）一旦所有节点链接在一起并 Build 了每个可能的路径，它将从迷宫的入口节点开始，并运行我的A *算法的实现以找出正确的路径，并返回如果它在一个死路 . 如你所见，它毫无困难地解决了迷宫问题 .

enter image description here

所以我的程序有效 . 那有什么问题呢？问题是节点链接部分 . 在小型迷宫上，需要半秒钟 . 但是让迷宫变得更大，那么节点的数量将急剧增加 . 而且由于它遍历节点列表很多时间（每个像素搜索每个节点一次），你可以想象我是否有60万个节点......这需要很长时间 .

所以's what I' m请求帮助：更好，更快的方式将节点链接在一起 . 我在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.")

谢谢你，如果你阅读了所有这些，我知道这不是一个非常精确的问题，但是我花了很多时间来努力完成这项工作，现在我确实坚持了我可以改进它的方法^^ ” .

2 回答

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

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

有很多方法可以让它快得多 .

您可以使用位置作为键将节点放入字典中，因此您可以只查找位置以查找其中的节点 .

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

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

由于这是一个有趣的问题，我用一个简单的BFS编写了一个快速版本 . 我不想破坏你所有的乐趣，所以这里只是BFS部分，这样你就可以直接在图像上看到我的意思了：

#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
    if len(nextlevel) < 1:
        print("Could not find exit!")
        return
    prevlevel = nextlevel
    nextdist += 1
    nextlevel = []
    nextpix = markerPixel(nextdist)

    for prevpos in prevlevel:
        for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
            x = prevpos[0]+dir[0]
            y = prevpos[1]+dir[1]
            if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
                nextlevel.append((x,y))
                #mark it used and distance mod 3
                mazepix[x,y]=nextpix
                if y>=H-1:
                    exitpos=x

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

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

编辑：已经很长一段时间了，OP已经有了他的乐趣，所以这里是完整的python解算器：

from PIL import Image
import math
import sys
import time
import pickle
import os

whitepix = (255,255,255)
blackpix = (0,0,0)
redpix = (255,0,0)
greenpix = (0,255,0)

def markerPixel(distance):
    val=120+(distance%3)*40
    return (val,val,0)

def smallerMarker(pixel):
    return markerPixel(pixel[0]-1)

def isMarker(pixel):
    return pixel[2]==0 and pixel[0]==pixel[1] and pixel[0]>=120

def solve(imagename, outputname, showmarkers):

    maze = Image.open(imagename)
    maze = maze.convert('RGB')
    mazepix = maze.load()
    nodelist = []

    print(maze.size)

    starttime = time.time()

    W = maze.size[0]
    H = maze.size[1]
    entrypos = -1

    # Find the entry
    for i in range(0,W):
        if mazepix[i, 0] == whitepix:
            entrypos=i
            break

    if entrypos < 0:
        print("No entry!")
        return

    #Breadth-first search over the graph
    #We use special colored pixels in the image to mark visited locations and their distance
    nextlevel=[(entrypos,0)]
    nextdist=0
    mazepix[entrypos,0] = markerPixel(nextdist)
    exitpos = -1
    while exitpos<0:
        if len(nextlevel) < 1:
            print("Could not find exit!")
            return
        prevlevel = nextlevel
        nextdist += 1
        nextlevel = []
        nextpix = markerPixel(nextdist)

        for prevpos in prevlevel:
            for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
                x = prevpos[0]+dir[0]
                y = prevpos[1]+dir[1]
                if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
                    nextlevel.append((x,y))
                    #mark it used and distance mod 3
                    mazepix[x,y]=nextpix
                    if y>=H-1:
                        exitpos=x

    #found the exit -- color the path green
    nextpos = (exitpos,H-1)
    while nextpos != None:
        nextpix = smallerMarker(mazepix[nextpos[0],nextpos[1]])
        prevpos = nextpos
        mazepix[nextpos[0],nextpos[1]] = greenpix
        nextpos = None
        #find the next closest position -- all adjacent positions are either
        #1 closer, 1 farther, or the same distance, so distance%3 is enough
        #to distinguish them
        for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
            x = prevpos[0]+dir[0]
            y = prevpos[1]+dir[1]
            if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==nextpix:
                nextpos=(x,y)
                break

    #Erase the marker pixels if desired
    if not showmarkers:
        for y in range(0,H):
            for x in range(0,W):
                if isMarker(mazepix[x,y]):
                    mazepix[x,y]=whitepix

    maze.save(outputname)

solve("maze.gif", "solved.png", False)

回复于 2024-04-26T12:08:37+08:00

你的迷宫只有301x301像素，所以在我看来0.5秒对于解决方案来说太大了 . 当我使用栅格A *方法时：

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

整个解决方案只需 ~1.873ms ，这与您的巨大差异 ~500ms . 粗图A *有更大的开销，所以我很好奇并想测试它所以我编码我的版本（在 C++ 基于相同如上面的链接中的代码），结果是从图像获取的图形占用 ~3ms 并且图形A *占用 ~0.18ms 所以仍然与您的巨大差异（/ - 计算机设置差异） .

So what to check for first?

我不是python编码器，但我没有在你的代码中看到任何图像访问 . 您应该检查您的图像访问是否快速 . 对于使用类似东西的新手而言，这是常见的错误

GetPixel/PutPixel
Pixels[][]

那些通常很慢（根据我在GDI Win32上的经验，比直接像素访问慢1000-10000倍）并且如果纠正会产生巨大的差异 . 有关详情，请参阅：

Display an array of color in C

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

Algorithm

算法的微小变化可以产生巨大的影响 . 在您的情况下，我使用 DIP 边缘检测技术和拓扑排序边缘的加速结构的组合 . 这会将 O(n) 或 O(n^2) 搜索更改为简单的 O(1) 操作 . 这个想法是按照 xy 和 yx 排序迷宫的所有顶点的有序列表 . 如果每个顶点在这样的结构中知道它的索引，它可以很容易地获得它的邻居顶点......

Stack/heap trashing

这减缓了很多事情 . 特别是具有递归功能 . 较大的递归级别和操作数大小通过效果更差 .

Here my simple C++ example based on the link above

//---------------------------------------------------------------------------
//--- A star class ver: 1.00 ------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _A_star_h
#define _A_star_h
//---------------------------------------------------------------------------
#include "list.h"
//---------------------------------------------------------------------------
class A_star_graph
    {
public:
    // variables
    struct _pnt
        {
        int x,y;            // 2D position (image)
        int mx;             // mxy[y][mx] index
        int my;             // mxy[x][my] index
        int pN,pS,pE,pW;    // index of linked point in direction or -1
        int lN,lS,lE,lW;    // distance to linked point in direction or 0 (cost for A*)
        int a;              // value for A*
        _pnt()  {}
        _pnt(_pnt& a)   { *this=a; }
        ~_pnt() {}
        _pnt* operator = (const _pnt *a) { *this=*a; return this; }
        //_pnt* operator = (const _pnt &a) { ...copy... return this; }
        };
    List<_pnt> pnt;         // list of all vertexes
    List< List<int> > mxy,myx;  // xy and yx index sorted pnt[] (indexes of points)
    List<int>  path;        // found path (indexes of points)

    int xs,ys;              // map esolution
    DWORD col_space;        // colors for rendering
    DWORD col_wall ;
    DWORD col_path ;

    // internals
    A_star_graph();
    A_star_graph(A_star_graph& a)   { *this=a; }
    ~A_star_graph(){}
    A_star_graph* operator = (const A_star_graph *a) { *this=*a; return this; }
    //A_star_graph* operator = (const A_star_graph &a) { ...copy... return this; }

    // inteface
    void reset();                                       // clear all
    void ld(Graphics::TBitmap *bmp,DWORD col_wall);     // create graph from bitmap col_wall is 0x00RRGGBB
    void draw(Graphics::TBitmap *bmp);                  // draw map to bitmap for debuging
    void compute(int p0,int p1);                        // compute path from pnt[p0] to pnt[p1] into path[]
    };
//---------------------------------------------------------------------------
A_star_graph::A_star_graph()
    {           //BBGGRR
    col_space=0x00FFFFFF;
    col_wall =0x00000000;
    col_path =0x00FFAA40;
    reset();
    }
//---------------------------------------------------------------------------
void A_star_graph::reset()
    {
    int x,y; xs=0; ys=0; pnt.num=0; path.num=0;
    for (x=0;x<mxy.num;x++) mxy[x].num=0; mxy.num=0;
    for (y=0;y<myx.num;y++) myx[y].num=0; myx.num=0;
    }
//---------------------------------------------------------------------------
void A_star_graph::ld(Graphics::TBitmap *bmp,DWORD col_wall)
    {
    _pnt p,*pp,*qq;
    int i,j,x,y,c[10]={0,0,0,0,0,0,0,0,0,0};
    DWORD *p0,*p1,*p2;
    reset();
    xs=bmp->Width;
    ys=bmp->Height;
    mxy.allocate(xs); mxy.num=xs; for (x=0;x<xs;x++) mxy[x].num=0;
    myx.allocate(ys); myx.num=ys; for (y=0;y<ys;y++) myx[y].num=0;
    if (!ys) return;
    p.pN=-1; p.pS=-1; p.pE=-1; p.pW=-1; p.mx=-1; p.my=-1;
    p0=NULL; p1=NULL; p2=(DWORD*)bmp->ScanLine[0];
    for (p.y=0;p.y<ys;p.y++)
        {
        p0=p1; p1=p2; p2=NULL;
        if (p.y+1<ys) p2=(DWORD*)bmp->ScanLine[p.y+1];
        for (p.x=0;p.x<xs;p.x++)
         if ((p1[p.x]&0x00FFFFFF)!=col_wall)    // ignore wall pixels
            {
            // init connection info
            p.lN=0; p.lS=0; p.lE=0; p.lW=0;
            // init c[] array with not a wall predicates for 4-neighbors
            c[2]=0; c[4]=0; c[5]=1; c[6]=0; c[8]=0;
            if (p0) if ((p0[p.x]&0x00FFFFFF)!=col_wall) c[8]=1;
            if (p2) if ((p2[p.x]&0x00FFFFFF)!=col_wall) c[2]=1;
            if (p1)
                {
                if (p.x-1> 0) if ((p1[p.x-1]&0x00FFFFFF)!=col_wall) c[4]=1;
                if (p.x+1<xs) if ((p1[p.x+1]&0x00FFFFFF)!=col_wall) c[6]=1;
                }
            // detect vertex and its connection
            i=0;
            if (( c[2])&&(!c[8])){ i=1; p.lS=1; }   // L
            if ((!c[2])&&( c[8])){ i=1; p.lN=1; }
            if (( c[4])&&(!c[6])){ i=1; p.lW=1; }
            if ((!c[4])&&( c[6])){ i=1; p.lE=1; }
            j=c[2]+c[4]+c[6]+c[8];
            if (j==3)               // T
                {
                i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
                if (!c[2]) p.lS=0;
                if (!c[8]) p.lN=0;
                if (!c[6]) p.lE=0;
                if (!c[4]) p.lW=0;
                }
            if (j==4)               // +
                {
                i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
                }
            // add point
            if (i)
                {
                p.mx=myx[p.y].num;
                p.my=mxy[p.x].num;
                mxy[p.x].add(pnt.num);
                myx[p.y].add(pnt.num);
                pnt.add(p);
                }
            }
        }
    // find connection between points
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
        {
        if (pp->lE)
            {
            j=myx[pp->y][pp->mx+1]; qq=pnt.dat+j; pp->pE=j; qq->pW=i;
            j=abs(qq->x-pp->x)+abs(qq->y-pp->y);  pp->lE=j; qq->lW=j;
            }
        if (pp->lS)
            {
            j=mxy[pp->x][pp->my+1]; qq=pnt.dat+j; pp->pS=j; qq->pN=i;
            j=abs(qq->x-pp->x)+abs(qq->y-pp->y);  pp->lS=j; qq->lN=j;
            }
        }
    }
//---------------------------------------------------------------------------
void A_star_graph::draw(Graphics::TBitmap *bmp)
    {
    int i;
    _pnt *p0,*p1;
    // init
    bmp->SetSize(xs,ys);
    // clear (walls)
    bmp->Canvas->Pen->Color=TColor(col_wall);
    bmp->Canvas->Brush->Color=TColor(col_wall);
    bmp->Canvas->FillRect(TRect(0,0,xs,ys));
    // space
    bmp->Canvas->Pen->Color=TColor(col_space);
    for (p0=pnt.dat,i=0;i<pnt.num;i++,p0++)
        {
        if (p0->pN>=0){ p1=pnt.dat+p0->pN; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
        if (p0->pS>=0){ p1=pnt.dat+p0->pS; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
        if (p0->pE>=0){ p1=pnt.dat+p0->pE; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
        if (p0->pW>=0){ p1=pnt.dat+p0->pW; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
        }
    // found path
    bmp->Canvas->Pen->Color=TColor(col_path);
    for (i=0;i<path.num;i++)
        {
        p0=pnt.dat+path.dat[i];
        if (!i) bmp->Canvas->MoveTo(p0->x,p0->y);
         else   bmp->Canvas->LineTo(p0->x,p0->y);
        }
    }
//---------------------------------------------------------------------------
void A_star_graph::compute(int p0,int p1)
    {
    _pnt *pp,*qq;
    int i,a,e;
    List<int> upd;  // list of vertexes to update
    // init
    path.num=0;
    if ((p0<0)||(p0>=pnt.num)) return;
    if ((p1<0)||(p1>=pnt.num)) return;
    // clear with max value
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++) pp->a=0x7FFFFFFF;
    // init A* to fill from p1
    upd.allocate(xs+ys); upd.num=0;             // preallocate
    upd.add(p1); pnt[p1].a=0;                   // start from p1
    // iterative A* filling
    for (e=1;(e)&&(upd.num);)                   // loop until hit the start p0 or dead end
        {
        // process/remove last pnt in que
        pp=pnt.dat+upd[upd.num-1]; upd.num--;
        // link exist?                     compute cost    if less        update it                   reached p0?
        i=pp->pN; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lN; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
        i=pp->pS; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lS; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
        i=pp->pE; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lE; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
        i=pp->pW; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lW; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
        }
    // reconstruct path
    e=p0; pp=pnt.dat+e; path.add(e);
    for (;e!=p1;) // loop until path complete
        {
        a=0x7FFFFFFF; e=-1;
        // e = select link with smallest cost
        i=pp->pN; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
        i=pp->pS; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
        i=pp->pE; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
        i=pp->pW; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
        if (e<0) break; // dead end
        pp=pnt.dat+e; path.add(e);
        }
    }
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

和用法：

Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
A_star_graph map;
map.ld(maze,0);
map.compute(0,map.pnt.num-1);
map.draw(maze);

代码基于 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编码器，但认为代码是直截了当的...所以我跳了你没有问题移植/适应你的环境 .

这里输出：

result

看起来它模仿你的...代码仍未优化，可以进一步改进...我认为你应该仔细看看 mx,my 和 mxy[][],myx[][] 变量 . 这些是topologicaly索引排序的顶点，可以实现对代码的巨大加速...

[Edit1]

我更新了A *搜索代码（thx到Matt Timmermans），所以这里有更新的结果：

small

big

回复于 2024-04-26T12:08:37+08:00

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

2 回答

相关问题