3

C# で A* パスファインディングを正常に実装しましたが、非常に遅く、その理由がわかりません。openNodes リストをソートしないようにしましたが、それでも同じです。

マップは 80x80 で、10 ～ 11 個のノードがあります。

ウィキペディアから擬似コードを取得しました

そして、これは私の実装です:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

私が使用しているヒューリスティックは次のとおりです。

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

私は何を間違っていますか？同じコードを見続けるのは丸一日です。

4

6 に答える 6

16

まず、プロファイラーを使用します。ツールを使用して何が遅いかを教えてください。何が遅いのかと驚くことがよくあります。そして、デバッガを使用してください。5 つのノードを含むマップを作成し、コードのすべての行をステップ実行してパスを見つけようとします。予期しないことが起こりましたか？もしそうなら、何が起こっているのかを理解してください。

第二に、パフォーマンスの問題はさておき、正確性の問題もあると思います。マンハッタン距離が合理的なヒューリスティックであると考える理由を説明していただけますか?

(これを読んでいる人でメトリックに慣れていない人のために説明すると、「マンハッタン距離」または「タクシー距離」は、グリッド上に配置された都市に住んでいる場合に移動する必要がある 2 点間の距離です。つまり、北東に 14 マイル進むと、北に 10 マイル、次に東に 10 マイル、合計 20 マイル移動する必要があります。)

A* アルゴリズムでは、2 点間を移動するために必要な実際の距離をヒューリスティックが常に過小評価することが正確である必要があります。グラフに「斜めのショートカット」道路がある場合、マンハッタン距離はそれらのパスの距離を過大評価するため、アルゴリズムは必ずしも最短パスを見つけるとは限りません。

ヒューリスティックとしてユークリッド距離を使用しないのはなぜですか?

ヒューリスティックとして「常にゼロ」を使用してアルゴリズムを試しましたか? それは過小評価であることは保証されています。(そうすると、ダイクストラのアルゴリズムが実装されます。)

第三に、この実装では非常に多くの並べ替えを行っているようです。確かに、優先キューを使用している可能性があります。仕分けよりもずっと安いです。

4 つ目は、私のブログに C# 3 での A* の実装があります。明示または黙示の保証はありません。ご自身の責任で使用してください。

http://blogs.msdn.com/b/ericlippert/archive/tags/astar/

私のコードは非常に簡単です。私の実装のアルゴリズムは次のようになります。

var closed = new HashSet<Node>();
var queue = new PriorityQueue<double, Path<Node>>();
queue.Enqueue(0, new Path<Node>(start));
while (!queue.IsEmpty)
{
    var path = queue.Dequeue();
    if (closed.Contains(path.LastStep)) continue;
    if (path.LastStep.Equals(destination)) return path;
    closed.Add(path.LastStep);
    foreach(Node n in path.LastStep.Neighbours)
    {
        double d = distance(path.LastStep, n);
        var newPath = path.AddStep(n, d);
        queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
    }
}

アイデアは、パスの優先キューを維持することです。つまり、最短距離でこれまでのパスを常に伝えることができるパスのキューです。次に、目的地に到達したかどうかを確認します。もしそうなら、私たちは終わりです。そうでない場合は、目標までの (過小に) 推定された距離に基づいて、一連の新しいパスをキューに入れます。

第 5 に、ウィキペディアの疑似コードは改善される可能性があります。私の実際のコードは多くの点で疑似コードよりも理解しやすいという事実は、疑似コードに詳細が多すぎる可能性があることを示しています。

于 2011-02-01T17:26:55.470 に答える
5

いくつかのメモ：

List<T>最初の要素を削除するために最適化されていません。逆の順序で並べ替えて、最後の要素を取る方がよいでしょう。Stack<T>または、またはを使用しQueue<T>ます。

List.Remove(current)非常に非効率です。削除するインデックスは既にわかっているため、リスト全体で要素を検索しないでください。

