6

このサイトの完全加重グラフとハミルトニアン ツアーのトピックについて、ユーザーの 1 人から尋ねられ、私の大学の多くのスタッフに尋ねましたが、良い答えが得られませんでした。この質問の重要な部分を次のように変更します。次のとおりです。

問題 A: 完全加重グラフ G が与えられたとき、weights最小加重のハミルトニアン ツアーを見つけます。

問題 B: 完全加重グラフ G と実数 R が与えられた場合、G は最大で R の重みを持つハミルトニアン ツアーを持ちますか?

B を解くマシンがあるとします。そのマシンで問題 A を解くために、(G と実数 R が与えられるたびに) B を何回呼び出すことができますか? M までの G のエッジの合計を想定します。

  1. 数えられない状態があるので、これはできません。

  2. O(|E|)回

  3. O(lg m) 回

  4. A は NP 困難であるため、これは実行できません。

私はこのファイルを読み、2ページ目に彼は次のように書いた:

a) 最適化問題 (厳密な意味で): 最適解を見つける

b) 評価問題: 最適解の値を決定する

c) 範囲問題: 範囲 B が与えられた場合、最適解の値が B より上か下かを判断します。

次の 2 つの段落で

b) を解く際に c) を利用するために、組み合わせ問題の可能な値は通常離散的であり、整数と見なすことができるという事実を使用します。制限された問題 c) を時間 T 以内に解くことができると仮定します。対応する評価問題 b) については、通常、値が整数の特定の範囲 [L, U] 内にあることがアプリオリにわかっています。二分探索を使用して、log | で評価問題を解決します。U - L | 束縛問題 c) への呼び出し、したがって、時間内に T log | U - L |。

そして次に彼は書いた：

例: 重み付きグラフの TSP Kn = (V, E, w: E -> Reals), |V| = n、|E| = n-choose-2。c) を使用して b) を解決します。n 頂点のグラフのツアーまたはハミルトニアン サイクルには、正確に n 個のエッジがあります。したがって、n 個の最長エッジの合計 S は、最適ツアーの長さの上限です。一方、n エッジの m 選択 n サブセットすべての合計は有限の数のセットであり、これらの数のうちの 2 つの最小の非ゼロ差 d がツアーの長さの粒度を定義します。2 つの異なるツアーは、値が同じか、長さが少なくとも d 異なります。したがって、log( S / d) 範囲の問題を計算するバイナリ検索によって、最適なツアーの長さ (値) が決まります。

私の質問は、この方法で (3) を選択するためにこのソリューションを適応させることができるかということです。

4

1 に答える 1

1

B を解くマシンがあるとします。そのマシンで問題 A を解くために、(G と実数 R が与えられるたびに) B を何回呼び出すことができますか? M までの G のエッジの合計を想定します。

O(log M).

ピックしa = 0, b = Mます。

  1. セットR = (a + b) / 2。これでBを解きRます。

  2. 結果はTrue

    次に、重みが最大 のハミルトニアン ツアーがありRます。より厳しい上限のためのものはありますか? 設定b = Rして繰り返し、見つけます (1 に進みます)。

  3. 結果はFalse

    この場合、重みが最大 のハミルトニアン ツアーはありませんR。最小の重みはより大きくなります。設定a = Rして繰り返します (1 に移動)。

これが二分探索アルゴリズムです。

理論的には、このアルゴリズムがすべての実数 (特に無理数) で機能するわけではありませんが、実際には無理数を持つことはできません。いずれにせよ、コンピューターは無理数の近似値しか表現できないため、バイナリ サーチを使用して、アルゴリズムを実行する任意の数の小数に適した近似値を取得できます。

たとえば、エッジの 1 つに値 がある場合pi、数学定数piの桁数は無限であるため、最初はその近似値で解決する必要があります。したがって、使用したアルゴリズムに関係なく、ある程度の精度の問題が発生します。

于 2015-03-15T19:10:36.117 に答える