集合分区比差分更好
kus*_*szi 29 algorithm optimization partition-problem
已知分区问题是NP难的.根据问题的具体情况,我们可以尝试动态编程或一些启发式方法,如差分(也称为Karmarkar-Karp算法).
后者似乎对于具有大数字的实例(使动态编程难以处理)非常有用,但并不总是完美的.什么是找到更好的解决方案的有效方法(随机,禁忌搜索,其他近似)？
PS:问题背后有一些故事.自2004年7月以来,SPOJ就迎来了挑战Johnny Goes Shopping.到目前为止,1087个用户已经解决了这个挑战,但只有11个用户得分高于正确的Karmarkar-Karp算法(目前得分,Karmarkar-Karp给出了11.796614)点).怎么做得更好？(最受欢迎的已接受提交支持的答案,但请不要透露您的代码.)
Evg*_*uev 16
有许多论文描述了用于集合划分的各种高级算法.这里只有两个:
- Richard E. Korf撰写的"完整的数字分割算法".
- Hans Kellerer等人的"子集和问题的有效全多项式逼近方案".
老实说,我不知道哪一个能提供更有效的解决方案.可能不需要这些高级算法来解决SPOJ问题.科夫的论文仍然非常有用.这里描述的算法非常简单(理解和实现).他还概述了几种更简单的算法(第2节).因此,如果您想了解Horowitz-Sahni或Schroeppel-Shamir方法(如下所述)的详细信息,您可以在Korf的论文中找到它们.另外(在第8节中)他写道,随机方法并不能保证足够好的解决方案.因此,您不太可能通过爬山,模拟退火或禁忌搜索等方式获得显着改进.
我尝试了几种简单的算法及其组合来解决分区问题,大小高达10000,最大值高达10 14,时间限制为4秒.他们在随机均匀分布的数字上进行测试.我尝试的每个问题实例都找到了最佳解决方案.对于某些问题实例,算法保证了最优性,对于其他问题,最优性不是100%保证,但获得次优解的概率非常小.
对于最大4的尺寸(左侧的绿色区域),Karmarkar-Karp算法始终提供最佳结果.
对于高达54的尺寸,蛮力算法足够快(红色区域).Horowitz-Sahni或Schroeppel-Shamir算法之间有一个选择.我使用了Horowitz-Sahni,因为它对于给定的限制似乎更有效.Schroeppel-Shamir使用更少的内存(一切都适合L2缓存),因此当其他CPU内核执行一些内存密集型任务或使用多个线程进行集合分区时,这可能更为可取.或者用不那么严格的时间限制来解决更大的问题(Horowitz-Sahni只是耗尽了内存).
当大小乘以所有值的总和小于5*10 9(蓝色区域)时,动态编程方法是适用的.图中的强力和动态编程区域之间的边界显示了每种算法在哪些方面表现更好.
右边的绿色区域是Karmarkar-Karp算法以几乎100%的概率提供最佳结果的地方.这里有很多完美的分区选项(delta 0或1),Karmarkar-Karp算法几乎肯定能找到其中之一.可以发明Karmarkar-Karp总是给出次优结果的数据集.例如{17 13 10 10 10 ...}.如果将此乘以某个大数,KK和DP都无法找到最佳解.幸运的是,这些数据集实际上不太可能.但是问题设定者可能会添加这样的数据集以使比赛变得更加困难.在这种情况下,您可以选择一些高级算法以获得更好的结果(但仅适用于图中的灰色和右侧绿色区域).
我尝试了两种方法来实现Karmarkar-Karp算法的优先级队列:使用最大堆和排序数组.使用线性搜索,排序数组选项似乎稍快,而使用二进制搜索则显着更快.
黄色区域是您可以在保证最佳结果(使用DP)或仅具有高概率的最佳结果(使用Karmarkar-Karp)之间进行选择的地方.
最后,灰色区域,其中两个简单算法本身都不能给出最佳结果.在这里,我们可以使用Karmarkar-Karp预处理数据,直到它适用于Horowitz-Sahni或动态编程.在这个地方还有许多完美的分区选项,但比绿色区域要少,因此Karmarkar-Karp本身有时会错过适当的分区.更新:如@mhum所述,没有必要实现动态编程算法来使事情有效.Horowitz-Sahni与Karmarkar-Karp预处理就足够了.但是,Horowitz-Sahni算法必须在所述时间限制内处理大小达到54的大小,以(几乎)保证最佳分区.所以C++或其他语言具有良好的优化编译器和快速计算机是更可取的.
以下是我将Karmarkar-Karp与其他算法结合使用的方法:
template<bool Preprocess = false>
i64 kk(const vector<i64>& values, i64 sum, Log& log)
{
log.name("Karmarkar-Karp");
vector<i64> pq(values.size() * 2);
copy(begin(values), end(values), begin(pq) + values.size());
sort(begin(pq) + values.size(), end(pq));
auto first = end(pq);
auto last = begin(pq) + values.size();
while (first - last > 1)
{
if (Preprocess && first - last <= kHSLimit)
{
hs(last, first, sum, log);
return 0;
}
if (Preprocess && static_cast<double>(first - last) * sum <= kDPLimit)
{
dp(last, first, sum, log);
return 0;
}
const auto diff = *(first - 1) - *(first - 2);
sum -= *(first - 2) * 2;
first -= 2;
const auto place = lower_bound(last, first, diff);
--last;
copy(last + 1, place, last);
*(place - 1) = diff;
}
const auto result = (first - last)? *last: 0;
log(result);
return result;
}
链接到完整的C++ 11实现.此程序仅确定分区总和之间的差异,它不报告分区本身.警告:如果要在可用内存小于1 Gb的计算机上运行它,请降低kHSLimit常量.
mhu*_*hum 15
无论它的价值如何,[Korf88]中"完整的Karmarkar Karp"(CKK)搜索程序的简单,未经优化的Python实现 - 在给定的时间限制(例如,4.95秒)之后仅稍微修改以避免搜索返回到目前为止找到的最佳解决方案 - 足以在SPOJ问题上得分14.204234,击败Karmarkar-Karp的得分.在撰写本文时,排名上排名第3(参见下面的编辑#2)
在[Mert99]中可以找到更加可读的Korf CKK算法.
编辑#2 - 我实施了Evgeny Kluev应用Karmarkar-Karp 的混合启发式,直到数字列表低于某个阈值,然后切换到精确的Horowitz-Sahni子集枚举方法[HS74](简明描述可以在[Korf88]).正如所怀疑的那样,我的Python实现需要降低切换阈值而不是他的C++实现.经过一些反复试验,我发现阈值为37是允许我的程序在限定时间内完成的最大值.然而,即使在那个较低的门槛,我也能获得15.265633的分数,足以获得第二名.
我进一步尝试将这种混合KK/HS方法结合到CKK树搜索中,基本上通过使用HS作为非常积极且昂贵的修剪策略.在简单的CKK中,我无法找到甚至与KK/HS方法匹配的切换阈值.然而,使用ILDS(见下文)CKK和HS(阈值为25)的搜索策略进行修剪,我能够比之前的得分产生非常小的增益,最高可达15.272802.在这种背景下,CKK + ILDS的表现可能超过普通的CKK,因为它可以为HS阶段提供更多的输入多样性,因此可能不足为奇.
编辑#1 - 我已经尝试了对基本CKK算法的两个进一步改进:
"改进的有限差异搜索"(ILDS)[Korf96]这是搜索树中路径的自然DFS排序的替代方案.与常规的深度优先搜索相比,它更倾向于在早期探索更多样化的解决方案.
"加速双向数字分区"[Cerq12]这将CKK中的一个修剪标准从叶节点的4个级别内的节点推广到叶节点上方5,6和7级的节点.
在我的测试案例中,这两个改进通常比原始CKK提供了明显的好处,减少了探索的节点数量(在后者的情况下)和更快地达到更好的解决方案(在前者的情况下).但是,在SPOJ问题结构的范围内,这些都不足以提高我的分数.
鉴于此SPOJ问题的特殊性质(即:5秒时间限制和仅一个特定且未公开的问题实例),很难就可能实际提高得分*的内容提供建议.例如,我们是否应该继续寻求替代搜索排序策略(例如:Wheeler Ruml 在此列出的许多论文)？或者我们是否应该尝试将某种形式的局部改进启发式结合到CKK找到的解决方案中以帮助修剪？或者我们应该放弃基于CKK的方法并尝试动态编程方法？PTAS怎么样？如果不了解SPOJ问题中使用的实例的具体形状,就很难猜测哪种方法会产生最大的好处.每个都有自己的优点和缺点,具体取决于给定实例的特定属性.
* 除了简单地运行相同的东西,比如说,通过用C++而不是Python实现.
参考
[Cerq12] Cerquides,Jesús和Pedro Meseguer."加速双向数字分区." 外部评级机构.2012年,doi:10.3233/978-1-61499-098-7-223
[HS74] Horowitz,Ellis和Sartaj Sahni." 计算分区与应用程序的背包问题. "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." 改进了有限的差异搜索." AAAI/IAAI,Vol.1. 1996年.
[Mert99] Mertens,Stephan(1999),一个完整的平衡数字划分算法,arXiv:cs/9903011
编辑这是一个以Karmarkar-Karp差异开始然后尝试优化结果分区的实现.
时间允许的唯一优化是从一个分区到另一个分区给出1并在两个分区之间交换1为1.
我在开始时对Karmarkar-Karp的实施必须是不准确的,因为仅仅Karmarkar-Karp的得分为2.711483而不是OP引用的11.796614分.使用优化时,得分为7.718049.
SPOILER WARNING 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]);
}
}