5

私はここでこのアルゴリズムを見つけました。

問題があります。ヒューリスティック関数を設定して渡す方法が理解できないようです。

    static public Path<TNode> AStar<TNode>(TNode start, TNode destination,
        Func<TNode, TNode, double> distance,
        Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
    {
        var closed = new HashSet<TNode>();
        var queue = new PriorityQueue<double, Path<TNode>>();
        queue.Enqueue(0, new Path<TNode>(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 (TNode n in path.LastStep.Neighbours)
            {
                double d = distance(path.LastStep, n);
                var newPath = path.AddStep(n, d);
                queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
            }
        }
        return null;
    }

ご覧のとおり、距離関数と推定関数の2つの関数を受け入れます。

マンハッタンヒューリスティック距離関数を使用して、2つのパラメーターを取得する必要があります。彼のソースを変更して、マンハッタンの見積もりを渡すことができるように、TNodeの2つのパラメーターを受け入れるように変更する必要がありますか？これは、4番目のパラメータが次のようになることを意味します。

Func<TNode, TNode, double> estimate) where TNode : IHasNeighbours<TNode>

推定関数を次のように変更します。

queue.Enqueue(newPath.TotalCost + estimate(n, path.LastStep), newPath);

私のマンハッタン関数は次のとおりです。

    private float manhattanHeuristic(Vector3 newNode, Vector3 end)
    {
        return (Math.Abs(newNode.X - end.X) + Math.Abs(newNode.Y - end.Y));
    }
4

2 に答える 2

8

良い質問。私はその記事が混乱していたことに同意します。私はあなたの質問に対処するためにそれを更新しました。

まず、あなたが尋ねた質問に答えるために：あなたは別の機能をとるために与えられたコードを修正するべきですか？必要に応じて、確かに、しかしあなたは確かにそうする必要はありません。私のアドバイスは、アルゴリズムが必要とする関数であるため、アルゴリズムが必要とする関数を渡すことです。アルゴリズムが必要としない情報を渡すのはなぜですか？

どうすればいいですか？

私が与えるA*アルゴリズムは2つの機能を取ります。

最初の関数は、2つの指定された隣接ノード間の正確な距離を示します。

2番目の関数は、特定のノードと宛先ノードの間の推定距離を示します。

それはあなたが持っていない2番目の機能です。

2つの特定のノード間の推定距離を提供する関数があり、特定のノードと宛先ノード間の推定距離を提供する関数が必要な場合は、その関数を作成するだけです。

Func<Node, Node, double> estimatedDistanceBetweenTwoNodes = whatever;
Func<Node, double> estimatedDistanceToDestination = n=>estimatedDistanceBetweenTwoNodes(n, destination);

これで完了です。これで、必要な機能が得られました。

パラメータの1つを特定の値に固定することによって2パラメータ関数を1パラメータ関数に変換するこの手法は、「部分機能アプリケーション」と呼ばれ、関数型プログラミングでは非常に一般的です。

それはすべて明らかですか？

次に、2番目のはるかに深刻な問題に移ります。私の記事で説明したように、アルゴリズムの正しい動作は、推定関数が保守的であることを前提としています。マンハッタン距離が決して過大評価されないことを保証できますか？それはありそうもないようです。グリッド内のどこかに「対角線」の道路がある場合、マンハッタン距離は2点間の最適距離を過大評価し、A*アルゴリズムはそれを検出しません。2点間の最短距離は定義上過大評価ではないため、ほとんどの人はA *アルゴリズムにユークリッド距離（別名L2ノルム）を使用します。 なぜマンハッタン距離を使用しているのですか？ なぜこれが良い考えだと思うのか、私は非常に混乱しています。

于 2010-12-26T16:01:32.693 に答える
0

はい、コードを変更する必要があります。2つのパラメーターを使用estimateしてメソッドをそこに適合させることはできないためです。TNode

于 2010-12-26T03:00:34.820 に答える