アルゴリズム このアルゴリズムへの入力は、数値の集合S とパラメータkです。必要な出力は、 Sを k 個のサブセットに分割し、各サブセット内の合計が可能な限り等しくなるようにすることです。アルゴリズムの主な手順は次のとおりです。
数字を大きい順から小さい順に並べなさい。 最大値と2番目に大きい数値を、それらの差に置き換えます。 2つ以上の数字が残っている場合は、手順1に戻ります。 バックトラッキング を用いて、分割を計算します。
双方向分割 k = 2の場合、メインステップ (2) は次のように動作します。
S の中で最大の 2 つの数を取り出し、それらをS から削除し、それらの差を挿入します (これは、これらの数をそれぞれ異なる部分集合に入れるという決定を表します)。この手順を繰り返して、最終的に1つの数値が残るまで続けます。この1つの数値が、2つの部分集合の合計値の差となります。 例えば、S = {8,7,6,5,4} の場合、最大の 2 つの数 {8,7} を取り出し、差 8-7=1 を挿入すると、結果として得られる差集合は {6,5,4,1} になります。この手順を繰り返すと、{4,1,1}、{3,1}、{2} となります。
ステップ 3 では、バックトラックによってパーティション内の部分集合を構築します。最後のステップは {2},{} に対応します。次に、一方のセットでは 2 が 3 に、もう一方のセットでは 1 に置き換えられます。{3},{1}、次に {4},{1,1}、次に {4,5}, {1,6}、次に {4,7,5}, {8,6} となり、和の差は確かに 2 です。
このアルゴリズムの実行時間計算量は、ステップ 1 (ソート) によって支配され、O( n log n ) の時間がかかります。
この分割は最適ではないことに注意してください。分割{8,7}、{6,5,4}では、合計差は0です。しかし、これが「良い」分割であるという証拠があります。
数値が[0,1]の範囲で一様に分布している場合、2つの合計の期待差はn − Θ （ ログ （ n ） ） ） {\displaystyle n^{-\Theta (\log(n)))}} 1 + n − Θ （ ログ （ n ） ） ） {\displaystyle 1+n^{-\Theta (\log(n)))}} 3 ] アイテム数が最大4つの場合、LDMは最適な分割を返します。 LDM は常に、最大合計が最適値の 7/6 倍以下であるような分割を返します。[ 4 ] [ 2 ] ランダムなインスタンスでは、この近似アルゴリズムは貪欲な数値分割 よりもはるかに優れたパフォーマンスを発揮します。しかし、数値がセットのサイズに対して指数関数的に増加するインスタンスでは、依然としてパフォーマンスが劣ります。[ 5 ]
マルチウェイパーティショニング 任意のk ≥ 2に対して、アルゴリズムは次のように一般化できます。[ 2 ]
まず、 S の各数i に対して、 1 つの部分集合が { i }であり、他のk -1 個の部分集合が空である k 個の部分集合からなるタプルを作成します。各反復において、最大和と最小和の差が最大となる2 つのk タプルA とBを選択し、それらをサイズの逆順で結合します。つまり、 A の最小部分集合とBの最大部分集合、 A の2 番目に小さい部分集合とB の 2 番目に大きい部分集合、などです。 単一のパーティションが残るまで、この手順を繰り返してください。 例：
S = {8,7,6,5,4} かつk =2 の場合、初期分割は ({8},{}), ({7},{}), ({6},{}), ({5},{}), ({4},{}) です。最初のステップの後、({6},{}), ({5},{}), ({4},{}), ({8},{7}) を得ます。次に ({4},{}), ({8},{7}), ({6},{5}) を得ます。次に ({4,7},{8}), ({6},{5}) を得、最後に ({4,7,5},{8,6}) を得ます。ここで、和の差は 2 です。これは、上記で説明した分割と同じです。 S = {8,7,6,5,4} かつk =3 の場合、初期分割は ({8},{},{}), ({7},{},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}) です。最初のステップの後、({8},{7},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}) を得ます。次に ({5},{},{}), ({4},{},{}), ({8},{7},{6}) を得ます。次に ({5},{4},{}), ({8},{7},{6}) を得、最後に ({5,6},{4,7},{8}) を得ます。ここで、和の差は 3 です。 S = {5,5,5,4,4,3,3,1} かつk =3 の場合、7 回反復すると、分割 ({4,5},{1,4,5},{3,3,5}) が得られます。[ 2 ] LDMの優れたパフォーマンスを示す証拠がある：[ 2 ]
シミュレーション実験によると、数値が [0,1] で一様乱数である場合、LDM は常に貪欲な数値分割 よりも優れたパフォーマンスを発揮します (つまり、最大合計がより小さい分割を生成します)。項目の数nが十分に大きい場合、 マルチフィット アルゴリズム よりも優れたパフォーマンスを発揮します。数値が [ o , o +1] で一様乱数である場合、あるo >0 から、LDM のパフォーマンスは安定していますが、マルチフィットのパフォーマンスはo の 増加 とともに悪化します。o >0.2 の場合、LDM のパフォーマンスが優れています。 f* を最適な最大合計値とする。すべての数値がf */3より大きい場合、LDM は最適な解を返す。そうでない場合、LDM は最大合計値と最小合計値の差が最大数値（最大f */3）以下となる解を返す。アイテム数が最大でk +2個の場合、LDMが最適である。 項目の数nが k +2 から 2 k の間である場合、LDM 分割における最大合計は4 3 − 1 3 （ n − k − 1 ） {\displaystyle {\frac {4}{3}}-{\frac {1}{3(nk-1)}}} すべての場合において、LDM 分割における最大合計値は4 3 − 1 3 k {\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}} 4 3 − 1 3 （ k − 1 ） {\displaystyle {\frac {4}{3}}-{\frac {1}{3(k-1)}}} 2方向分割の場合、入力が一様分布の確率変数である場合、最大合計と最小合計の期待差はn − Θ （ ログ n ） {\displaystyle n^{-\Theta (\log n)}} 3 ]
バランスの取れた双方向パーティショニング LDMのいくつかの変種は、すべての部分集合が同じ濃度 （最大1）を持つ必要があるバランスのとれた数分割問題のために開発されました。
PDM（ペア差分法） は次のように機能します。[ 6 ]
数字を大きい順から小さい順に並べなさい。 1番と2番をその差に置き換え、3番と4番をその差に置き換え、以下同様です。 2つ以上の数字が残っている場合は、手順1に戻ります。 バックトラッキング を用いて、分割を計算します。PDMはLDMよりも平均的な特性が劣ります。2方向分割の場合、入力が一様分布の確率変数である場合、最大合計と最小合計の期待差はΘ （ 1 / n ） {\displaystyle \Theta (1/n)}
RLDM（制限付き最大差分法） は次のように動作します。[ 7 ]
数字を大きい順から小さい順に並べなさい。 1番と2番をその差に置き換え、3番と4番をその差に置き換え、以下同様です。 n /2個の差のリストを大きい順に並べ替えます。各ペアを順番に異なるセットに割り当てます。ペアの中で大きい方を合計が最小のセットに、小さい方を合計が最大のセットに割り当てます。 2方向分割の場合、入力が一様分布の確率変数である場合、最大合計と最小合計の期待差はO （ ログ n / n 2 ） {\displaystyle O(\log {n}/n^{2})}
BLDM（Balanced Largest Differencing Method） は次のように動作します。[ 3 ]
数字を大きい順から小さい順に並べなさい。 1番と2番をその差に置き換え、3番と4番をその差に置き換え、以下同様です。 差分の集合に対してLDMを実行する。 BLDMはLDMと同様の平均的な特性を持つ。2方向分割の場合、入力が一様分布のランダム変数である場合、最大合計と最小合計の期待差はn − Θ （ ログ n ） {\displaystyle n^{-\Theta (\log n)}} 3 ]
多分割の場合、c = ceiling( n / k ) で、k 個のサブセットのそれぞれが ceiling( n / k ) または floor( n / k ) 個の項目を含む必要があるとき、最小最大合計に対する BLDM の近似比は、 c = 3 の場合 4/3、c = 4 の場合 19/12、c = 5 の場合 103/60、c = 6 の場合 643/360、c = 7 の場合 4603/2520 となります。これらの比は、 混合整数線形計画問題 を解くことによって求められました。一般に (任意のc に対して)、近似比は少なくとも2 − ∑ j = 0 c − 1 j ! c ! {\displaystyle 2-\sum _{j=0}^{c-1}{\frac {j!}{c!}}} 2 − 1 c − 1 {\displaystyle 2-{\frac {1}{c-1}}} k ）の場合、近似比は正確に2 − 1 k {\displaystyle 2-{\frac {1}{k}}} 8 ]
最小最大部分列問題 最小最大部分列問題 では、入力はn 個の数値の多重集合と整数パラメータk であり、目標は隣接するk 個の数値の各ブロックの最大合計が可能な限り小さくなるように数値を順序付けることです。この問題はビデオサーバーの設計で発生します。[ 9 ] この問題はk = 2の場合は多項式時間で解くことができますが、k ≥ 3の場合は強い NP 困難 です。この問題には差分法の変種を適用できます。[ 10 ]
正確なアルゴリズム 完全なカルマーカー・カルプアルゴリズム（CKK）は、 次数 の木を構築することによって最適解を見つけます。k ! {\displaystyle k!}
k = 2の場合、各レベルは 2 つの数値に対応し、2 つの分岐はそれらの差を取る（つまり、それらを異なる集合に入れる）か、それらの和を取る（つまり、それらを同じ集合に入れる）かに対応します。一般のkの場合、各レベルは k タプルのペアに対応し、k ! {\displaystyle k!} k = 2の場合、CKK はランダムなインスタンスに対して完全貪欲アルゴリズム (CGA) よりも大幅に高速に動作します。これは 2 つの理由によるものです。等しい分割が存在しない場合、CKK は CGA よりもトリミングを多く許容することが多く、等しい分割が存在する場合、CKK はそれをはるかに速く見つけることができ、そのため早期に終了できます。Richard E. Korf は 、CKK は 40 個の 15 桁の倍精度数を約 3 時間で最適に分割できるのに対し、CGA は約 9 時間かかると報告しています。実際には、k = 2 の場合、数値の 有効桁 数が最大 12 桁であれば、任意のサイズの問題を CKK で解決できます。k = 3 の場合、有効桁数が最大 6 桁であれば解決 できます。[ 11 ]
CKKはいつでも実行できるアルゴリズム としても機能します。まずKK解を見つけ、その後、時間が許す限り徐々に優れた解を見つけます（最悪の場合、最適解に到達するのに指数関数的な時間が必要になる可能性があります）。[ 12 ]
CKKとバランス型LDMアルゴリズム（BLDM）を組み合わせることで、バランス型分割問題 を解決するための完全ないつでも実行可能なアルゴリズム が得られます。[ 13 ]
過去の言及 カルマルカー・カルプ差分ヒューリスティックに相当するアルゴリズムは、ナフマニデス とヨセフ・イブン・ハビブ による古代ユダヤ法文書に記載されている。このアルゴリズムは、同じローンに関する異なる証言を組み合わせるために使用されている。[ 14 ]
実装 Python : prtpy ライブラリには、Karmarkar-Karp アルゴリズムの実装と完全な Karmarkar-Karp アルゴリズムが含まれています。
参考文献 ↑ Narendra Karmarkar およびRichard M. Karp 、「集合分割の差分法」、技術報告書 UCB/CSD 82/113、カリフォルニア大学バークレー校 コンピュータサイエンス部門、1982 年1 2 3 4 5 Michiels, Wil; Korst, Jan; Aarts, Emile (2003). "Karmarkar–Karp差分法の性能比". Electronic Notes in Discrete Mathematics . 13 : 71– 75. CiteSeerX 10.1.1.107.1332 . doi : 10.1016/S1571-0653(04)00442-1 . 1 2 3 4 5 Yakir, Benjamin (1996-02-01). "The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp". Mathematics of Operations Research . 21 (1): 85–99 . doi : 10.1287/moor.21.1.85 . ISSN 0364-765X . ↑ Fischetti, Matteo; Martello, Silvano (1987-02-01). "分割問題に対する差分法の最悪ケース分析" . Mathematical Programming . 37 (1): 117– 120. doi : 10.1007/BF02591687 . ISSN 1436-4646 . S2CID 30065792 . ↑ ヘイズ、ブライアン （2002年3月～4月）「最も簡単な難問」、 アメリカン・サイエンティスト 、第 90巻、第2号、シグマ・サイ、科学研究協会、 113～ 117 ページ、 JSTOR 27857621 ↑ Lueker, George S (1987-12-01). "A note on the average-case behavior of a simple differential method for partitioning" . Operations Research Letters . 6 (6): 285– 287. doi : 10.1016/0167-6377(87)90044-7 . ISSN 0167-6377 . ↑ Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling" . SIAM Journal on Computing . 21 (1): 59–64 . doi : 10.1137/0221007 . ISSN 0097-5397 . ↑ ウィル・マイケルズ。ヤン・コルスト。アーツ、エミール。 van Leeuwen、Jan (2003)、 平衡数分割問題に適用された差分法のパフォーマンス比 、コンピュータ サイエンスの講義ノート、vol. 2607、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 583–595 、 doi : 10.1007/3-540-36494-3_51 、 ISBN 978-3-540-00623-7 2021年10月15日 取得↑ ウィル・マイケルズ (2004)。 「差分法のパフォーマンス比」。アイントホーフェン工科大学、2004 年。https://www.elibrary.ru/item.asp? id=8860464 ↑ Michiels, Wil; Korst, Jan (2001). "マルチゾーンディスク記録における最小最大部分列問題" . Journal of Scheduling . 4 (5): 271–283 . doi : 10.1002/jos.80 . ISSN 1099-1425 . ↑ Korf, Richard E. (1995年8月20日). 「近似解から最適解へ：数値分割の事例研究」 . 第14回国際人工知能合同会議議事録 - 第1巻 . IJCAI'95. カナダ、ケベック州モントリオール：Morgan Kaufmann Publishers Inc.：266–272 頁 . ISBN 978-1-55860-363-9 。↑ Korf, Richard E. (1998-12-01). "数値分割のための完全ないつでも実行可能なアルゴリズム" . 人工知能 . 106 (2): 181– 203. doi : 10.1016/S0004-3702(98)00086-1 . ISSN 0004-3702 . ↑ Mertens, Stephan (1999-03-11). "バランスのとれた数値分割のための完全ないつでも実行可能なアルゴリズム". arXiv : cs/9903011 . ↑ Ron Adin と Yuval Roichman (2015). 「証拠の組み合わせ: 数学的側面」 (PDF) . BDD (ヘブライ語). 30 . Bar-Ilan University : 7– 20. 
