logo标签列表

如何加速A*算法在大空间尺度下的运行？

performancealgorithma-starnetlogo
6
从http://ccl.northwestern.edu/netlogo/models/community/Astardemo，我使用网络中的节点编写了一个A*算法来定义最小成本路径。代码似乎可以工作，但是在使用大规模空间时速度太慢了。我的景观范围为1000个补丁x 1000个补丁，其中1个补丁= 1个像素。即使我将其减少到400个补丁x 400个补丁，其中1个补丁= 1个像素，它仍然太慢了（我无法将我的景观修改为低于400个补丁x 400个补丁）。以下是代码：
to find-path [ source-node destination-node] 

let search-done? false
let search-path []
let current-node 0
set list-open []
set list-closed []  
let list-links-with-nodes-in-list-closed []
let list-links []

set list-open lput source-node list-open
while [ search-done? != true]
[    
ifelse length list-open != 0
[
  set list-open sort-by [[f] of ?1 < [f] of ?2] list-open 
  set current-node item 0 list-open 
  set list-open remove-item 0 list-open 
  set list-closed lput current-node list-closed
  ask current-node
  [  
    if parent-node != 0[
    set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed 
    ]
    ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)]
    [
      set search-done? true 
    ]
    [        
      ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ]  
      [  
        if not member? self list-open and self != source-node and self != destination-node
        [
          set list-open lput self list-open
          set parent-node current-node
          set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node)
          set g sum (map [ [link-cost] of ? ] list-links)
          set h distance destination-node 
          set f (g + h)
        ]
      ]
    ]
  ]
]

[
  user-message( "A path from the source to the destination does not exist." )
  report []
 ]
]
set search-path lput current-node search-path
let temp first search-path
while [ temp != source-node ]
[
 ask temp
[
  set color red
]
set search-path lput [parent-node] of temp search-path 
set temp [parent-node] of temp 
]
set search-path fput destination-node search-path
set search-path reverse search-path  
print search-path
end

很遗憾，我不知道如何加速这段代码。是否有一种解决方案可以在大空间尺度上快速计算最小成本路径?

非常感谢你的帮助。

4
我完全不懂这种语言，但你在每次迭代中都使用 sort-by 对 list-open 进行排序，我不知道是否会增加额外开销。同时，设置 g 可能是 "当前路径成本 +1"，这可能会给你一点小小的提升。我对语言的了解不够深入，无法提出更多建议，但它具有一些特征，让我感觉像是较慢的语言中常见的。 - Mooing Duck
代码看起来对我来说没问题。如果有任何效率上的错误，我没有发现它们。也许你尝试做的计算量太大了，你需要想出一种使用更少计算量的方法来解决你的问题。如何使用启发式算法，这些算法不一定找到最佳路径，但往往选择合理的路径呢？ - Seth Tisue
5个回答
11

我很好奇，所以我测试了我的A*算法，这是我的结果：

迷宫 1280 x 800 x 32 位像素

A* test

  • 你可以看到它只用了约23毫秒
  • 没有使用多线程（AMD 3.2GHz）
  • C++ 32位应用程序（BDS2006 Turbo C++或者 Borland C++ builder 2006）
  • 我发现最慢的路径大约需要44毫秒（填充几乎整个地图）

我认为这已经足够快了...

这是我的 A* 类的源代码:

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const DWORD A_star_space=0xFFFFFFFF;
const DWORD A_star_wall =0xFFFFFFFE;
//---------------------------------------------------------------------------
class A_star
    {
public:
    // variables
    DWORD **map;        // map[ys][xs]
    int xs,ys;          // map esolution   xs*ys<0xFFFFFFFE !!!
    int *px,*py,ps;     // output points px[ps],py[ps] after compute()

    // internals
    A_star();
    ~A_star();
    void _freemap();                                    // release map memory
    void _freepnt();                                    // release px,py memory

    // inteface
    void resize(int _xs,int _ys);                       // realloc map to new resolution
    void set(Graphics::TBitmap *bmp,DWORD col_wall);    // copy bitmap to map
    void get(Graphics::TBitmap *bmp);                   // draw map to bitmap for debuging
    void compute(int x0,int y0,int x1,int y1);          // compute path from x0,y0 to x1,y1 output to px,py
    };
