分割問題は NP 困難であることが知られています。問題の特定のインスタンスに応じて、動的計画法または差分などのヒューリスティック (Karmarkar-Karp アルゴリズムとも呼ばれます) を試すことができます。
後者は、大きな数のインスタンス (動的プログラミングを扱いにくくするもの) には非常に便利なようですが、必ずしも完全ではありません。より良い解を見つける効率的な方法は何ですか (ランダム、タブー検索、その他の近似)?
PS: 質問には裏話があります。2004 年 7 月から、ジョニー ゴーズ ショッピングが SPOJ で利用できる課題があります。現在までに、この課題は 1087 人のユーザーによって解決されましたが、正しい Karmarkar-Karp アルゴリズムの実装よりも良いスコアを獲得したのは 11 人だけでした (現在のスコアでは、Karmarkar-Karp は 11.796614 を与えます)。ポイント）。より良い方法は？（承認された提出によってサポートされる回答が最も望まれますが、コードを公開しないでください。）
価値が何であれ、[Korf88] の「完全な Karmarkar Karp」(CKK) 検索手順の単純で最適化されていない Python 実装 -- わずかに変更されて、指定された時間制限 (たとえば、4.95 秒) 後に検索から抜け出し、これまでに見つかった最良の解を返します。これは、SPOJ 問題で14.204234を獲得するのに十分であり、Karmarkar-Karp のスコアを上回ります。これを書いている時点で、これはランキングで第 3 位です(以下の編集 #2 を参照) 。
[Mert99] には、Korf の CKK アルゴリズムのもう少し読みやすいプレゼンテーションがあります。
編集 #2 -数のリストがしきい値を下回るまで Karmarkar-Karp を適用し、正確な Horowitz-Sahni サブセット列挙法 [HS74] に切り替えるEvgeny Kluev のハイブリッド ヒューリスティックを実装しました (簡潔な説明は、 [Korf88])。予想どおり、私の Python 実装では、C++ 実装よりも切り替えしきい値を下げる必要がありました。試行錯誤の結果、制限時間内にプログラムを終了できる最大値は 37 であることがわかりました。それでも、その低いしきい値でも、2 位に十分な15.265633のスコアを達成することができました。
さらに、このハイブリッド KK/HS メソッドを CKK ツリー検索に組み込むことを試みました。これは、基本的に HS を非常に攻撃的でコストのかかる枝刈り戦略として使用することによって行われました。素の CKK では、KK/HS 方式とさえ一致する切り替えしきい値を見つけることができませんでした。ただし、CKK および HS (しきい値 25) の ILDS (以下を参照) 検索戦略を使用してプルーニングすると、以前のスコアを15.272802までわずかに上回ることができました。CKK+ILDS は、設計上、HS フェーズにより多様な入力を提供するため、このコンテキストでプレーンな CKK よりも優れていることはおそらく驚くべきことではありません。
編集 #1 - ベースの CKK アルゴリズムにさらに 2 つの改良を加えてみました。
"Improved Limited Discrepancy Search" (ILDS) [Korf96] これは、検索ツリー内のパスの自然な DFS 順序付けに代わるものです。通常の深さ優先検索よりも早い段階で、より多様なソリューションを探索する傾向があります。
「2-Way Number Partitioning の高速化」 [Cerq12] これは、葉ノードの 4 レベル内のノードから葉ノードの上の 5、6、および 7 レベル内のノードへの CKK の枝刈り基準の 1 つを一般化します。
私のテストケースでは、これらの改良の両方が、探索するノードの数を減らし (後者の場合)、より良い解決策に早く到達する (前者の場合) という点で、元の CKK よりも顕著な利点を一般に提供しました。しかし、SPOJ の問題構造の範囲内では、どちらも私のスコアを向上させるのに十分ではありませんでした。
この SPOJ 問題の特異な性質 (つまり、制限時間は 5 秒で、特定の非公開の問題インスタンスは 1 つだけ) を考えると、何が実際にスコアを改善するかについてアドバイスすることは困難です*。たとえば、代替の検索順序付け戦略を引き続き追求する必要があります (例:ここにリストされているWheeler Ruml による多くの論文)? それとも、プルーニングを支援するために、CKK によって見つかったソリューションに何らかの形のローカル改善ヒューリスティックを組み込んでみる必要がありますか? それとも、CKK ベースのアプローチを完全に放棄して、動的プログラミングのアプローチを試す必要があるのでしょうか? PTASはどうですか？SPOJ 問題で使用されるインスタンスの特定の形状について詳しく知らなければ、どのようなアプローチが最も効果的かを推測することは非常に困難です。特定のインスタンスの特定のプロパティに応じて、それぞれに長所と短所があります。
* Python の代わりに C++ で実装するなどして、単に同じことをより高速に実行することは別として。
[Cerq12] Cerquides、Jesús、Pedro Meseguer。「双方向の数値分割の高速化」。ECAI。2012年、土井：10.3233/978-1-61499-098-7-223
[HS74] ホロウィッツ、エリス、サルタージ・サーニ。「ナップザック問題へのアプリケーションによるパーティションの計算。」 ACM ジャーナル (JACM) 21.2 (1974): 277-292。
[Korf88] Korf、Richard E. (1998)、「数値分割のための完全ないつでもアルゴリズム」、人工知能 106 (2): 181–203、doi: 10.1016/S0004-3702(98)00086-1、
[Korf96] Korf、Richard E.「改善された制限された不一致検索。」ＡＡＡＩ／ＩＡＡＩ Ｖｏｌ．1. 1996年。
[Mert99] Mertens、Stephan (1999)、バランスのとれた数の分割のための完全ないつでもアルゴリズム、arXiv: cs/9903011
編集これは、Karmarkar-Karp 差分で始まり、結果のパーティションを最適化しようとする実装です。
時間が許す唯一の最適化は、1つのパーティションから別のパーティションに1 を与え、両方のパーティション間で 1 対 1 で交換することです。
Karmarkar-Karp だけで得られたスコアはOP で引用された 11.796614 ポイントではなく2.711483であるため、最初の Karmarkar-Karp の実装は不正確である必要があります。最適化を使用すると、スコアは7.718049になります。
ネタバレ注意 C# サブミッション コードは次のとおりです。
using System;
using System.Collections.Generic;
using System.Linq;
public class Test
{
// some comparer's to lazily avoid using a proper max-heap implementation
public class Index0 : IComparer<long[]>
{
public int Compare(long[] x, long[] y)
{
if(x[0] == y[0]) return 0;
return x[0] < y[0] ? -1 : 1;
}
public static Index0 Inst = new Index0();
}
public class Index1 : IComparer<long[]>
{
public int Compare(long[] x, long[] y)
{
if(x[1] == y[1]) return 0;
return x[1] < y[1] ? -1 : 1;
}
}
public static void Main()
{
// load the data
var start = DateTime.Now;
var list = new List<long[]>();
int size = int.Parse(Console.ReadLine());
for(int i=1; i<=size; i++) {
var tuple = new long[]{ long.Parse(Console.ReadLine()), i };
list.Add(tuple);
}
list.Sort((x, y) => { if(x[0] == y[0]) return 0; return x[0] < y[0] ? -1 : 1; });
// Karmarkar-Karp differences
List<long[]> diffs = new List<long[]>();
while(list.Count > 1) {
// get max
var b = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
// get max
var a = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
// (b - a)
var diff = b[0] - a[0];
var tuple = new long[]{ diff, -1 };
diffs.Add(new long[] { a[0], b[0], diff, a[1], b[1] });
// insert (b - a) back in
var fnd = list.BinarySearch(tuple, new Index0());
list.Insert(fnd < 0 ? ~fnd : fnd, tuple);
}
var approx = list[0];
list.Clear();
// setup paritions
var listA = new List<long[]>();
var listB = new List<long[]>();
long sumA = 0;
long sumB = 0;
// Karmarkar-Karp rebuild partitions from differences
bool toggle = false;
for(int i=diffs.Count-1; i>=0; i--) {
var inB = listB.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
var inA = listA.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
if(inB >= 0 && inA >= 0) {
toggle = !toggle;
}
if(toggle == false) {
if(inB >= 0) {
listB.RemoveAt(inB);
}else if(inA >= 0) {
listA.RemoveAt(inA);
}
var tb = new long[]{diffs[i][1], diffs[i][4]};
var ta = new long[]{diffs[i][0], diffs[i][3]};
var fb = listB.BinarySearch(tb, Index0.Inst);
var fa = listA.BinarySearch(ta, Index0.Inst);
listB.Insert(fb < 0 ? ~fb : fb, tb);
listA.Insert(fa < 0 ? ~fa : fa, ta);
} else {
if(inA >= 0) {
listA.RemoveAt(inA);
}else if(inB >= 0) {
listB.RemoveAt(inB);
}
var tb = new long[]{diffs[i][1], diffs[i][4]};
var ta = new long[]{diffs[i][0], diffs[i][3]};
var fb = listA.BinarySearch(tb, Index0.Inst);
var fa = listB.BinarySearch(ta, Index0.Inst);
listA.Insert(fb < 0 ? ~fb : fb, tb);
listB.Insert(fa < 0 ? ~fa : fa, ta);
}
}
listA.ForEach(a => sumA += a[0]);
listB.ForEach(b => sumB += b[0]);
// optimize our partitions with give/take 1 or swap 1 for 1
bool change = false;
while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
change = false;
// give one from A to B
for(int i=0; i<listA.Count; i++) {
var a = listA[i];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0]) - (sumB + a[0]))) {
var fb = listB.BinarySearch(a, Index0.Inst);
listB.Insert(fb < 0 ? ~fb : fb, a);
listA.RemoveAt(i);
i--;
sumA -= a[0];
sumB += a[0];
change = true;
} else {break;}
}
// give one from B to A
for(int i=0; i<listB.Count; i++) {
var b = listB[i];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA + b[0]) - (sumB - b[0]))) {
var fa = listA.BinarySearch(b, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.RemoveAt(i);
i--;
sumA += b[0];
sumB -= b[0];
change = true;
} else {break;}
}
// swap 1 for 1
for(int i=0; i<listA.Count; i++) {
var a = listA[i];
for(int j=0; j<listB.Count; j++) {
var b = listB[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b[0]) - (sumB -b[0] + a[0]))) {
listA.RemoveAt(i);
listB.RemoveAt(j);
var fa = listA.BinarySearch(b, Index0.Inst);
var fb = listB.BinarySearch(a, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.Insert(fb < 0 ? ~fb : fb, a);
sumA = sumA - a[0] + b[0];
sumB = sumB - b[0] + a[0];
change = true;
break;
}
}
}
//
if(change == false) { break; }
}
/*
// further optimization with 2 for 1 swaps
while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
change = false;
// trade 2 for 1
for(int i=0; i<listA.Count >> 1; i++) {
var a1 = listA[i];
var a2 = listA[listA.Count - 1 - i];
for(int j=0; j<listB.Count; j++) {
var b = listB[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a1[0] - a2[0] + b[0]) - (sumB - b[0] + a1[0] + a2[0]))) {
listA.RemoveAt(listA.Count - 1 - i);
listA.RemoveAt(i);
listB.RemoveAt(j);
var fa = listA.BinarySearch(b, Index0.Inst);
var fb1 = listB.BinarySearch(a1, Index0.Inst);
var fb2 = listB.BinarySearch(a2, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.Insert(fb1 < 0 ? ~fb1 : fb1, a1);
listB.Insert(fb2 < 0 ? ~fb2 : fb2, a2);
sumA = sumA - a1[0] - a2[0] + b[0];
sumB = sumB - b[0] + a1[0] + a2[0];
change = true;
break;
}
}
}
//
if(DateTime.Now.Subtract(start).TotalSeconds > 4.8) { break; }
// trade 2 for 1
for(int i=0; i<listB.Count >> 1; i++) {
var b1 = listB[i];
var b2 = listB[listB.Count - 1 - i];
for(int j=0; j<listA.Count; j++) {
var a = listA[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b1[0] + b2[0]) - (sumB - b1[0] - b2[0] + a[0]))) {
listB.RemoveAt(listB.Count - 1 - i);
listB.RemoveAt(i);
listA.RemoveAt(j);
var fa1 = listA.BinarySearch(b1, Index0.Inst);
var fa2 = listA.BinarySearch(b2, Index0.Inst);
var fb = listB.BinarySearch(a, Index0.Inst);
listA.Insert(fa1 < 0 ? ~fa1 : fa1, b1);
listA.Insert(fa2 < 0 ? ~fa2 : fa2, b2);
listB.Insert(fb < 0 ? ~fb : fb, a);
sumA = sumA - a[0] + b1[0] + b2[0];
sumB = sumB - b1[0] - b2[0] + a[0];
change = true;
break;
}
}
}
//
if(change == false) { break; }
}
*/
// output the correct ordered values
listA.Sort(new Index1());
foreach(var t in listA) {
Console.WriteLine(t[1]);
}
// DEBUG/TESTING
//Console.WriteLine(approx[0]);
//foreach(var t in listA) Console.Write(": " + t[0] + "," + t[1]);
//Console.WriteLine();
//foreach(var t in listB) Console.Write(": " + t[0] + "," + t[1]);
}
}