このデータ構造からグラフを作成するにはどうすればよいですか？

Question

私はこのA* tutorialからこのデータ構造を取っ：

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); 

Answer 1

。 A *（およびここのパス）は、グラフ内の2つのノード間のパスを見つけるために使用されます。パスは、本質的に指向性であり、単一のラインにフラット化することができます。たとえば、上記のグラフでは、すべてのノードを通過する唯一の可能なパスは3から始まり2で終了します（パスが2回追加されるか天気かどうかは、あなたの問題に大きく左右されます解決しようとしている。

をだから、基本的に、あなたが最初にそれらが特定の問題を解決するのに、それから、あなたがアルゴリズムを実行することができ、グラフの表現を必要としています。

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

Answer 2

私はA *用に作られたものをどのように使うのか分かりません。

これは問題です。 「A *のために構築されたもの」はありません。 Pathクラスは、それが言うように、ジェネリックです：

あなたはどんなNodeを使用することができます。

をそして、我々は、ノードがのが一般的なものを作ってみましょう、どのように見えるかを正確に知っていないので、あなたが好きなクラスは、グラフのすべてのノードで同じものです。コードは、Nodeのインタフェースを使用していないため、Nodeクラスの動作についてはには関係ありません。にはNodeのインターフェイスが使用されていません。それはストアPaths、すなわちNodeのシーケンス（の参照）です。 （具体的には、侵入型のリンクリストを作成することでこれを行いますが、パスコストも加算されます）。Pathを新しく作成し、AddStepを使用してNodeをPathに追加してからPathIEnumerableとします。

通常、Nodeは引き続き使用できます。必要なのは、ノードがグラフ内のエッジの「コスト」を表す何らかの方法を持っていることを確認することです。その情報をAddStepに渡すことができます。