0

情報: 100 ノードの配列 [ 0 .. 99 ] があります。各ノードは、任意の数のリンクされたノードを持つことができます。

eg1, 0 は 5、10、15、20 にリンクします。eg2, 1 は 30、40、50 にリンクします。eg3 など。

100 個のノードすべてに少なくとも 1 つのリンクされたノードがあり、ノードは誰がそれらにリンクしているかを知りません。

質問: START と END が指定されている場合、最短のリンク パスを見つけるにはどうすればよいですか。

例えば。START=5、END=80、リンクパス(例) : [5]->10->24->36->[80]?

私は Pascal や PHP を使用していますが、探しているものを理解することは [コードも役立ちます]。

4

5 に答える 5

2

多数の読み取り/アルゴリズム: 最短経路問題。事実上、すべてのエッジ (「リンク」と呼んだように) を同じ重みで持つだけです。

于 2009-02-18T19:07:34.773 に答える
1

開始ノードから始めて幅優先トラバーサルを実行し、終了ノードが見つかったらすぐに終了します。

于 2009-02-18T19:10:45.983 に答える
1

これにはサイクルがありますか？つまり、DAGですか？

サイクルがない場合:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {   
       //If this is the node you are looking for...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the end node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       List<Node> bestPath = null;

       foreach(Node child in startNode.Children)
       {             
          //get the shortest path from this child
          List<Node> childPath = GetShortestPath(child, endNode);
          if (childPath != null &&
             ( bestPath == null || childPath.Count < bestPath.Count))
          { 
              bestPath = childPath;
          }
       }

       bestPath.Insert(0, startNode);
       return bestPath;
    }

[編集: サイクルの例を追加] サイクルが存在する可能性がある場合:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {
        List<Node> nodesToExclude = new List<Node>();
        return GetShortestPath(startNode, endNOde, nodesToExclude);
   }

   List<Node> GetShortestPath(Node startNode, Node endNode, List<Node> nodesToExclude)
   {   
       nodesToExclude.Add(startNode);

       List<Node> bestPath = null;

       //If this is end node...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the child node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       foreach(Node child in startNode.Children)
       {
          if (!nodesToExclude.Contains(child))
          {
              //get the shortest path from this child
              List<Node> childPath = GetShortestPath(child, endNode);
              if (childPath != null &&
                 ( bestPath == null || childPath.Count < bestPath.Count))
              { 
                  bestPath = childPath;
              }
          }
       }

       nodesToExclude.Remove(startNode);
       bestPath.Insert(0, child);

       return bestPath;
    }
于 2009-02-18T19:26:00.783 に答える
1

2 つの構造: セットとリスト。

セットには、すでに訪れたノードを保存します。これにより、サイクルをたどることができなくなります。

このリストは、(1) ノード、および (2) ノードを見つけたノードへのポインタを含むオブジェクトのリストです。

開始ノードから始めて、それをセットに追加し、null 後方参照を使用してリストに追加し、リスト内のインデックス 0 (開始ノード) への後方参照を使用して、到達できるすべてのノードをリストに追加します。 .

その後、リスト内の各要素に対して、最後に到達するまで、次の操作を行います。

  1. セット内にある場合は、スキップして (既にアクセス済み)、リスト内の次の項目に移動します。
  2. それ以外の場合は、セットに追加し、リストの最後に「見ている」インデックスへの後方参照を使用して、到達できるすべてのノードをリストに追加します。次に、リスト内の次のインデックスに移動して繰り返します。

任意の時点で終了ノードに到達した場合 (リストにアクセスするのではなく、リストに追加するのが最適です)、開始ノードへの後方参照を追跡し、パスを逆にします。

例：

ノード 0 から 3 を指定すると、
node0 --> node1
node0 --> node2
node1 --> node2
node2 --> node3
で、node0 は START で node3 は END です。

セット = {}
リスト = []

ステップ 1 - START を追加:

SET = {node0}
LIST = [[node0, null]]

ステップ 2 - リストのインデックス 0 で、到達可能なノードを追加します。

SET = {node0, node1, node2}
LIST = [ [node0, null] , [node1, 0], [node2, 0]]

ステップ 3 - LIST のインデックス 1 で、到達可能なノードを追加します。

node2 はすでに SET に含まれています。LIST への到達可能なノードの追加をスキップします。
SET = {node0, node1, node2}
LIST = [[node0, null], [node1, 0] , [node2, 0]]

ステップ 4 - LIST のインデックス 2 で、到達可能なノードを追加します。

SET = {node0, node1, node2, node3}
LIST = [[node0, null], [node1, 0], [node2, 0] , [node3, 2]]

ステップ 5 - END に到達し、バックトラックします。

LIST に挿入された END ノード (node3) には、リスト内のインデックス 2 (node2) への後方参照があります。これには、リスト内のインデックス 0、つまり node0 (START) への後方参照があります。これを逆にすると、node0 --> node2 --> node3 の最短パスが得られます。

于 2009-02-18T19:35:08.250 に答える
0

これはツリー/グラフですか、それともフォレストですか? フォレストの場合、パスは常に定義されているとは限りません。これがツリー/グラフの場合は、幅優先検索を使用してみてください。

このように考えてみてください。たとえば、近所でかわいいひよこを見つけるステルス ミッションに出ているとします。自分の家からスタートし、それを START としてマークします。次に、最も近い隣人をノックしに行きますよね？それで、まさにそれを行います-開始に接続されているすべてのノードをキューにプッシュします。ここで、このキュー内のすべてのノードに対して近隣検索を繰り返します。そして、あなたがあなたの女の子を手に入れるまで、これを続けてください、えーと、END.

于 2009-02-18T19:09:07.813 に答える