無向グラフの場合、この問題はNP完全であることがわかっているため、考えられるすべてのパスをチェックするためにブルートフォースを実行する必要があります。どうすればそれができますか？擬似コードを提案し、そのアルゴリズムの複雑さを教えてください。
最適化があれば、それは素晴らしいことです！
ナイーブなアプローチは、考えられるすべての頂点順列を実行できます。
すべての順列について、{v1, ..., vN}fromv1からv2、次にfromv2からv3などを取得できるかどうかを確認します。可能な場合は、対応するエッジの長さを現在のパスの長さに追加します。そうでない場合は、次の順列に進みます。
そのような道の中で最も長いものがあなたの答えです。
または、再帰を使用してほぼ同じことを行うことができます。
path = 0
bestPath = 0
used = new bool[N] // initialize with falses
for(u = 0; u < N; u++)
Path(u); // build paths starting from u
print bestPath
どこ
Path(u)
used[u] = true
foreach v in neighborhood(u)
if(!used[v])
path += distance(u, v)
bestPath = max(bestPath, path)
Path(v)
path -= distance(u, v)
used[u] = false
時間の複雑さはひどいO(N * N^N)です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加