1

隣接ツリーの構築と検索に関するインタビューの質問ですが、以前にそれらを使用したことがないため、どこから始めればよいかわかりません。

次のようなデータを含むファイルがあります。

2 13556 225 235
225 2212 226
2212 8888 2213
8888 144115 72629 141336 8889 146090 129948 167357
144115 160496 163089 144114 144116
...

次のようにフォーマットされています。

<parent node> <child node> [ <child node> [ …] ]

すべてのエッジの長さは 1 です。

次に、2 つのノード間の最短パスを計算する必要があります (2 つのノードは質問で指定されています)。次に、予想される複雑さを big-O 表記で提供する必要があります。

後者はおそらくごまかすことができますが、今まで聞いたことがなく、ウィキペディアは検索機能を大きなOに分解する方法を理解するのにあまり役に立ちませんが、後で心配します. （誰かが共有できる良いリンクを持っていない限り）。

私の関心事は、このデータをモデル化し、最短経路を検索することです。私が言ったように、私は以前にこの種の構造で働いたことがないので、どこから始めればいいのか途方に暮れています. ここで隣接リストに関する別の質問を見つけましたが、要点を完全に見逃していない限り、私が探しているものではないようです。私には、その質問で使用されている構造を満たすために入力データを再編成する必要があるように思えますが、ファイルからデータを読み取っているので、すべてのノードとノードのリストをトラバースする必要があると思いますすでに親を入力しているかどうかを判断しますが、それには長い時間がかかる可能性があります。また、その構造を使用して bfs 検索を作成する方法もわかりません。

そこには検索の例がたくさんあるので、その部分を整理できる可能性がありますが、データファイルからのロードに適し、bfs 検索に適したデータモデルを開始するための助けがあれば (または、そこにあるより良い検索オプション、私に教えてください）、非常に役立ちます。

4

1 に答える 1

1

HashTable<int, List<int>>このデータを(Dictionary) (Links) に格納したいでしょう。キーは int (NodeID) で、値はList<int>です。これらは、キーであるノードからの可能な宛先です。

2 つの NodeID を格納する別のHashTable<int, int>(ShortestPathLastStep) が必要です。これは、特定のノードに到達するための最短パスの最後のステップを表します。これは、最短パスを再生できるようにするために必要です。

BFS (幅優先検索) を実行するには、Queue<int>(bfsQueue) を使用します。開始ノード (質問で指定) をキューにプッシュします。次のアルゴリズムを実行します

-- currentNodeID = pop bfsQueue
---- children = Links[NodeID]
------ foreach (childNodeID in children)
--------- if (childNodeID == destinationNodeID)
----------- exit and playback shortest path
----------if (!ShortestPathLastStep.contains(childNodeID))
------------ ShortestPathLastStep.Add(childNodeID, currentNodeID);
----------bfsQueue.Push(childNodeID);
----------goto first line

このソリューションでは、任意の 2 つのノード間の移動が一定のコストであると想定しています。目的地に最初に到着したときに最短のパスをたどることになるため、BFS には理想的です (リンクが可変長の場合は当てはまりません)。リンクの長さが一定でない場合は、ShortestPathLastStep 値を上書きすることを決定するときにさらにロジックを追加する必要があります。キューが空になるまで終了できず、ノードをキューにプッシュするのは、ノードに行ったことがない (短いパス リストには存在しません) または、ノードに到達するためのこの新しい方法が、最後に到達する方法よりも短いことを発見しました (ここで、ノードの最短距離を再計算する必要があります)。このノードからアクセスできます)。

于 2013-04-02T21:54:27.030 に答える