無向グラフで最長（重い）のトレイルを見つけるにはどうすればいいですか？

Question

私は都市を加重（距離）でつなぐ米国の空間マップを持っています。私はこの地図の中で最も長い（最も重み付けされた）道を見つけたいと思っています。

• 各エッジは、各ノードが[0、INF）回訪問することができ、0または1回
• を訪問しています。

すべてのノードまたはエッジを訪問する必要はありません。

方法とプロローグリソースの提案は問題ありません。

Answer 1

私は私が正しいだかどうかわからないが、あなたは次のことを試みることができる：

1. グラフがオイラーあるかどうかをチェックすることができます。もしそうなら、問題は多項式時間で行われるオイラー回路を見つけることです。

   そうでなければ、私が間違っていないとNP-難しい最大（おそらく誘発された）オイラーのサブグラフを見つけなければならないので、問題があります。

もちろん、すべての重みが負ではないと仮定しています。