1

このデータ構造は、このA* チュートリアルから取得しました。

public interface IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

public class Path<TNode> : IEnumerable<TNode>
{
    public TNode LastStep { get; private set; }
    public Path<TNode> PreviousSteps { get; private set; }
    public double TotalCost { get; private set; }
    private Path(TNode lastStep, Path<TNode> previousSteps, double totalCost)
    {
        LastStep = lastStep;
        PreviousSteps = previousSteps;
        TotalCost = totalCost;
    }
    public Path(TNode start) : this(start, null, 0) { }
    public Path<TNode> AddStep(TNode step, double stepCost)
    {
        return new Path<TNode>(step, this, TotalCost + stepCost);
    }
    public IEnumerator<TNode> GetEnumerator()
    {
        for (Path<TNode> p = this; p != null; p = p.PreviousSteps)
            yield return p.LastStep;
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

}

簡単なグラフを作成する方法がわかりません。

C# を使用して、次の無向グラフのようなものを追加するにはどうすればよいですか。

代替テキスト

基本的に、ノードを接続する方法を知りたいです。私は自分のデータ構造を持っているので、すでに近隣と距離を決定できます。それをこの投稿されたデータ構造に変換して、AStar アルゴリズムで実行できるようにしたいと思います。

私はもっ​​と次のようなものを探していました:

 Path<EdgeNode> startGraphNode = new Path<EdgeNode>(tempStartNode);
 startGraphNode.AddNeighbor(someOtherNode, distance);
4

2 に答える 2

0

しかし、私はA*用に構築されたこれをどのように使用するのか分かりません。

それが問題です。「A*用に作られたもの」はありません。Pathクラスは、次のように汎用的です。

また、ノードがどのように表示されるか正確にはわからないため、一般的なものにしましょう。

Nodeグラフ内のすべてのノードで同じクラスであれば、好きなクラスを使用できます。コードは、のインターフェイスを使用しないため、クラスがどのように機能するかを気にしません。それが行うのは、保存、つまりsのシーケンス（への参照）だけです。（具体的には、煩わしいリンクリストを作成することでこれを行いますが、パスのコストも増加します。）新しいを作成し、を使用してパスにsを追加すると、をとして使用できます。NodeNodePathsNodePathAddStepNodePathIEnumerable

あなたはあなたNodeのを普通に使い続けることができます。必要なのは、ノードがグラフ内のエッジの「コスト」を表す何らかの方法を備えていることを確認することです。これにより、その情報をに渡すことができますAddStep。

于 2010-12-31T04:49:33.130 に答える
0

これは、グラフを表すために間違った構造を使用しているためです。A* (およびここでのパス) は、グラフ内の 2 つのノード間のパスを見つけるために使用されます。パスは本質的に方向性があり、1 本の線にフラット化できます。たとえば、上記のグラフでは、すべてのノードを通過する可能性のある唯一のパスは 3 で始まり、2 で終了します (後者はパスに 2 回追加されることに注意してください。これが意味を成すかどうかは、問題によって大きく異なります。解決しようとしています。

したがって、基本的にはまずグラフの表現が必要です。次に、そこからアルゴリズムを実行して特定の問題を解決できます。

グラフの最も基本的な形式は、基本的に隣接ノードのメンバー リストを持つノードです。次に、A* を試すことができます。開始ノードと終了ノードを指定し、それらの間のパスを見つけます

于 2010-12-31T02:39:22.873 に答える