1

私は明らかに木々の間の森が恋しいです...

巡回セールスマンの問題については知っていますが、私のニーズ/説明により適した他のアルゴリズム/問題はありますか? このような数学的記述の助けを借りて、私の問題を説明する必要があります。

既知の始点と終点を持つ最大 5 つのポイントがあります。したがって、その 2 つのポイントの間の 3 つのポイントすべてを訪問する最短の方法を計算する必要があります。Dijkstra および同様のアルゴリズムは、2 点間の最短経路を見つけようとします。または、最短経路を見つけて 2 点間のすべての点を訪問するアルゴリズムはありますか?

4

1 に答える 1

7

あなたはそれを考えすぎています。3 つの中間ノードを通るパスは 6 つ (3*2*1) しかありません。それらをすべてチェックしてください。

より大きなインスタンスの場合、次のように問題をTSPに減らすことができます。

sが開始ノードでtが最終ノードである場合、 と の間に重みゼロのエッジを追加し、とと 1 つおきのノードとの間、および と 1 つおきのノードの間にs無限tに重いエッジを追加します。 st

この問題は NP 困難ですが、非常によく研究されています。調査できる正確なアルゴリズムと近似アルゴリズムは多数あります。

于 2013-09-24T19:23:18.733 に答える