0

2次元平面上にn個の点があり、n <= 12であり、すべての点を含む利用可能な最短経路の距離が必要で、それらのいずれかから始まりますが、閉回路は作成されません

フロイドマーシャル、旅行セールスマン問題、その他のアルゴリズムを試してみましたが成功しませんでした。

問題は私の先生にとっては簡単だと考えられているので、アロラ近似などは必要ないと思いますが、これを解決するための最良のアプローチは何かわかりませんが、おそらくいくつかの動的アルゴリズムなど

for i = 0 to n
    for j = 0 to n
    if path_distance(i,j) < mininum
        set minimum

助けはありますか？

4

3 に答える 3

1

ポイントが 12 個しかないことがわかっていて、すべてのノードを 1 回だけ訪れる最短パスを見つけたい場合は、ノードのすべての可能な順列を試し、それに沿ったパスの長さを計算することで、いつでも力ずくで解を求めることができます。順列。これはまったくうまくスケーリングしませんが、ノード数の上限が固定されている場合は妥当なはずです。

于 2011-03-03T01:34:18.597 に答える
1

これは宿題なので、ヒントだけを提供します。

この種の問題を分解する場合、再帰は非常に便利です。

これまでのルートのリスト、これまでの最適/最小距離、および未訪問のノードのリストを取得する関数を作成できます。未訪問のノードごとに、それをこれまでのルートに追加しようとし、そのルートがこれまでの最適/最小距離よりもまだ短い場合は、新しいルートと未訪問のノードのリストで自分自身を呼び出します。

于 2011-03-09T10:05:10.887 に答える
1

場合に限り、ブルート フォース アルゴリズムの改良版である分岐n <= 12限定アルゴリズムをお勧めします。

于 2011-03-09T08:28:03.110 に答える