3

総最小コストで、すべてのノードを通過する加重無向グラフのソリューションを作成する必要があります。開始ノードが定義されていない複数のパスは、最終的に 1 つの交差ノードで合流する必要があります。パスの数、およびパスに含まれるノードの数は、あらかじめ決められていません。ノードは複数回渡すことができます。

私はどのような問題を扱っていますか、解決策として可能なアルゴリズムは? 私はそれが最小スパニングツリーのバリエーションであるべきだと思います（交差点ノードを終点ではなくパスの始点として使用することを意味します）

4

2 に答える 2

0

最小コスト ハミルトニアン サーキット問題と呼ばれます。

詳細については、こちらをご覧ください。

于 2012-12-14T14:57:52.273 に答える
0

それはあなたが探しているツリーであり、問​​題は最小スパニング ツリーです。MST: グラフ内のすべてのノードにまたがるツリーを構築し、ツリーのエッジのコストを最小限に抑えます。多項式の問題です。Prim と Kruskal はそれぞれ、解決のためのよく知られたアルゴリズムを持っています。Kruskal のアルゴリズムについては、 http://en.wikipedia.org/wiki/Kruskal 's_algorithm を参照してください。

注: ツリーがグラフ内のすべてのノードではなく、ノードの特定の適切なサブセットにまたがると想定される場合、問題は NP 完全です。今回は、シュタイナー極小木問題として知られています。

于 2012-12-15T10:08:35.743 に答える