0

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.

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

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.

Thanks.

4

4 回答 4

1

您的 20x20 迷宫没有墙壁，因此有许多相同长度的路线。事实上，我估计有数万亿条等效路线。考虑到这一点，它似乎并没有那么糟糕。

当然，由于您的启发式算法看起来很完美，您应该从排除启发式预测的路线与迄今为止已知的最佳路线一样长的路线中获得很大的好处。（如果您的启发式方法正确，这是安全的，即永远不会高估剩余距离）。

于 2012-06-07T15:40:14.153 回答
1

openList.erasefor(int i=0;i<openList.size();i++)是 O(n)，并且由于调用而以 O(n^2)开头的 for 循环CheckVisited- 这些在每次迭代时都被调用，从而使您的整体算法为 O(n^3)。A*应该是 O(n log n)。

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

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

于 2012-06-07T16:53:40.907 回答
1

这是一个很大的提示。

如果你找到两条通向同一个单元格的路径，你总是可以扔掉较长的一条。如果有平局，您可以扔掉第二条以到达那里。

如果你实现了这一点，没有其他优化，搜索将变得非常快。

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

于 2012-06-07T16:57:03.040 回答
0

你不是经常回溯吗？

当当前最佳解决方案变得比另一个先前访问的路线更差时，A* 算法会回溯。在您的情况下，由于没有墙，所有路线都很好并且永不消亡（正如 MSalters 正确指出的那样，其中有几条路线）。当您迈出一步时，您的路线会变得比其他所有短一步的路线都差。

如果这是真的，这可能会解释您的算法所花费的时间。

于 2012-06-07T15:54:11.050 回答