algorithm - Mejores resultados en establecer partición que mediante diferenciación
optimization partition-problem (3)
Hay muchos documentos que describen varios algoritmos avanzados para establecer particiones. Aquí hay solo dos de ellos:
- "Un algoritmo completo en cualquier momento para la partición de números" por Richard E. Korf.
- "Un esquema de aproximación completamente polinomial eficiente para el problema de suma de subconjuntos" por Hans Kellerer et al.
Honestamente, no sé cuál de ellos ofrece una solución más eficiente. Probablemente ninguno de estos algoritmos avanzados sea necesario para resolver ese problema SPOJ. El documento de Korf sigue siendo muy útil. Los algoritmos descritos allí son muy simples (para comprender e implementar). También revisa varios algoritmos incluso más simples (en la sección 2). Entonces, si desea conocer los detalles de los métodos Horowitz-Sahni o Schroeppel-Shamir (mencionados a continuación), puede encontrarlos en el documento de Korf. También (en la sección 8) escribe que los enfoques estocásticos no garantizan soluciones suficientemente buenas. Por lo tanto, es poco probable que obtenga mejoras significativas con algo como subir montañas, recocido simulado o búsqueda tabú.
Probé varios algoritmos simples y sus combinaciones para resolver problemas de particiones con un tamaño de hasta 10000, un valor máximo de hasta 10 14 y un límite de tiempo de 4 segundos. Fueron probados en números aleatoriamente distribuidos uniformemente. Y se encontró una solución óptima para cada instancia problema que probé. Para algunas instancias de problema, la optimalidad está garantizada por el algoritmo, para otras la optimalidad no está 100% garantizada, pero la probabilidad de obtener una solución subóptima es muy pequeña.
Para tamaños de hasta 4 (área verde a la izquierda), el algoritmo Karmarkar-Karp siempre da un resultado óptimo.
Para tamaños de hasta 54, un algoritmo de fuerza bruta es lo suficientemente rápido (área roja). Existe una opción entre los algoritmos de Horowitz-Sahni o Schroeppel-Shamir. Usé Horowitz-Sahni porque parece más eficiente para los límites dados. Schroeppel-Shamir usa mucha menos memoria (todo encaja en la memoria caché L2), por lo que puede ser preferible cuando otros núcleos de la CPU realizan algunas tareas de uso intensivo de la memoria o para establecer particiones utilizando múltiples subprocesos. O para resolver problemas más grandes con un límite de tiempo no estricto (donde Horowitz-Sahni simplemente se queda sin memoria).
Cuando el tamaño multiplicado por la suma de todos los valores es menor que 5 * 10 9 (área azul), se aplica el enfoque de programación dinámica. El límite entre la fuerza bruta y las áreas de programación dinámica en el diagrama muestra dónde cada algoritmo funciona mejor.
El área verde a la derecha es el lugar donde el algoritmo Karmarkar-Karp da un resultado óptimo con casi el 100% de probabilidad. Aquí hay tantas opciones de partición perfecta (con delta 0 o 1) que el algoritmo de Karmarkar-Karp casi con certeza encuentra una de ellas. Es posible inventar el conjunto de datos donde Karmarkar-Karp siempre da un resultado subóptimo. Por ejemplo, {17 13 10 10 10 ...}. Si multiplicas esto por un número grande, ni KK ni DP podrán encontrar una solución óptima. Afortunadamente, estos conjuntos de datos son muy poco probables en la práctica. Pero el solucionador de problemas podría agregar tal conjunto de datos para hacer el concurso más difícil. En este caso, puede elegir algún algoritmo avanzado para obtener mejores resultados (pero solo para las áreas verdes gris y derecha en el diagrama).
Intenté 2 formas de implementar la cola de prioridad del algoritmo Karmarkar-Karp: con max heap y con array ordenado. La opción de matriz ordenada parece ser un poco más rápida con la búsqueda lineal y significativamente más rápida con la búsqueda binaria.
El área amarilla es el lugar donde puede elegir entre un resultado óptimo garantizado (con DP) o simplemente un resultado óptimo con alta probabilidad (con Karmarkar-Karp).
Finalmente, área gris, donde ninguno de los algoritmos simples por sí solo da un resultado óptimo. Aquí podríamos usar Karmarkar-Karp para procesar datos antes de que sea aplicable a Horowitz-Sahni o a la programación dinámica. En este lugar también hay muchas opciones de partición perfecta, pero menos que en el área verde, por lo que Karmarkar-Karp por sí solo a veces podría perder la partición adecuada. Actualización: Como lo señala @mhum, no es necesario implementar el algoritmo de programación dinámica para que las cosas funcionen. Horowitz-Sahni con preprocesamiento de Karmarkar-Karp es suficiente. Pero es esencial para el algoritmo Horowitz-Sahni trabajar en tamaños de hasta 54 en dicho límite de tiempo para (casi) garantizar una partición óptima. Entonces C ++ u otro lenguaje con un buen compilador de optimización y una computadora rápida son preferibles.
Aquí es cómo combiné Karmarkar-Karp con otros algoritmos:
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;
}
Enlace a la implementación completa de C ++ 11. Este programa solo determina la diferencia entre las sumas de partición, no informa las particiones por sí mismas. Advertencia: si desea ejecutarlo en una computadora con menos de 1 Gb de memoria libre, disminuya la constante kHSLimit .
Se sabe que el problema de partición es NP-hard. Dependiendo de la instancia particular del problema, podemos probar la programación dinámica o algunas heurísticas como la diferenciación (también conocido como algoritmo Karmarkar-Karp).
Este último parece ser muy útil para las instancias con grandes números (lo que hace que la programación dinámica no se pueda resolver), aunque no siempre es perfecto. ¿Cuál es una forma eficiente de encontrar una mejor solución (al azar, búsqueda tabú, otras aproximaciones)?
PD: La pregunta tiene algo de historia detrás. Hay un desafío que Johnny Goes Shopping está disponible en SPOJ desde julio de 2004. Hasta ahora, 1087 usuarios habían resuelto el desafío, pero solo 11 de ellos obtuvieron mejores resultados que la implementación correcta del algoritmo Karmarkar-Karp (con puntuación actual, Karmarkar-Karp da 11.796614 puntos). ¿Cómo hacer mejor? (Las respuestas respaldadas por la presentación aceptada son las más solicitadas, pero no revele su código).
Para lo que valga la pena, una implementación directa, no optimizada de Python del procedimiento de búsqueda "Karmarkar Karp completo" (CKK) en [Korf88] - se modificó solo ligeramente para salir de la búsqueda después de un límite de tiempo dado (digamos, 4,95 segundos) y devolver la mejor solución encontrada hasta el momento: es suficiente para obtener un puntaje de 14.204234 en el problema SPOJ, superando el puntaje de Karmarkar-Karp. Al escribir estas líneas, este es el # 3 en la clasificación ( ver Edición # 2 a continuación )
Una presentación un poco más legible del algoritmo CKK de Korf se puede encontrar en [Mert99].
EDIT # 2 : he implementado la heurística híbrida de Evgeny Kluev para aplicar Karmarkar-Karp hasta que la lista de números esté por debajo de un umbral y luego cambie al método de enumeración de subconjuntos Horowitz-Sahni exacto [HS74] (se puede encontrar una descripción concisa en [Korf88]). Como se sospechaba, mi implementación de Python requería reducir el umbral de conmutación en comparación con su implementación en C ++. Con algunos intentos de prueba y error, descubrí que un umbral de 37 era el máximo que permitía a mi programa finalizar dentro del límite de tiempo. Sin embargo, incluso en ese umbral más bajo, pude lograr un puntaje de 15.265633 , lo suficientemente bueno para el segundo lugar .
Además intenté incorporar este método híbrido KK / HS en la búsqueda de árbol CKK, básicamente usando HS como una estrategia de poda muy agresiva y costosa. En CKK simple, no pude encontrar un umbral de conmutación que igualara el método KK / HS. Sin embargo, usando la estrategia de búsqueda ILDS (ver a continuación) para CKK y HS (con un umbral de 25) para podar, pude obtener una ganancia muy pequeña sobre la puntuación anterior, hasta 15.272802 . Probablemente no debería sorprender que CKK + ILDS supere en rendimiento al CKK simple en este contexto ya que, por diseño, proporcionaría una mayor diversidad de entradas a la fase HS.
EDIT # 1 - He intentado dos refinamientos adicionales para el algoritmo CKK base:
"Búsqueda mejorada de discrepancias limitadas" (ILDS) [Korf96] Esta es una alternativa al ordenamiento DFS natural de las rutas dentro del árbol de búsqueda. Tiene una tendencia a explorar soluciones más diversas antes que la Búsqueda de profundidad-primera regular.
"Acelerar el Particionamiento de Números de 2 Vías" [Cerq12] Esto generaliza uno de los criterios de poda en CKK desde nodos dentro de 4 niveles de los nodos hoja a nodos dentro de 5, 6 y 7 niveles sobre nodos hoja.
En mis casos de prueba, estos dos refinamientos generalmente proporcionaron beneficios notables sobre el CKK original en la reducción del número de nodos explorados (en el caso de este último) y en llegar a mejores soluciones antes (en el caso del primero). Sin embargo, dentro de los límites de la estructura del problema SPOJ, ninguno de estos fue suficiente para mejorar mi puntaje.
Dada la naturaleza idiosincrásica de este problema SPOJ (es decir: límite de tiempo de 5 segundos y solo una instancia de problema específico y no divulgado), es difícil dar consejos sobre lo que en realidad puede mejorar el puntaje * . Por ejemplo, ¿deberíamos continuar buscando estrategias alternativas para ordenar las búsquedas (por ejemplo: muchos de los documentos de Wheeler Ruml que se enumeran aquí )? ¿O deberíamos intentar incorporar alguna forma de heurística de mejora local a las soluciones encontradas por CKK para ayudar a la poda? ¿O tal vez deberíamos abandonar por completo los enfoques basados en CKK e intentar un enfoque de programación dinámica? ¿Qué tal un PTAS? Sin saber más sobre la forma específica de la instancia utilizada en el problema SPOJ, es muy difícil adivinar qué tipo de enfoque produciría el mayor beneficio. Cada uno tiene sus fortalezas y debilidades, dependiendo de las propiedades específicas de una instancia determinada.
* Aparte de simplemente ejecutar lo mismo más rápido, por ejemplo, implementando en C ++ en lugar de hacerlo en Python.
Referencias
[Cerq12] Cerquides, Jesús y Pedro Meseguer. "Acelerando el Particionamiento de Números de 2 vías". ECAI. 2012, doi: 10.3233/978-1-61499-098-7-223
[HS74] Horowitz, Ellis y Sartaj Sahni. " Computación de particiones con aplicaciones al problema de la mochila " . Revista de la ACM (JACM) 21.2 (1974): 277-292.
[Korf88] Korf, Richard E. (1998), " Algoritmo completo en cualquier momento para partición de números ", Artificial Intelligence 106 (2): 181-203, doi: 10.1016/S0004-3702(98)00086-1 ,
[Korf96] Korf, Richard E. " Mejor búsqueda de discrepancias limitada ". AAAI / IAAI, vol. 1. 1996.
[Mert99] Mertens, Stephan (1999), Algoritmo completo en cualquier momento para partición equilibrada de números, arXiv: cs/9903011
EDITAR Aquí hay una implementación que comienza con la diferenciación de Karmarkar-Karp y luego trata de optimizar las particiones resultantes.
Las únicas optimizaciones que permite el tiempo son dar 1 de una partición a la otra e intercambiar 1 por 1 entre ambas particiones.
Mi implementación de Karmarkar-Karp al principio debe ser inexacta ya que la puntuación resultante con solo Karmarkar-Karp es 2.711483, no 11.796614 puntos citados por OP . La puntuación va a 7.718049 cuando se usan las optimizaciones.
ADVERTENCIA DE SPOILER El código de envío C # sigue
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]);
}
}