//---------------------------------------------------------------------------
     A_star::A_star()   { map=NULL; xs=0; ys=0; px=NULL; py=NULL; ps=0; }
     A_star::~A_star()  { _freemap(); _freepnt(); }
void A_star::_freemap() { if (map) delete[] map; map=NULL; xs=0; ys=0; }
void A_star::_freepnt() { if (px) delete[] px; px=NULL; if (py) delete[] py; py=NULL; ps=0; }
//---------------------------------------------------------------------------
void A_star::resize(int _xs,int _ys)
    {
    if ((xs==_xs)&&(ys==_ys)) return;
    _freemap();
    xs=_xs; ys=_ys;
    map=new DWORD*[ys];
    for (int y=0;y<ys;y++)
     map[y]=new DWORD[xs];
    }
//---------------------------------------------------------------------------
void A_star::set(Graphics::TBitmap *bmp,DWORD col_wall)
    {
    int x,y;
    DWORD *p,c;
    resize(bmp->Width,bmp->Height);
    for (y=0;y<ys;y++)
     for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
        {
        c=A_star_space;
        if (p[x]==col_wall) c=A_star_wall;
        map[y][x]=c;
        }
    }
//---------------------------------------------------------------------------
void A_star::get(Graphics::TBitmap *bmp)
    {
    int x,y;
    DWORD *p,c;
    bmp->SetSize(xs,ys);
    for (y=0;y<ys;y++)
     for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
        {
        c=map[y][x];
             if (c==A_star_wall ) c=0x00000000;
        else if (c==A_star_space) c=0x00FFFFFF;
        else                      c=((c>>1)&0x7F)+0x00404040;
        p[x]=c;
        }
    }
//---------------------------------------------------------------------------
void A_star::compute(int x0,int y0,int x1,int y1)
    {
    int x,y,xmin,xmax,ymin,ymax,xx,yy;
    DWORD i,j,e;
    // [clear previous paths]
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
      if (map[y][x]!=A_star_wall)
       map[y][x]=A_star_space;
/*
    // [A* no-optimizatims]
    xmin=x0; xmax=x0; ymin=y0; ymax=y0;
    if (map[y0][x0]==A_star_space)
     for (i=0,j=1,e=1,map[y0][x0]=i;(e)&&(map[y1][x1]==A_star_space);i++,j++)
      for (e=0,y=ymin;y<=ymax;y++)
       for (   x=xmin;x<=xmax;x++)
        if (map[y][x]==i)
        {
        yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymin>yy) ymin=yy; }
        yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymax<yy) ymax=yy; }
        yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmin>xx) xmin=xx; }
        yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmax<xx) xmax=xx; }
        }
*/
    // [A* changed points list]
    // init space for 2 points list
    _freepnt();
    int i0=0,i1=xs*ys,n0=0,n1=0,ii;
    px=new int[i1*2];
    py=new int[i1*2];
    // if start is not on space then stop
    if (map[y0][x0]==A_star_space)
        {
        // init start position to first point list
        px[i0+n0]=x0; py[i0+n0]=y0; n0++; map[y0][x0]=0;
        // search until hit the destination (swap point lists after each iteration and clear the second one)
        for (j=1,e=1;(e)&&(map[y1][x1]==A_star_space);j++,ii=i0,i0=i1,i1=ii,n0=n1,n1=0)
         // test neibours of all points in first list and add valid new points to second one
         for (e=0,ii=i0;ii<i0+n0;ii++)
            {
            x=px[ii]; y=py[ii];
            yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            }
        }
    // [reconstruct path]
    _freepnt();
    if (map[y1][x1]==A_star_space) return;
    if (map[y1][x1]==A_star_wall) return;
    ps=map[y1][x1]+1;
    px=new int[ps];
    py=new int[ps];
    for (i=0;i<ps;i++) { px[i]=x0; py[i]=y0; }
    for (x=x1,y=y1,i=ps-1,j=i-1;i>=0;i--,j--)
        {
        px[i]=x;
        py[i]=y;
        if ((y>   0)&&(map[y-1][x]==j)) { y--; continue; }
        if ((y<ys-1)&&(map[y+1][x]==j)) { y++; continue; }
        if ((x>   1)&&(map[y][x-1]==j)) { x--; continue; }
        if ((x<xs-0)&&(map[y][x+1]==j)) { x++; continue; }
        break;
        }
    }
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

