行列NxNがあります。ここで、は無向グラフの頂点とjmatrice[i][j]の間のエッジのコストです。if
私が決定する必要があるのは、行列のすべての頂点を含む最短経路です。
したがって、次のような入力の場合：
0 198 67 368
198 0 131 432
67 131 0 301
368 432 301 0
私はすべての可能なパスを試す必要があり、この場合：
0-->1-->2-->3-->0
長さ998を与える正しいです。
どうすればこれを実装できますか？
1 に答える
3
あなたは、広く研究されている巡回セールスマン問題について説明しています。
解を近似する方法はたくさんありますが、正確な解には確かに指数関数的な実行時間が必要であり、ブルートフォースはそれを解くための1つのオプションです（O (n!)）。
アイデアは、すべての可能な順列を生成し、それぞれを評価し、最小値を見つけることです。
たとえば、
この質問では、すべての順列を生成する方法について説明します。同じ考えがあなたの問題にも当てはまります。
于 2012-12-07T10:50:01.047 に答える