0

私は現在、A*検索アルゴリズムに取り組んでいます。アルゴリズムは、テキストファイルの迷路を解決するだけです。私は、A*アルゴリズムがフィニッシュを見つけるのに非常に速いことになっていることを知っています。壁のない20x20の迷路で道を見つけるのに6秒かかるようです。それはそれがそうするのに永遠にかかる正しい道で終わりを見つけます。

コードのどの部分が問題であるかを知っていれば、それを投稿するだけですが、何が問題になっているのか本当にわかりません。これが私が使用するアルゴリズムです...

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

私はこのコードが厄介で、物事を行うための最も効率的な方法ではないことを知っていますが、それでもそれが何であるかよりも速いはずだと思います。どんな助けでも大歓迎です。

ありがとう。

4

4 に答える 4

1

openList.eraseは O(n) であり、for ループの先頭for(int i=0;i<openList.size();i++)は O(n^2)CheckVisitedです。これらは繰り返しごとに呼び出され、アルゴリズム全体が O(n^3) になります。A*はO(n log n) である必要があります。

openList本来あるべきプライオリティ キューとvisitedList、ハッシュ テーブルに変更してみてください。その後、ループ全体forを a に置き換えることができます - キューに入れる前にdequeue確認してください!visitedList.Contains(node)

ManHattenDistanceまた、 for every node は決して変更されないため、反復ごとに再計算する必要はありません。

于 2012-06-07T16:53:40.907 に答える
1

20x20 の迷路には壁がないため、非常に多くのルートがすべて同じ長さです。実際、何兆もの同等のルートがあると見積もっています。それを考えるとそれほど悪くはないように思えます。

もちろん、ヒューリスティックは完璧に見えるので、これまでに知られている最適なルートと正確に同じ長さになるとヒューリスティックに予測されたルートを除外することで、大きなメリットが得られるはずです。(ヒューリスティックが正しい場合、つまり、残りの距離を決して過大評価しない場合、これは安全です)。

于 2012-06-07T15:40:14.153 に答える
1

ここに大きなヒントがあります。

同じセルへの 2 つのパスを見つけた場合は、長い方をいつでも破棄できます。同点の場合は、2 番目のものを捨ててそこにたどり着くことができます。

これを実装すると、他に最適化を行わなくても、検索は許容できる以上に高速になります。

第 2 に、A* アルゴリズムは、現在のセルまでの長さとヒューリスティックを足したものが、現在のセルまでの長さと他のノードのヒューリスティックを足した長さを超える場合にのみバックトラックを行う必要があります。それを実装すると、直接パスを見つけて停止するはずです。これを容易にするために、ベクトルではなく優先キュー (通常はヒープで実装) にパスを格納する必要があります。

于 2012-06-07T16:57:03.040 に答える
0

常に後戻りしていませんか？

A* アルゴリズムは、現在の最適解が以前に訪れた別のルートよりも悪くなるとバックトラックします。あなたの場合、壁がないため、すべてのルートが適切であり、死ぬことはありません（MSaltersが正しく指摘したように、いくつかあります）。一歩を踏み出すと、あなたのルートは、一歩短い他のすべてのルートよりも悪くなります。

もしそうなら、これはあなたのアルゴリズムにかかる時間を説明しているかもしれません.

于 2012-06-07T15:54:11.050 に答える