Problema de partición

El problema de la partición (también el problema de la distribución de números, que a menudo se observa con PARTICIÓN ) es un problema de optimización o decisión en la combinatoria .

Formulación del problema de la partición

La tarea para el problema de la partición es la siguiente: Se da un ( multi ) conjunto de números naturales. Buscamos una división de estos números en dos grupos para que la diferencia entre las sumas de los números en los dos grupos sea lo más pequeña posible.

Una formulación equivalente dice más precisamente: Se da un (multi) conjunto A de N números naturales . Buscamos un subconjunto tal que ${\ Displaystyle a_ {i}}$ ${\ Displaystyle A_ {1} \ subconjunto A}$

${\ Displaystyle E: = \ left | \ sum _ {a_ {i} \ in A_ {1}} a_ {i} - \ sum _ {a_ {i} \ in A \ setminus A_ {1}} a_ {i } \ right |}$

se vuelve mínimo. Una división que es para se llama división perfecta. ${\ Displaystyle E = 0}$

Como condición adicional, se puede restringir el conjunto de solución del problema de partición desde el principio permitiendo solo particiones balanceadas en las que ambos grupos sean iguales, es decir, el número de números en los subconjuntos debe ser el mismo para N pares y debe ser igual para N. impares difieren en 1. También en este caso, el problema de la partición está completo. ${\ Displaystyle {\ mathcal {NP}}}$

Si cambia la pregunta y pregunta: "¿Existe una división perfecta?", El problema de optimización descrito anteriormente se convierte en un problema de decisión . Ya no buscas la mejor distribución, solo preguntas por su existencia.

El problema de la partición es uno de los 21 problemas NP-completos clásicos , de los cuales Richard M. Karp pudo demostrar en 1972 que pertenecen a la clase de problemas NP-completos.

Transición de fase en el problema de la partición

Se observan dos fases distintas con el problema de la partición: si el conjunto A consta de muchos números pequeños, está claro que hay muchas particiones perfectas y es fácil encontrar una de estas particiones (fase simple). Si, por el contrario, A consta de unos pocos números grandes, es poco probable que exista una división perfecta y debe probar todas las posibilidades para encontrar la mejor división (fase difícil).

Se observa una transición entre la fase simple y la dura, que, en analogía con la física estadística, se denomina transición de fase . En esta transición de fase, la probabilidad de encontrar una distribución perfecta cae a pasos agigantados de 1 en la fase fácil a 0 en la fase difícil. A medida que aumenta el número N de números, la transición se vuelve más nítida.

La posición de la transición de fase dependiendo del número y tamaño de los números individuales se puede calcular utilizando métodos de física estadística .

Todos los algoritmos actualmente conocidos tienen un "tiempo de ejecución en el peor de los casos" que crece exponencialmente con el número de números N , es decir, en el peor de los casos, necesita un tiempo de cálculo que aumenta exponencialmente con N para resolver el problema de decisión . En muchos casos, sin embargo, el tiempo de cálculo realmente requerido es significativamente menor: en la fase simple, el algoritmo encuentra rápidamente una de las muchas soluciones perfectas y, por lo tanto, puede responder al problema de decisión con "sí, hay una solución perfecta" y detener el buscar. Incluso en la fase difícil, los algoritmos adecuados (por ejemplo, el algoritmo cBLDM) pueden finalizar rápidamente la búsqueda con una decisión negativa si no existe una solución. Por lo tanto, los problemas “más difíciles” se encuentran directamente en la transición de fase, donde deben probarse todas las subdivisiones antes de poder decidir el problema. ${\ Displaystyle 2 ^ {N-1}}$

Solución mediante programación dinámica

Con la ayuda de la programación dinámica se puede resolver el problema de la partición en tiempo pseudopolinomial . Los subproblemas más pequeños se consideran sistemáticamente y sus soluciones se tabulan y combinan de forma recursiva.

