A*寻路速度慢

Question

我目前正在研究一个A*搜索算法。该算法将只是解决文本文件迷宫。我知道A*算法应该可以非常快地找到终点。我的似乎需要6秒才能在没有围墙的20x20迷宫中找到路径。它确实找到了具有正确路径的终点，只是这样做需要花费很长的时间。

如果我知道代码的哪一部分是问题所在，我会直接把它发布出来，但我真的不知道哪里出了问题。所以这是我使用的算法。

 while(!openList.empty()) {  
    visitedList.push_back(openList[index]);
    openList.erase(openList.begin() + index);

    if(currentCell->x_coor == goalCell->x_coor && currentCell->y_coor == goalCell->y_coor)          
    }
        FindBestPath(currentCell);
        break;
    }

    if(map[currentCell->x_coor+1][currentCell->y_coor] != wall)
    {
    openList.push_back(new SearchCell(currentCell->x_coor+1,currentCell->y_coor,currentCell));
    }
    if(map[currentCell->x_coor-1][currentCell->y_coor] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor-1,currentCell->y_coor,currentCell));
    }
    if(map[currentCell->x_coor][currentCell->y_coor+1] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor+1,currentCell));
    }
    if(map[currentCell->x_coor][currentCell->y_coor-1] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor-1,currentCell));
    }

    for(int i=0;i<openList.size();i++) {
        openList[i]->G = openList[i]->parent->G + 1;
        openList[i]->H = openList[i]->ManHattenDistance(goalCell);
    }

    float bestF = 999999;
    index = -1;

    for(int i=0;i<openList.size();i++) {
        if(openList[i]->GetF() < bestF) {
            for(int n=0;n<visitedList.size();n++) {
                if(CheckVisited(openList[i])) {
                    bestF = openList[i]->GetF();
                    index = i;
                }
            }
        }
    }
    if(index >= 0) {
        currentCell = openList[index];
    }
}

我知道这段代码很乱，也不是最有效的方式，但我认为它仍然应该比它本身更快。任何帮助都将不胜感激。

谢谢。

Answer 1

你的20x20迷宫没有围墙，因此许多许多路线都是相同的长度。事实上，我估计有数万亿条等同的路由。当你考虑到这一点时，它看起来并不是那么糟糕。

当然，由于你的启发式看起来很完美，你应该从排除那些启发式预测的与目前已知的最佳路线一样长的路线中获得很大的好处。(这是安全的，如果您的启发式是正确的，即永远不会高估剩余的距离)。

Answer 2

openList.erase是O(n)，而以for(int i=0;i<openList.size();i++)开头的for循环是O(n^2)，这是由于对CheckVisited的调用-每次迭代都会调用这些循环，从而使整个算法为O(n^3)。A*应为O(n log n)。

尝试将openList改为优先级队列，并将visitedList改为哈希表。然后可以用dequeue替换整个for循环-确保在入队前检查是否为visitedList.Contains(node)！

此外，不需要在每次迭代中重新计算每个节点的ManHattenDistance，因为它永远不会改变。

Answer 3

这里有一个很大的提示。

如果你找到两条到同一单元格的路径，你总是可以去掉更长的那条。如果是平局，你可以扔掉第二个去那里。

如果你在没有其他优化的情况下实现这一点，搜索速度将变得非常快。

其次，A*算法应该只在到当前单元格的长度加上启发式的长度超过、到当前单元格的长度加上任何其他节点的启发式长度时才需要回溯。如果你实现了它，那么它应该直接找到一条路径并停止。为了便于实现，您需要将路径存储在优先级队列(通常使用堆实现)中，而不是向量中。