新しいノードを正しい場所に挿入してソートを維持openNodesすることは、リスト全体を継続的に再ソートするよりもはるかに高速です。リストの並べ替えをスキップすると、重要な不変条件が削除され、アルゴリズム全体が壊れます。スキップするのではなく、ソートを高速化する必要があります。

あなたが行っている主な操作closedNodesは、プレゼンス テストですclosedNodes.Contains()。そのために最適化されたデータ構造を使用しますSet<T>。または、さらに良いことに、各ノードにクローズド フラグ フィールドを配置し、各パスの開始時にそれらをすべてクリアします。closedNodesこれは、各反復で線形検索を実行するよりも大幅に高速になります。

solutionNodes最初は何も入れないでください。両方mEndともmStart、パスを通過する最後のループ中に追加されます。

neighborNodesリスト全体を一度に必要とすることはないため、のIEnumerable<T>代わりに を使用できます。List<T>を使用foreachすると、インデックスでリストを列挙するよりもわずかに高速になります。

于 2011-02-01T16:22:05.800 に答える
1

quickgraph ライブラリの A* 実装と比較する (または単に利用する) ことができます。

QuickGraph.Algorithms.ShortestPath.AStarShortestPathAlgorithm<TVertex,TEdge>
于 2011-02-01T16:20:49.880 に答える
0

メモリ消費量はどのくらいですか？Red Gate ツールをダウンロードします。パフォーマンス プロファイラーを使用して、最も時間が費やされている場所を確認し、メモリ プロファイラーを使用して、メモリ リークやオブジェクトが十分に迅速に破棄されていないかどうかを判断します。

@Rodrigo が指摘したように、大きなマップを扱うことができます。ネストされたループのパフォーマンスは期待できません。

于 2011-02-01T16:15:54.987 に答える
0

トラバーサル ノードのコストは次のように計算します。

cost = current.G + 10;

しかし、ヒューリスティックの場合、単純な距離があります。ここでも同じ距離を使わないのはなぜですか？現在のノードの距離によっては、ヒューリスティックが低すぎる可能性があります。

間違っているかもしれない別の「詳細」: current.GetNeighborNodes. これはどのように実装されていますか？異なるパス上の同じノードが共有されるように、同じ場所に対して同じノードを返しますか、それとも常に new を使用して新しいノードを割り当てますか?

于 2011-02-01T16:37:18.940 に答える
-1

地形表現にグリッドを使用していますか? もしそうなら、その場合の最善のヒューリスティックは Octile です:

ヒューリスティック コスト = (最小 (x の差、y の差) * 2 の平方根 + 最大 (x の差、y の差) - 最小 (x の差、y の差))

グリッドの場合、これは常に最適です。残念ながら、このヒューリスティックはあまり知られていません。

もう 1 つの役立つヒントは、開いているリストのデータ構造をマップのサイズに合わせて選択することです。マップが比較的小さい場合 (100 x 100)、ソートされていないベクターが最も高速な方法です。要素を削除するには、最後の要素と削除したい要素のイテレータ スワップを実行し、pop_back を呼び出します。マップが大きい場合は、ヒープを使用します。最も安いノードだけを気にするので、他のすべてをソートしても何のメリットもありません。ヒープは、複雑さのログ n を使用して挿入および並べ替えを行います。中規模および大規模のデータ セットには最適ですが、小規模のデータ セットには時間がかかります。

最後に、速度が問題になる場合は、ジャンプ ポイント検索を実装します。平均して、経路探索 A* よりも 20 倍から 30 倍高速であり、メモリのオーバーヘッドもありません (または、研究論文が主張しているように、その証拠は見つかっていません)。基本的に、A* の「隣人を見つける」ステップを「後継者を見つける」に置き換えるので、コードに組み込むのは比較的簡単です。

それが役立つことを願っています。

于 2013-06-25T19:43:07.897 に答える