我知道代码有点多，但它是完整的。重要的东西在成员函数compute中，所以搜索[A* changed points list]。未经优化的A*（已注释掉）慢了大约100倍。

代码使用Borland VCL中的位图，因此如果您没有它，请忽略get,set函数并将它们重写为您的输入/输出图形风格。它们只是从bitmap加载map并将计算后的map绘制回bitmap。

用法：

// init
A_star map;
Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
map.set(maze,0); // walls are 0x00000000 (black)
// this can be called repetitive without another init
map.compute(x0,y0,x1,y1); // map.px[map.ps],map.py[map.ps] holds the path
map.get(maze,0); // this is just for drawing the result map back to bitmap for viewing

关于A*的更多信息请参见A星算法中的回溯

如果你从起点和终点同时投射路径，直到路径相交，那么这个过程可以加速至少2倍。但是这需要更大的点列表和稍微不同的路径编码... 加速取决于地图和额外开销（有时甚至会减慢速度）... - Spektre
非常感谢您，Spektre。由于我从未使用过C++语言，我不知道如何编译和执行代码。我尝试使用编译器dev-C++，但是收到了许多错误信息（例如DWORD未命名类型）。感谢您的帮助。 - Marine
@Marine DWORD是32位无符号整数，您可以使用任何整数类型，但如果使用有符号数字，则必须将A_star_space和A_star_wall常量从0xFFFFFFF?更改为0x7FFFFFF?...在您的情况下，我会在源代码开头添加typedef unsigned int DWORD;。此外，您还需要根据您的环境重写get、set函数（我使用来自Borland VCL的位图，因此只需将其更改为您使用的数据类型...）。另外，您可以尝试将此从C++重写为您的语言（我完全不认识它...） - Spektre
2
这个答案如何与问题相关？这有什么意义？ - moooeeeep
@moooeeeep，这是个比较的例子，排除分辨率太大而导致计算速度过慢的可能性。由于原作者缺少有关硬件和运行时间的信息，通过这种方式可以在相对短的时间内完成计算，从而看出速度问题出现在其他方面。 - Spektre
10

TL;DR：在您的节点列表（图形）中只包括重要的补丁（或代理）！

加快搜索速度的一种方法是不要在每个网格空间上进行搜索。A *是一种图形搜索，但似乎大多数编码人员只是将网格中的每个点都倒入图形中。这不是必需的。使用稀疏搜索图，而不是在屏幕上搜索每个点，可以加快速度。

即使在复杂的迷宫中，您也可以通过仅在图形中包括拐角和交叉口来加速。不要将走廊网格添加到开放列表中-向前寻找下一个拐角或交叉口。这就是预处理屏幕/网格/地图以构建搜索图形可以节省后来时间的地方。

正如您可以从我在turtlezero.com上的（相当低效的）A *模型中看到的图像中看到的那样，一种天真的方法会创建许多额外的步骤。在长直廊中创建的任何开放节点都是浪费的：

Sample maze solved with naive a-star

通过从图中消除这些步骤，解决方案的寻找速度可以提高数百倍。
另一种稀疏图技术是使用一个距离行走者越远逐渐变得不那么密集的图。也就是说，在行走者附近详细描述你的搜索空间，在行走者远离的地方则稀疏（节点更少，障碍物描述不够准确）。这在行走者正在穿过地图上的详细地形或向着一个移动目标前进且路径必须重新计算的情况下特别有用。
例如，在交通模拟中，道路可能会变得拥堵或发生事故。同样，在一个代理人在不断变化的景观中追逐另一个代理人的模拟中。在这些情况下，只需要精确绘制接下来的几步即可。到达目的地的一般路径可以是近似的。
实现这个简单的方法是随着路径长度的增加逐渐增加行走者的步长。忽略障碍物或进行快速的线段相交或切线测试。这给行走者一个大致的想法去哪里。
可以每步或定期或遇到障碍物时重新计算改进的路径。
虽然只能节省毫秒级时间，但在即将改变的路径末端浪费的毫秒可以更好地用于为更多行走者提供智能、更好的图形或与家人共度更多时间。

