問題タブ [hamiltonian-cycle]

このサイトの完全加重グラフとハミルトニアン ツアーのトピックについて、ユーザーの 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) を選択するためにこのソリューションを適応させることができるかということです。

私は試験の準備をしており、アルゴリズム コースでは NP の完全性をカバーする必要がありましたが、それらの実際のチュートリアルはなく、試験の「練習問題」の山が与えられました。私は最後を除いてすべてに取り組みましたが、それを解決する方法が本当にわかりません（これまでにインターネットに尋ねると、私が理解できない公開された論文が返されました）。

前の 2 つの質問は、ハミルトン パス問題がクラス NP にあることを示しており、ハミルトン サイクル問題がそれに帰着することを示すことによって、それが NP 完全であることを示していました。

これは、私が前進できないように見える3番目の質問につながります。

グラフの次数制約スパニング ツリーは、一定の k に対して最大次数 k のスパニング ツリーです (ツリーの各頂点は、最大で k 個のエッジに隣接します)。グラフ G に次数が k = 2 で制約されたスパニング ツリーが含まれているかどうかを判断するのがハミルトニアン パス問題です。これは、先ほど示した NP 完全問題です。一般的な k に対して、次数が k で制約される全域木がグラフ G に含まれているかどうかを判断することも NP 完全問題であることを示します。

これに答える私の現在の試みは、次のようなものです。

k = 2 の場合、任意の頂点 V について、頂点 V のみを共有し、ハミルトニアン パスに対して true を返す 2 つの異なるサブグラフにグラフを分割できます。つまり、k=3 の場合、頂点 V があり、グラフをすべてハミルトニアン パスを持つ 3 つの異なるサブグラフに分割できます。

これが正しくないことはわかっていますが、正しい道に沿っていると感じていますが、最終目標に到達する方法がまったくわかりません。どんな助けでも大歓迎です。

これは、グラフ内のハミルトニアン サイクルを見つけるための私のアルゴリズムです。

最初のハミルトニアン サイクルを 1 つ見つけることができます。グラフで見つかったすべての可能なハミルトニアンサイクルを見つけるように適応させることは可能ですか?

入力は非対称行列 (ノード間の一部のリンクは一方向) であり、一部のノードは他のノードへの 2 つまたは 3 つのリンクを持つ場合があります。

ありがとうございました

編集：

明確にするために、アルゴリズムは既に解決策を見つけることができますが、2 番目の解決策を見つけることはできません。読んだところ、バックトラッキングを使用する A* で問題が解決する可能性がありますが、既に持っているものに追加できるかどうかはわかりません。

与えられた無向グラフ G、ハミルトニアン パスとハミルトン サイクルが互いに可約な多項式時間であることを示す必要があります。これが私の還元ですが、これは正しいですか？

サイクルからパスの場合 V に属する頂点 v の場合、頂点 v' を追加し、すべての e(v,u) に対してエッジ e(v' ,u) を追加します。v から v' へのハミルトニアン パスが存在する場合、v のハミルトニアン サイクルが存在します。

頂点 s および t の場合、すべてのエッジ e(t,u) に対してエッジ e(s,u) を追加し (このエッジが存在しない場合)、すべてのエッジ e(s,u) に対して endge を追加します。 (t,u) (このエッジが存在しない場合)。最後にエッジ e(s,t) を追加します。s または t にハミルトニアン サイクルがある場合、s から t へのハミルトニアン パスが存在します。

削減は正しいですか？また、これは、これら 2 つの問題が多項式時間で相互に還元可能であることを示すのに十分ですか?

C#で遺伝的アルゴリズムを使用して巡回セールスマン問題を解決しようとしています。しかし、私のアプリでは、最高の値がゆっくりと変化します。クラシック、貪欲、pmx などのさまざまな Crossing-Over メソッドを試しましたが、欲しいものが得られませんでした。遺伝的アルゴリズムで局所最小値への近似が遅くなる最も効果的な理由は何ですか? クロスオーバー法じゃないですか。

私の CO の方法は正しいと思いますね。私のコード: