3

無向で重みのないグラフのノードの特定のサブセットがあります。これらすべてのノード間にパスがあるかどうかを判断しようとしています。ある場合、ノードのサブセットにないノードが最も少ない最短パスは何ですか。

これを達成するために最小スパニング ツリー アルゴリズムを変更する方法を考えてみましたが、これまでのところ実行可能な解決策は思いつきませんでした。

これを行う良い方法はありますか、またはこれは既知のアルゴリズムの説明ですか?

4

6 に答える 6

0

ダイクストラのアルゴリズムまたは幅優先探索を使用します。

于 2012-10-12T01:21:09.557 に答える
0

ダイクストラの最短パス アルゴリズムを使用する必要があります。まず、グラフ内のすべてのエッジに重み (または距離) を割り当てる必要があります。サブセットにない 2 つのノードを接続するすべてのエッジには、重み 1 を指定する必要があります。サブセットの 1 つまたは 2 つのノードを接続するすべてのエッジには、無限を指定する必要があります。重さ。次に、結果のグラフでダイクストラのアルゴリズムを実行する必要があります。このアルゴリズムは、グラフのすべてのエッジを調べます。

また、 A* (A-star) アルゴリズムを使用することもできます。

更新: 最初はこの問題がわかりません。@amit が言うように、これは NP 困難な問題であり、HCP と TSP の組み合わせです。おそらく、ある種の確率的探索アルゴリズムは、これを多項式時間で高い確率で解決できます。

于 2012-10-12T07:54:02.847 に答える
0

For someone who doesn't really have a background in graph theory, I have tackled this problem and found that in an unweighted, undirected graph the easiest method is Depth First Search. Implementations of algorithms such as Dijkstra's often take a weighted solution and input an arbitrary value for the weight.

The solution I found to work I traversed nodes in using DFS and log every successful journey, then it's simply a case of returning the shortest successful journey.

Here's the file that does the heavy lifting: Depth First Search Algorithm

于 2016-05-31T14:57:41.117 に答える
0

最短パスを表示するだけでなく、すべてのノードが接続されているかどうかも確認できる Graph/Node/Connection クラスを作成しました。

var allNodesAreConnected = StartNode.AllNodes.All(n => n.IsConnectedToStartNode);

または、接続されていないノードを知りたい場合は、少し変更します。

var anotConnectedNodes = StartNode.AllNodes.Where(n => !n.IsConnectedToStartNode);

この投稿のその他の例と完全なコード: 独自のナビゲーション システムを作成する (Graph、Node、および Connection クラスを使用)

于 2014-03-05T12:36:30.307 に答える