如何加快在大空间尺度A *算法？如何加快在大空间尺度A *算法？(How to speed up A

从http://ccl.northwestern.edu/netlogo/models/community/Astardemo ，我通过使用节点的网络中，以限定最小代价路径编码的A *算法。 该代码似乎工作，但它实在太慢，当我用它的大空间scales.My景观有1000个补丁×1000级的补丁与补丁1 = 1个像素的程度。 即使我减少在400个补丁×400级的补丁与补丁1 = 1个像素，这是又太慢（我不能修改低于400个补丁×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

不幸的是，我不知道如何加快这个代码。 有没有在大空间尺度上快速地计算成本最低的路径的解决方案吗？

非常感谢您的帮助。

Answer 1:

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

迷宫1280个* 800×32个像素

• 你可以看到它了〜23MS
• 没有多线程（AMD 3.2GHz的）
• C ++ 32位应用程序（BDS2006的Turbo C ++或Borland的C ++ Builder的2006年，如果你喜欢）
• 我发现最慢的路径是〜44ms（几乎填满整个地图）

我认为这是足够快...

这里是源矿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* （REM-ED）为约100倍慢。

代码中使用位图从Borland的VCL所以如果你没有它忽略功能get,set并重写你的输入/输出GFX风格。 他们只是加载map从bitmap和绘制计算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

Answer 2:

A *是二启发式; Djikstra的算法和贪婪搜索。 Djikstra的算法搜索的最短路径。 贪婪搜索寻找最廉价的路径。 Djikstra的算法是非常缓慢的，因为它不承担风险。 乘贪婪搜索的效果承担更大的风险。

例如，如果A* = Djikstra + Greedy ，然后更快的A* = Djikstra + 1.1 * Greedy 。 不管你多么优化你的内存访问或你的代码，它不会修复坏的方法来解决这个问题。 让你的A *更贪婪，将重点放在寻找解决方案，而不是一个完美的解决方案。

注意：

Greedy Search = distance from end
Djikstra's Algorithm = distance from start

在标准的A *，它还将努力直到达到一个障碍完善的解决方案。 该视频显示在行动不同的搜索启发式; 注意如何快速贪婪搜索可以是（跳到2:22为A *，4:40贪婪）。 我自己也有类似的问题，当我第一次开始与A *和修改后的A *我在上面勾勒出成倍提高自己的表现。 故事的道德启示; 使用了合适的工具。

Answer 3:

TL; DR：包括在你的节点列表（图）只有补丁（或代理人）是重要的！

加快速度的一个方法是每一个网格空间不超过搜索。 A *是一个图搜索，但似乎最喜欢的程序员只转储在网格进图中每个点。 这不是必需的。 使用稀疏搜索图，而不是在屏幕上寻找每一个点，可以加快速度。

即使在复杂的迷宫，你可以只包括图中的弯道和路口加快。 不要走廊网格添加到开放列表 - 寻求提前找下一个弯道或结。 这是预处理所述屏幕/网格/地图构建搜索图稍后可以节省时间。

正如你可以从我的（相当低效）A *在turtlezero.com模型此图像中看到，一个天真的做法创造了很多额外的步骤。 在长直走廊建立的任何公开的节点被浪费：

通过消除从图中这些步骤，可以找到解决办法快几百倍。

另一个稀疏图技术是使用的曲线图是从助行器逐渐不太致密的进一步。 也就是说，使从助走附近的沃克详细的搜索空间，以及稀疏（更少的节点，不太准确的有关障碍）。 这是特别有用，其中所述助行器通过详细的地形移动地图即改变或朝向目标正在移动并且路由必须被重新计算反正上。

例如，在交通仿真地方道路可能会变得四通八达，或发生意外事故。 同样，模拟其中一个代理追求另一个代理在不断变化的环境。 在这种情况下，只需要准确地绘制在接下来的几个步骤。 到目的地的路线一般可近似。

实现这一点的一种简单的方法就是逐步提高行人的步长作为路径变长。 无视障碍或做一个快速线交点或切试验。 这给了步行者的哪里去了一个大致的了解。

一种改进的路径可以与每个步骤被​​重新计算，或周期性地，或遇到障碍物时。

它可能只毫秒保存，但毫秒浪费在路的即将结束的变化可能是更加步行者，或更好的图形，或更多的时间与家人更好地利用提供的大脑。

对于不同密度的稀疏图的示例，请参阅从A按大卫·华莱士克罗夫特高级Java编程第8章： http://www.apress.com/game-programming/java/9781590591239

他使用的演示坦克游戏越来越稀疏与A *算法驾驶敌人的坦克的圆形图。

另一种稀疏图的方法是填充的利息只有中间点的图表。 例如，绘制整个建筑，只有出入口，一个简单的校园路线，和角落是很重要的。 沿建筑物的侧面或在开放空间中的点之间并不重要，并且可以从搜索图被省略。 更详细的地图，可能需要更多的中间点 - 例如绕喷泉雕像或，或铺的路相交节点的圆。

这里的表示路点之间的路径的图。

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

它采用简单的NetLogo补丁查询找到兴趣点，如外部和内部的角落。 我敢肯定有些更复杂的查询集合可以处理像角壁。 但是，即使没有这样花哨的进一步优化，将A *搜索空间将由数量级的减少。

不幸的是，因为现在的Java 1.7不会允许未签名的小程序，你不能没有调整Java安全性设置运行在网页中的模型。 对于那个很抱歉。 但阅读说明。

Answer 4:

如果你计划在同一地图中多次重复使用，某种形式的预处理通常是最佳的。 实际上，你的工作出一些常见的两点之间的最短距离，并把它们添加到图表的边缘，这通常会帮助*更快地找到解决方案。 虽然它更加难以实施。

例如，你可以在地图上，英国的所有高速公路路线做到这一点，所以搜索算法只需要找到高速公路的路线，并从高速公路路口到它的目的地。

Answer 5:

我不能告诉观察slowlyness的真正原因可能是什么。 也许这只是被手头的编程语言强加在效率不足所致。 你是如何衡量你的表现？ 我们怎样才能重现？

除此之外，所使用的试探法（距离度量）具有上，以便找到最佳路径进行并因此也影响算法的所感知效率勘探的量有很大的影响。

从理论上讲，你必须用启发的，那就是，一个从来没有高估的剩余距离。 在实践中，这取决于迷宫的复杂，对于2D网格迷宫保守的选择，像曼哈顿距离，可能显著低估剩下的距离。 因此大量的探索是在迷宫区域远离目标的完成。 这导致勘探程度的类似于更愿意认为穷举搜索（例如，广度优先搜索），比什么人会从一位知情搜索算法的期望。

这可能是东西看看。

也看看我的相关答案在这里：

• https://stackoverflow.com/a/16656993/1025391

在那里，我已经比较了基本的A星算法中使用不同的启发式检测和可视化的结果。 你会觉得很有趣。

文章来源: How to speed up A* algorithm at large spatial scales?