完全な無向グラフのハミルトニアンパスとハミルトニアン回路の比較

Question

私は重み付き完全グラフ（Adj。行列）を持っています。私はこのグラフ（巡回セールスマン問題）の最小ハミルトニアン回路を枝と境界を使って見つけるための解法を構築しました。私は今、与えられた開始ノードと終了ノードを持つ最良のハミルトニアンパスを見つけることにこだわりました。与えられた開始ノードと終了ノードがなければ、最良の解決策は、回路のハミルトニアン回路最長エッジです。

私は、与えられた開始ノードと終了ノードでもっともハミルトニアンなパスを見つけるために単にブルートフォースを強制する以外の解決策は考えられませんでした。この問題をどのように進めるかについてのいくつかの指針を提供してください。

Answer 1

与えられた開始ノードと終了ノードは、終了ノードと開始ノードの間の有向エッジがTSPツアーの一部でなければならないという制約に相当します。希望の開始にすべての着信エッジを設定し、開始ノードへの無限の重量に所望の最終ノードから発信されるすべてのエッジ

• セット、エッジを除く
• ：

  だから、あなたは、単にあなたの隣接行列を変更することができます終了ノードからのエッジを除いて無限の重みへのノード

• 開始ノードから終了ノードまでのエッジを無限の重みに設定します（リバースソリューションを取得しないようにします。行列は対称ではない）

これは、実装で使用する分岐方法と非常によく似ています。

Answer 2

与えられた開始ノードと終了ノードの間のエッジ以外のすべてのエッジの重みに大きな定数を追加します。ゼロに設定する必要があります。定数は、N*maxweightとして選択できます。ここで、Nは頂点の数、maxweightは最大エッジの重みです。これにより、与えられたエッジが回路に含まれることが保証されます。