A *寻路缓慢 [英] A* pathfinding slow

问题描述

我目前工作的一个A *搜索算法。该算法也只是解决文本文件的迷宫。我知道，A *算法应该是非常快找到终点。矿似乎需要6秒，找到一个20x20的迷宫没有围墙的路径。它确实找到它只是需要永远做正确的路径终点。

I am currently working on a A* search algorithm. The algorithm would just be solving text file mazes. I know that the A* algorithm is supposed to be very quick in finding the finish. Mine seems to take 6 seconds to find the path in a 20x20 maze with no walls. It does find the finish with the correct path it just takes forever to do so.

如果我知道其中code部分是问题，我只想张贴，但我真的不知道是怎么了。因此，这里是我使用的算法...

If I knew which part of code was the problem I would just post that but I really have no idea what is going wrong. So here is the algorithm that I use...

 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];
    }
}

我知道这code是凌乱的，而不是最有效的方式做的事情，但我想应该还是会更快那么它是什么。任何帮助将大大AP preciated。

I know this code is messy and not the most efficient way to do things but I think it should still be faster then what it is. Any help would be greatly appreciated.

感谢。

推荐答案

openList.erase 为O（n），以及用于循环使用<$ C $开头C>的for（int i = 0; I＆LT; openList.size（）;我++）是O（n ^ 2）由于调用 CheckVisited - 这些被称为每次迭代，使你的整体算法为O（n ^ 3）。 A *的应该的是为O（n log n）的。

openList.erase is O(n), and the for-loop beginning with for(int i=0;i<openList.size();i++) is O(n^2) due to the call to CheckVisited - these are called every iteration, making your overall algorithm O(n^3). A* should be O(n log n).

试着改变 openList 来优先级队列像它应该是，和 visitedList 来一个哈希表。整个为循环就可以被替换为一个离队 - 一定要检查是否 visitedList 。载（节点）的在的入队！

Try changing openList to a priority-queue like it's supposed to be, and visitedList to a hash table. The entire for loop can then be replaced by a dequeue - make sure you check if visitedList.Contains(node) before enqueuing!

另外，也没有必要重新计算 ManHattenDistance 为每个节点每次迭代，因为它不会改变。

Also, there is no need to recalculate the ManHattenDistance for every node every iteration, since it never changes.

这篇关于A *寻路缓慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！