有向グラフでは、エッジの重みの平均が最も低いサイクルを探します。たとえば、長さ 2 の 1 から 2 へのパスと長さ 4 の 2 から 1 へのパスを持つノード 1 と 2 を持つグラフの最小平均サイクルは 3 になります。
複雑な方法 (Karp) を探しているのではなく、プルーニング ソリューションを使用した単純なバックトラッキングを探しています。説明は、「現在の実行中の平均が、見つかった最良の平均重量サイクル コストよりも大きい場合、重要な剪定を伴うバックトラックで解決可能」と示されています。
しかし、なぜこの方法が機能するのでしょうか。サイクルの途中で、重みが見つかった最良の平均よりも大きい場合、重みのエッジが小さいと、現在のサイクルが見つかった最良の平均よりも低くなる状況に到達する可能性はありませんか?
編集: ここにサンプルの問題があります: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031
与えられたグラフの最適解を、平均辺の重み X を持つサイクルにします。
のようなエッジを持ついくつかの最適なサイクルがe_1ありe_2ます。e_navg(e_i) = X
私の証明のために、私はすべてのインデックスをモジュロ n と仮定しe_(n + 1)ますe_1。
私たちのヒューリスティックがこの解を見つけることができないとしましょう。つまり、各i(最初に取得したエッジが何であれ) に対して、シーケンス内のエッジの平均重み...が X より大きい(これまでに からまでjのすべてのエッジをたどった) ようなものが存在します。 (ヒューリスティックはこのソリューションを削除します)。ije_ie_j
次に、平均辺の重みが X に等しくなり得ないことを示すことができます。ヒューリスティックによって枝刈りされていない最長の連続部分列を取ります (各要素の平均辺の重みが X より大きくない)。少なくとも 1 つe_i <= X、そのようなサブシーケンスが存在します。e_kそのようなサブシーケンスの最初の要素には、pそのようなものがありavg(e_k ... e_p) > Xます。そのような を最初に取りpます。次にk' = p + 1、別の を取得してみましょうp'。再びイニシャルに到達するまで、このプロセスを繰り返しますk。Finalpは initialkを超えることはありません。これは、 final サブシーケンスに initial が含まれていることを意味します。[e_k, e_p - 1]これは、 の構築と矛盾しますe_k。これで、シーケンスe_1...e_nは重複しないサブシーケンスによって完全に覆われましたe_k ... e_p。e_k'...e_p'など、それぞれが X より大きい平均エッジ ウェイトを持っています。したがって、矛盾がありavg(e_i) = Xます。
あなたの質問について：
サイクルの途中で、重みが見つかった最良の平均よりも大きい場合、重みのエッジが小さいと、現在のサイクルが見つかった最良の平均よりも低くなる状況に到達する可能性はありませんか?
もちろん。しかし、このソリューションは安全に刈り込むことができます。後で、刈り込まれない別のエッジから始まる同じサイクルを発見するからです。私の証明は、グラフのすべての可能なサイクルを考慮すれば、遅かれ早かれ最適なサイクルが見つかることを示しています。