Sea la suma de todos los números dados. Obviamente, si es extraño, no hay una división perfecta. De lo contrario, se comprueba para todos y cada uno si hay una selección de números en la familia de los primeros números, cuya suma es exacta . Para y este es obviamente el caso, al igual que para y . Para y no para todos los demás . Este es el comienzo de la recursividad, que se indica en la primera fila de una tabla. Para las otras líneas, las entradas resultan de la siguiente recursividad: Existe una selección para exactamente si ya existe una para , o si es y existe una selección para . La respuesta al problema de decisión viene dada por la última entrada de la tabla (para y ). ${\ Displaystyle S}$ ${\ Displaystyle 0 \ leq i \ leq N}$ ${\ Displaystyle 0 \ leq j \ leq S / 2}$ ${\ Displaystyle \ {a_ {1}, a_ {2}, ..., a_ {i} \}}$ ${\ Displaystyle i}$ ${\ Displaystyle j}$ ${\ Displaystyle i = 0}$ ${\ Displaystyle j = 0}$ ${\ Displaystyle i = 1}$ ${\ Displaystyle j = a_ {1}}$ ${\ Displaystyle i> 1}$ ${\ Displaystyle j}$ ${\ Displaystyle (i, j)}$ ${\ Displaystyle (i-1, j)}$ ${\ Displaystyle j> a_ {i}}$ ${\ Displaystyle (i-1, y-a_ {i})}$ ${\ Displaystyle i = N}$ ${\ Displaystyle j = S / 2}$

La complejidad de este algoritmo es . ${\ Displaystyle {\ mathcal {O}} (n \ cdot S)}$

El siguiente ejemplo muestra una implementación del algoritmo en el lenguaje de programación C ++ .

#include <iostream>
using namespace std;

// Diese Funktion prüft, ob es eine Aufteilung der Menge mit gleichen Summen gibt und gibt dann true zurück, sonst false
bool findPartition(int numbers[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) // for-Schleife, die die Summe der Zahlen berechnet
    {
        sum += numbers[i];
    }
    if (sum % 2 != 0) // Wenn die Summe ungerade ist, wird false zurückgegeben
    {
        return false;
    }
    bool* part = new bool[sum / 2 + 1]; // Deklariert ein Array, in dem gespeichert wird, ob die Zahlen 0, 1, 2, ... als Summe einer Teilmenge der gegebenen Zahlen dargestellt werden können
    for (int i = 0; i <= sum / 2; i++) // for-Schleife, die das Array initialisiert
    {
        part[i] = false;
    }
    for (int i = 0; i < n; i++) // for-Schleife, die die Indexe der Zahlen durchläuft
    {
        for (int j = sum / 2; j >= numbers[i]; j--) // In dieser for-Schleife wird geprüft, ob Halbe Gesamtsumme - Zahl mit Index i als Summe einer Teilmenge von Zahlen mit Index kleiner als i dargestellt werden kann
        {
            if (part[j - numbers[i]] || j == numbers[i]) // Wenn die Summe j - Zahl mit Index i dargestellt werden kann oder die Zahl mit Index i gleich j ist, wird das Element für die Summe j auf true gesetzt
            {
                part[j] = true;
            }
        }
    }
    return part[sum / 2]; // Gibt das Element für die halbe Gesamtsumme der Zahlen zurück. Dieses Element vom Typ bool gibt an, ob diese Summe dargestellt werden kann.
}

// Hauptfunktion die das Programm ausführt
int main()
{
    int numbers[] = { 1, 3, 3, 2, 3, 2 };
    int n = sizeof(numbers) / sizeof(numbers[0]); // Variable für die Anzahl der Zahlen
    if (findPartition(numbers, n)) // Wenn eine Aufteilung mit gleichen Summen gefunden wurde
    {
        cout << "Es gibt eine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole
    }
    else
    {
        cout << "Es gibt keine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole
    }
}

literatura

Steven S. Skiena: El manual de diseño de algoritmos. Segunda impresión corregida. Springer y col., Nueva York NY y col. 1998, ISBN 0-387-94860-0 .

Evidencia individual

↑ Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 223 .
↑ Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 47 .
↑ S. Mertens: Un algoritmo completo en cualquier momento para la partición de números balanceados , arxiv : cs / 9903011
↑ Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 90-92 .
↑ GeeksforGeeks: problema de partición

[1] Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 223 .

[2] Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 47 .

[npp5-3] S. Mertens: Un algoritmo completo en cualquier momento para la partición de números balanceados , arxiv : cs / 9903011

[4] Michael R. Garey, David Stifler Johnson : Computadoras e intratabilidad . Una guía para la teoría de la integridad NP. ISBN 0-7167-1045-5 , págs. 90-92 .

[5] GeeksforGeeks: problema de partición

Languages