关于稀疏图的一个例子，请参阅Apress出版社的David Wallace Croft所著《高级Java编程》第8章：http://www.apress.com/game-programming/java/9781590591239

他在一个演示坦克游戏中使用了一个不断变稀疏的圆形图，并使用a*算法来驱动敌方坦克。

另一种稀疏图的方法是只将感兴趣的路径点添加到图中。例如，在简单的建筑物校园中规划路线时，只有入口、出口和拐角很重要。建筑物侧面或开放空间中的点并不重要，可以从搜索图中省略。更详细的地图可能需要更多的路径点，比如环绕喷泉或雕像的节点圆圈，或者铺设的路径交叉点。

下面是显示路径点之间路径的图表。

Sample of building corner waypoints for path-search optimization

这是由我在turtlezero.com上使用校园建筑路径图模型生成的：http://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph

它使用简单的NetLogo补丁查询来查找兴趣点，例如外部和内部拐角。我相信一组稍微复杂一些的查询可以处理诸如对角墙之类的事情。但即使没有这样的花哨进一步优化，A *搜索空间也会减少数个数量级。

不幸的是，自从Java 1.7不再允许无符号小程序以来，您无法在网页中运行该模型，除非调整Java安全设置。对此我们深感抱歉。但请阅读说明。

8
A*是两种启发式搜索算法：Dijkstra算法和贪心搜索。Dijkstra算法寻找最短路径，而贪心搜索则寻找最便宜的路径。由于Dijkstra算法不冒险，所以它非常慢。将贪心搜索的效果乘以一个系数，可以使A*更加冒险，从而更快地找到解决方案。例如，如果A*=Dijkstra+Greedy，则更快的A*=Dijkstra+1.1*Greedy。无论你如何优化内存访问或代码，都不能解决问题的错误方法。让A*更贪心，它会专注于寻找解决方案，而不是一个完美的解决方案。注意：
Greedy Search = distance from end
Dijkstra's Algorithm = distance from start

在标准A*算法中，它会一直寻找完美的解决方案，直到遇到障碍物。 这个视频 展示了不同的搜索启发式算法；请注意贪婪搜索可以有多快（跳到2:22查看A*，4:40查看Greedy）。当我第一次使用A*算法时，我自己也遇到了类似的问题，而我上面概述的修改后的A*算法使我的性能呈指数级提高。故事的寓意是：用正确的工具做正确的事情。
3
如果您计划多次重复使用同一张地图，则通常最优的方法是进行某种形式的预处理。实际上，您可以计算出某些公共点之间的最短距离，并将它们作为边添加到图中，这通常有助于 a* 更快地找到解决方案。虽然这种方法更难实现。
例如，在英国地图上为所有高速公路路线执行此操作，因此搜索算法只需查找到高速公路，并从高速公路交汇处到其目的地即可。
1

我无法确定观察到的缓慢速度的实际原因。也许只是由于所使用的编程语言的效率不足而导致的。你如何测量性能？我们如何复制它？

此外，使用的启发式（距离度量）对于探索寻找最优路径的数量有很大影响，从而也影响了算法的效率。理论上，必须使用一种可接受的启发式，即永远不会高估剩余距离的距离度量。在实践中，根据迷宫的复杂程度，对于二维网格迷宫，例如曼哈顿距离，保守选择可能会显着低估剩余距离。因此，在远离目标的迷宫区域进行了大量的探索。这导致了探索程度更像是穷举搜索（例如广度优先搜索），而不是人工智能搜索算法应有的样子。

这可能值得研究。

还请查看我在此处的相关答案：

我已经比较了基本 A-Star 算法使用的不同启发式方法并可视化了结果。您可能会发现它很有趣。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接