2

1<=n<=1000 の都市があります。都市番号 1 で始まり、都市番号 1 で終わるすべての都市 (すべての都市は 1 回だけ訪れることができます) を結ぶパスを見つける必要があります。このパスでは、2 つの都市間の最大長はできるだけ短くする必要があります。

例えば：

ここに画像の説明を入力

入力：

coordinates of cities

出力：

5 1 3 //longest connection is 5 and it is between cities 1 and 3
1 3 6 4 5 2 1 //path
4

2 に答える 2

2

以下は、単純な貪欲なアルゴリズムよりも平均してより良い結果が得られる近似アルゴリズムです。

  1. グラフが完全であると考えてください。頂点のすべてのペアの間にn(n-1)/2エッジの合計があります。
  2. 重み/距離の降順でエッジを並べ替えます。
  3. 最高距離のエッジから最低距離のエッジまで反復し、そのエッジを削除した後、両方の端点がまだ ceil(n/2) 以上の次数を持っている場合は削除します (ハミルトニアン サイクルが存在することを保証するためのディラックの定理)。オーレの定理のようなより強力な結果を使用して、さらに多くのエッジをトリミングすることもできますが、計算の複雑さが増します。
  4. 残りのグラフでは、欲張りアルゴリズムを使用してハミルトニアン サイクルを見つけます。貪欲なアルゴリズムは基本的に 1 から始まり、まだサイクルの一部を形成していないノードまでの距離が最も小さいエッジを選択し続けます。したがって、あなたの例では、最初に 1 -> 2、次に 2->4、次に 4->5 などを選択します。最後に選択した頂点には、1 に戻るパスがあります。

ステップ 4 で与えられた貪欲なアルゴリズムを入力グラフに直接使用することもできますが、一般に、前処理ステップ 1 ～ 3 により、ほとんどのグラフで結果が大幅に改善されます。

于 2013-01-22T18:05:08.530 に答える
0

合計ではなく 2 つの都市間の最大長を最小化する必要があることを除いて、 TSPに似ています (おそらく根本的に異なるものになります)。

私の考えは次のようなものです：

create edges between each pair of cities
while (true)
  next = nextLongestEdge
  if (graph.canRemove(next)) // this function may be somewhat complicated,
                             // note that it must at the very least check that every node has at least 2 edges
    graph.remove(next)
  else
    return any path starting and ending at 1 from the remaining edges
于 2013-01-22T15:14:58.477 に答える