LISTA DE PROBLEMAS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Ejemplo de un problema de mochila unidimensional (restricción): ¿qué cajas se deben elegir para maximizar la cantidad de dinero mientras se mantiene el peso total por debajo o igual a 15 kg? Un problema con restricciones múltiples podría considerar tanto el peso como el volumen de las cajas.
(Solución: si hay disponible cualquier número de cada cuadro, entonces tres cuadros amarillos y tres cuadros grises; si solo están disponibles los cuadros mostrados, entonces todos menos el cuadro verde).

El problema de la mochila o la mochila es un problema en la optimización combinatoria : dado un conjunto de artículos, cada uno con un peso y un valor, determina el número de cada artículo que se incluirá en una colección para que el peso total sea menor o igual a un límite dado y el valor total es lo más grande posible. Deriva su nombre del problema que enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarlo con los elementos más valiosos.

El problema a menudo surge en la asignación de recursos donde hay restricciones financieras y se estudia en campos como la combinatoria , la informática , la teoría de la complejidad , la criptografía y las matemáticas aplicadas .

El problema de la mochila se ha estudiado durante más de un siglo, con trabajos tempranos que datan de 1897. ^[1] El nombre "problema de la mochila" se remonta a los primeros trabajos del matemático Tobias Dantzig (1884–1956), ^[2] y se refiere al problema común de empacar los artículos más valiosos o útiles sin sobrecargar el equipaje.

Aplicaciones [ editar ]

Un estudio de 1999 del Repositorio de Algoritmo de la Universidad Stony Brook mostró que, de 75 problemas algorítmicos, el problema de la mochila era el decimonoveno más popular y el tercero más necesario después de los árboles de sufijos y el problema del embalaje del contenedor . ^[3]

Los problemas de mochila aparecen en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, como encontrar la forma menos costosa de cortar materias primas, ^[4] selección de inversiones y carteras , ^[5] selección de activos para la titulización respaldada por activos , ^[6] y generar claves para Merkle – Hellman ^[7] y otros criptosistemas de mochila .

Una de las primeras aplicaciones de los algoritmos de mochila fue la construcción y calificación de las pruebas en las que los examinados tienen la opción de elegir qué preguntas responder. Para pequeños ejemplos, es un proceso bastante simple proporcionar a los examinados con tal opción. Por ejemplo, si un examen contiene 12 preguntas cada una con un valor de 10 puntos, el examinado solo necesita responder 10 preguntas para lograr un puntaje máximo posible de 100 puntos. Sin embargo, en las pruebas con una distribución heterogénea de valores puntuales, es más difícil proporcionar opciones. Feuerman y Weiss propusieron un sistema en el que los estudiantes reciben una prueba heterogénea con un total de 125 puntos posibles. Se les pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores de puntos totales suman 100,^[8]

Definición [ editar ]

El problema más común que se resuelve es el problema de la mochila 0-1 , que restringe el número$${\ displaystyle x_ {i}}de copias de cada tipo de artículo a cero o uno. Dado un conjunto de$${\ displaystyle n} artículos numerados del 1 al $${\ displaystyle n}, cada uno con un peso $${\ displaystyle w_ {i}} y un valor $${\ displaystyle v_ {i}}, junto con una capacidad máxima de peso $${\ displaystyle W},

maximizar $${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

sujeto a $${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W} y $${\ displaystyle x_ {i} \ in \ {0,1 \}}.

aquí $${\ displaystyle x_ {i}} representa el número de instancias del artículo $${\ displaystyle i}para incluir en la mochila. Informalmente, el problema es maximizar la suma de los valores de los artículos en la mochila para que la suma de los pesos sea menor o igual que la capacidad de la mochila.

El problema de la mochila acotada ( BKP ) elimina la restricción de que solo hay uno de cada elemento, pero restringe el número$${\ displaystyle x_ {i}} de copias de cada tipo de elemento a un valor entero máximo no negativo $${\ displaystyle c}:

maximizar $${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

sujeto a $${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W} y $${\ displaystyle 0 \ leq x_ {i} \ leq c}

El problema de la mochila sin límites ( UKP ) no coloca un límite superior en el número de copias de cada tipo de artículo y puede formularse como se indica arriba, excepto que la única restricción en$${\ displaystyle x_ {i}} es que es un entero no negativo.

maximizar $${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

sujeto a $${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W} y $${\ displaystyle x_ {i} \ geq 0}

Un ejemplo del problema de la mochila ilimitada se da usando la figura que se muestra al principio de este artículo y el texto "si hay disponible un número de cada casilla" en el título de esa figura.

Complejidad computacional [ editar ]

El problema de la mochila es interesante desde la perspectiva de la informática por muchas razones:

• La forma del problema de decisión del problema de la mochila ( ¿Se puede lograr un valor de al menos V sin exceder el peso W ? ) Es NP-completo , por lo tanto, no existe un algoritmo conocido tanto correcto como rápido (tiempo polinómico) en todos los casos.
• Si bien el problema de decisión es NP-completo, el problema de optimización es NP-duro , su resolución es al menos tan difícil como el problema de decisión, y no existe un algoritmo polinomial conocido que pueda determinar, dada una solución, si es óptimo (que significaría que no hay solución con una V más grande , resolviendo así el problema de decisión de NP completo).
• Hay un algoritmo de tiempo pseudo-polinomial que usa programación dinámica .
• Existe un esquema de aproximación de tiempo completamente polinomial , que utiliza el algoritmo de tiempo pseudo-polinomial como una subrutina, que se describe a continuación.
• Sin embargo, muchos casos que surgen en la práctica y las "instancias aleatorias" de algunas distribuciones pueden resolverse exactamente.

Existe un vínculo entre los problemas de "decisión" y "optimización" en el sentido de que si existe un algoritmo polinomial que resuelve el problema de "decisión", entonces se puede encontrar el valor máximo para el problema de optimización en tiempo polinómico aplicando este algoritmo de forma iterativa mientras aumentando el valor de k. Por otro lado, si un algoritmo encuentra el valor óptimo del problema de optimización en tiempo polinómico, entonces el problema de decisión puede resolverse en tiempo polinómico comparando el valor de la solución de salida por este algoritmo con el valor de k. Por lo tanto, ambas versiones del problema son de dificultad similar.

Un tema en la literatura de investigación es identificar cómo son las instancias "difíciles" del problema de la mochila, ^[9] [10] o verlas de otra manera, para identificar qué propiedades de las instancias en la práctica podrían hacerlas más susceptibles que su peor de los casos El comportamiento NP-completo sugiere. ^[11] El objetivo de encontrar estas instancias "difíciles" es su uso en sistemas de criptografía de clave pública , como el criptosistema de mochila Merkle-Hellman .

Además, es notable el hecho de que la dureza del problema de la mochila depende de la forma de la entrada. Si los pesos y las ganancias se dan como números enteros, es débilmente NP completo , mientras que es fuertemente NP completo si los pesos y las ganancias se dan como números racionales. ^[12] Sin embargo, en el caso de los pesos y ganancias racionales, todavía admite un FPTAS .

Resolviendo [ editar ]

Hay varios algoritmos disponibles para resolver problemas de mochilas, basados ​​en el enfoque de programación dinámica, ^[13] enfoque de rama y límite ^[14] o hibridaciones de ambos enfoques. ^{[11] [15] [16] [17]}

Algoritmo avanzado de programación dinámica [ editar ]

El problema de la mochila sin límites ( UKP ) no restringe el número de copias de cada tipo de artículo. Además, aquí asumimos que{\ displaystyle x_ {i}> 0}

$${\ displaystyle m [w '] = \ max \ left (\ sum _ {i = 1} ^ {n} v_ {i} x_ {i} \ right)}

sujeto a $${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq w '} y {\ displaystyle x_ {i}> 0}

Observa eso $${\ displaystyle m [w]} tiene las siguientes propiedades:

1) $${\ displaystyle m [0] = 0 \, \!} (la suma de cero elementos, es decir, la suma del conjunto vacío).

2) $${\ displaystyle m [w] = \ max (v_ {1} + m [w-w_ {1}], v_ {2} + m [w-w_ {2}], ..., v_ {i} + m [w-w_ {i}])} , $${\ displaystyle w_ {i} \ leq w}, dónde $${\ displaystyle v_ {i}} es el valor de $${\ displaystyle i}-th tipo de artículo.

La segunda propiedad necesita ser explicada en detalle. Durante el proceso de ejecución de este método, ¿cómo conseguimos el peso?$${\ displaystyle w}? Solo hay$${\ displaystyle i} formas y los pesos anteriores son $${\ displaystyle w-w_ {1}, w-w_ {2}, ..., w-w_ {i}} donde hay total $${\ displaystyle i}tipos de elementos diferentes (al decir diferentes, queremos decir que el peso y el valor no son completamente iguales). Si conocemos cada valor de estos$${\ displaystyle i} artículos y el valor máximo relacionado anteriormente, simplemente los comparamos entre sí y finalmente obtenemos el valor máximo y listo.

Aquí el máximo del conjunto vacío se toma como cero. Tabulando los resultados de$${\ displaystyle m [0]} a traves de $${\ displaystyle m [W]}da la solución Desde el cálculo de cada$${\ displaystyle m [w]} implica examinar a lo sumo $${\ displaystyle n} artículos, y hay a lo sumo $${\ displaystyle W} valores de $${\ displaystyle m [w]} para calcular, el tiempo de ejecución de la solución de programación dinámica es $${\ displaystyle O (nW)}. Divisor$${\ displaystyle w_ {1}, \, w_ {2}, \, \ ldots, \, w_ {n}, \, W}por su mayor divisor común es una forma de mejorar el tiempo de ejecución.

Incluso P ≠ NP , el$${\ displaystyle O (nW)}la complejidad no contradice el hecho de que el problema de la mochila es NP-completo , ya que$${\ displaystyle W}, diferente a $${\ displaystyle n}, no es polinomial en la longitud de la entrada al problema. La longitud de la$${\ displaystyle W} la entrada al problema es proporcional al número de bits en $${\ displaystyle W}, $${\ displaystyle \ log W}, No a $${\ displaystyle W}sí mismo. Sin embargo, dado que este tiempo de ejecución es pseudopolinomial , esto hace que la (versión de decisión del) problema de la mochila sea un problema débilmente NP-completo .

Problema de mochila 0/1 [ editar ]

Una solución de programación dinámica similar para el problema de mochila 0/1 también se ejecuta en tiempo pseudopolinomial. Asumir$${\ displaystyle w_ {1}, \, w_ {2}, \, \ ldots, \, w_ {n}, \, W}son enteros estrictamente positivos. Definir$${\ displaystyle m [i, w]} ser el valor máximo que puede alcanzarse con un peso menor o igual a $${\ displaystyle w} usando artículos hasta $${\ displaystyle i} (primero $${\ displaystyle i} artículos).

Podemos definir $${\ displaystyle m [i, w]}recursivamente de la siguiente manera: (Definición A)

• $${\ displaystyle m [0, \, w] = 0}
• $${\ displaystyle m [i, \, w] = m [i-1, \, w]} Si {\ displaystyle w_ {i}> w \, \!} (el nuevo artículo es más que el límite de peso actual)
• $${\ displaystyle m [i, \, w] = \ max (m [i-1, \, w], \, m [i-1, w-w_ {i}] + w_ {i})} Si $${\ displaystyle w_ {i} \ leqslant w}.

La solución se puede encontrar calculando $${\ displaystyle m [n, W]}. Para hacer esto de manera eficiente, podemos usar una tabla para almacenar cálculos anteriores.

El siguiente es un pseudocódigo para el programa dinámico:

1 // Entrada: 
2 // Valores (almacenados en la matriz v) 
3 // Pesos (almacenados en la matriz w) 
4 // Número de elementos distintos (n) 
5 // Capacidad de la mochila (W) 
6 // NOTA: La matriz Se supone que "v" y la matriz "w" almacenan todos los valores relevantes comenzando en el índice 1. 
7 
8 para  j  de  0  a  W  do : 
9     m [ 0 ,  j ]  : =  0 
10 
11 para  i  de  1  a  n  do : 
12     para j  de  0  a  W  do : 
13         si  w [ i ]  >  j  entonces : 
14             m [ i ,  j ]  : =  m [ i - 1 ,  j ] 
15         más : 
16             m [ i ,  j ]  : =  max ( m [ i - 1 ,  j ],  m [ i - 1,  j - w [ i ]]  +  v [ i ])

Por lo tanto, esta solución se ejecutará en $${\ displaystyle O (nW)} tiempo y $${\ displaystyle O (nW)} espacio.

Sin embargo, si damos un paso o dos más, deberíamos saber que el método se ejecutará en el tiempo entre $${\ displaystyle O (nW)} y $${\ displaystyle O (2 ^ {n})}. A partir de la definición A , podemos saber que no es necesario calcular todos los pesos cuando la cantidad de elementos y los elementos que elegimos son fijos. Es decir, el programa anterior calcula más de lo esperado porque el peso cambia de 0 a W todo el tiempo. Todo lo que necesitamos hacer es comparar m [i-1, j] ym [i-1, jw [i]] + v [i] para m [i, j], y cuando m [i-1, jw [i]] está fuera de rango, solo damos el valor de m [i-1, j] a m [i, j]. Desde esta perspectiva, podemos programar este método para que se ejecute de forma recursiva.

1 // Entrada: 
2 // Valores (almacenados en la matriz v) 
3 // Pesos (almacenados en la matriz w) 
4 // Número de elementos distintos (n) 
5 // Capacidad de la mochila (W) 
6 // NOTA: La matriz Se supone que "v" y la matriz "w" almacenan todos los valores relevantes comenzando en el índice 1. 
7 
8 Definir  valor [ n ,  W ] 
9 
10 Inicializar  todo el  valor [ i ,  j ]  =  - 1 
11 
12 Definir  m : = ( i, j )          // Defina la función m para que represente el valor máximo que podemos obtener bajo la condición: use primero los ítems i, el límite de peso total es j 
13 { 
14     si  i  =  0  o  j  <=  0  luego : 
15         devuelve  0 
16     
17     si  ( valor [ i - 1 , j ]  ==  - 1 )  entonces :      // m [i-1, j] no se ha calculado, tenemos que llamar a la función m 
18         valor [ i -1 , j ]  =  m ( i - 1 , j )          
19   
20     si  w [ i ]  >  j  entonces :                       // el artículo no cabe en la bolsa (ESTO FALTA DEL ALGORITMO ANTERIOR) 
21         valor [ i , j ]  =  valor [ i - 1 , j ] 
22     más :  
23         if  ( valor [ i - 1 ,  j- w [ i ]]  ==  - 1 )  entonces :      // m [i-1, jw [i]] no se ha calculado, tenemos que llamar a la función m 
24             valor [ i - 1 ,  j - w [ i ] ]  =  m ( i - 1 ,  j - w [ i ]) 
25         valor [ i ,  j ]  =  max ( valor [ i - 1 ,j ],  valor [ i - 1 ,  j - w [ i ]]  +  v [ i ]) 
26 
27     valor de retorno  [ i , j ] 28 } 29 30 Ejecutar m ( n , W )


 

Por ejemplo, hay 10 artículos diferentes y el límite de peso es 67. Entonces,

{\ displaystyle {\ begin {alineado} & w [1] = 23, w [2] = 26, w [3] = 20, w [4] = 18, w [5] = 32, w [6] = 27 , w [7] = 29, w [8] = 26, w [9] = 30, w [10] = 27 \\ & v [1] = 505, v [2] = 352, v [3] = 458 , v [4] = 220, v [5] = 354, v [6] = 414, v [7] = 498, v [8] = 545, v [9] = 473, v [10] = 543 \ \\ end {alineado}}}

Si usa el método anterior para calcular $${\ displaystyle m (10,67)}, obtendrá ( excluyendo llamadas que producen m (i, j) = 0 ):

${\displaystyle {\begin{aligned}&m(10,67)=1270\\&m(9,67)=1270,m(9,40)=678\\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\\end{aligned}}}$

Además, podemos romper la recursión y convertirla en un árbol. ¡Entonces podemos cortar algunas hojas y usar la computación paralela para acelerar la ejecución de este método!

Meet-in-the-middle [ editar ]

Otro algoritmo para la mochila 0-1, descubierto en 1974 ^[18] y a veces llamado "encuentro en el medio" debido a paralelos con un algoritmo con un nombre similar en criptografía , es exponencial en el número de elementos diferentes, pero puede ser preferible a el algoritmo DP cuando$${\ displaystyle W}es grande en comparación con n . En particular, si el$${\ displaystyle w_ {i}}no son negativos pero no son enteros, aún podríamos usar el algoritmo de programación dinámica escalando y redondeando (es decir, usando aritmética de punto fijo ), pero si el problema requiere$${\ displaystyle d} dígitos fraccionales de precisión para llegar a la respuesta correcta, $${\ displaystyle W} tendrá que ser escalado por $${\ displaystyle 10 ^ {d}}, y el algoritmo DP requerirá $${\ displaystyle O (W10 ^ {d})} espacio y $${\ displaystyle O (nW10 ^ {d})} hora.

El algoritmo Meet-in-the-middle es 
    entrada: un conjunto de elementos con pesos y valores.
    salida: el mayor valor combinado de un subconjunto.

    particione el conjunto {1 ... n } en dos conjuntos A y B de aproximadamente el mismo tamaño
    calcular los pesos y valores de todos los subconjuntos de cada conjunto

    para cada   subconjunto de  A  , 
        encuentre el subconjunto de B de mayor valor tal que el peso combinado sea menor que W

    realizar un seguimiento del mayor valor combinado visto hasta ahora

El algoritmo toma $${\ displaystyle O (2 ^ {n / 2})} el espacio y las implementaciones eficientes del paso 3 (por ejemplo, ordenar los subconjuntos de B por peso, descartar los subconjuntos de B que pesan más que otros subconjuntos de B de mayor o igual valor y usar la búsqueda binaria para encontrar la mejor coincidencia) resultan en un tiempo de ejecución de $${\ displaystyle O (n2 ^ {n / 2})}. Al igual que con el ataque en el medio en criptografía, esto mejora en el$${\ displaystyle O (n2 ^ {n})} tiempo de ejecución de un enfoque ingenuo de fuerza bruta (examinando todos los subconjuntos de $${\ displaystyle \ {1 ... n \}}), a costa de utilizar un espacio exponencial en lugar de constante (ver también paso gigante ).

Algoritmos de aproximación [ editar ]

Como para la mayoría de los problemas con NP completo, puede ser suficiente encontrar soluciones viables incluso si no son óptimas. Preferiblemente, sin embargo, la aproximación viene con una garantía sobre la diferencia entre el valor de la solución encontrada y el valor de la solución óptima.

Al igual que con muchos algoritmos útiles pero computacionalmente complejos, se ha realizado una investigación sustancial sobre la creación y el análisis de algoritmos que se aproximan a una solución. El problema de la mochila, aunque NP-Hard, es uno de una colección de algoritmos que aún se pueden aproximar a cualquier grado específico. Esto significa que el problema tiene un esquema de aproximación de tiempo polinómico. Para ser exactos, el problema de la mochila tiene un esquema de aproximación de tiempo completamente polinomial (FPTAS). ^[19]

Algoritmo de aproximación codicioso [ editar ]

George Dantzig propuso un algoritmo de aproximación codicioso para resolver el problema de la mochila sin límites. ^[20] Su versión clasifica los artículos en orden decreciente de valor por unidad de peso,$${\ displaystyle v_ {i} / w_ {i}}. Luego procede a insertarlos en el saco, comenzando con la mayor cantidad posible de copias del primer tipo de elemento hasta que ya no haya espacio en el saco para más. Siempre que haya un suministro ilimitado de cada tipo de artículo, si$${\ displaystyle m} es el valor máximo de los elementos que caben en el saco, entonces el codicioso algoritmo garantiza al menos un valor de $${\ displaystyle m / 2}. Sin embargo, para el problema limitado, donde el suministro de cada tipo de artículo es limitado, el algoritmo puede estar lejos de ser óptimo.

Esquema de aproximación de tiempo completamente polinomial [ editar ]

El esquema de aproximación de tiempo completamente polinomial (FPTAS) para el problema de la mochila aprovecha el hecho de que la razón por la cual el problema no tiene soluciones de tiempo polinomial conocidas es porque los beneficios asociados con los artículos no están restringidos. Si se redondean algunos de los dígitos menos significativos de los valores de ganancia, entonces estarán delimitados por un polinomio y 1 / ε donde ε es un límite en la corrección de la solución. Esta restricción significa que un algoritmo puede encontrar una solución en el tiempo polinomial que sea correcta dentro de un factor de (1-ε) de la solución óptima. ^[19]

algoritmo FPTAS es  
    entrada: ε ∈ (0,1]
            una lista A de n elementos, especificados por sus valores, $${\ displaystyle v_ {i}}
  
, y pondera
     salida: S 'la solución FPTAS

    P: = max $${\ displaystyle \ {v_ {i} \ mid 1 \ leq i \ leq n \}}
  
  // el valor más alto del artículo
    K: = ε $${\ displaystyle {\ frac {P} {n}}}
  


    para i de 1 a n do
        $${\ displaystyle v '_ {i}}
  
 : = $${\ displaystyle \ left \ lfloor {\ frac {v_ {i}} {K}} \ right \ rfloor}
  

    fin de

    devuelva la solución, S ', usando el$${\ displaystyle v '_ {i}}
  
 valores en el programa dinámico descrito anteriormente

Teorema: el conjunto$${\ displaystyle S '} calculado por el algoritmo anterior satisface $${\ displaystyle \ mathrm {profit} (S ') \ geq (1- \ varepsilon) \ cdot \ mathrm {profit} (S ^ {*})}, dónde $${\ displaystyle S ^ {*}} Es una solución óptima.

Relaciones de dominación [ editar ]

Resolver el problema de la mochila sin límites puede hacerse más fácil al tirar los artículos que nunca serán necesarios. Para un artículo determinado$${\ displaystyle i}, supongamos que pudiéramos encontrar un conjunto de artículos $${\ displaystyle J} tal que su peso total es menor que el peso de $${\ displaystyle i}, y su valor total es mayor que el valor de $${\ displaystyle i}. Luego$${\ displaystyle i} no puede aparecer en la solución óptima, porque siempre podríamos mejorar cualquier solución potencial que contenga $${\ displaystyle i} por reemplazo $${\ displaystyle i} con el conjunto $${\ displaystyle J}. Por lo tanto, podemos ignorar el$${\ displaystyle i}-th ítem por completo. En esos casos,$${\ displaystyle J}se dice que domina $${\ displaystyle i}. (Tenga en cuenta que esto no se aplica a problemas de mochila limitados, ya que es posible que ya hayamos agotado los elementos en$${\ displaystyle J}.)

Encontrar relaciones de dominio nos permite reducir significativamente el tamaño del espacio de búsqueda. Hay varios tipos diferentes de relaciones de dominio , ^[11] el cual toda satisface una desigualdad de la forma:

$${\ displaystyle \ qquad \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq \ alpha \, w_ {i}}y $${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq \ alpha \, v_ {i} \,} para algunos $${\ displaystyle x \ en Z _ {+} ^ {n}}

dónde $${\ displaystyle \ alpha \ en Z _ {+} \ ,, J \ subsetneq N} y $${\ displaystyle i \ not \ in J}. El vector$${\ displaystyle x} denota el número de copias de cada miembro de $${\ displaystyle J}.

Dominio colectivo

los $${\ displaystyle i}-th elemento está dominado colectivamente por$${\ displaystyle J}, Escrito como $${\ displaystyle i \ ll J}, si el peso total de alguna combinación de elementos en $${\ displaystyle J}es menor que w _i y su valor total es mayor que v _i . Formalmente,$${\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq w_ {i}} y $${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq v_ {i}} para algunos $${\ displaystyle x \ en Z _ {+} ^ {n}}es decir $${\ displaystyle \ alpha = 1}. Verificar este dominio es computacionalmente difícil, por lo que solo se puede usar con un enfoque de programación dinámica. De hecho, esto es equivalente a resolver un problema de decisión de mochila más pequeño donde$${\ displaystyle V = v_ {i}}, $${\ displaystyle W = w_ {i}}, y los artículos están restringidos a $${\ displaystyle J}.

Umbral de dominación

los $${\ displaystyle i}-el elemento es el umbral dominado por$${\ displaystyle J}, Escrito como $${\ displaystyle i \ prec \ prec J}, si alguna cantidad de copias de $${\ displaystyle i} están dominados por $${\ displaystyle J}. Formalmente,$${\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq \ alpha \, w_ {i}}y $${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq \ alpha \, v_ {i} \,} para algunos $${\ displaystyle x \ en Z _ {+} ^ {n}} y $${\ displaystyle \ alpha \ geq 1}. Esta es una generalización del dominio colectivo, introducida por primera vez en ^[13] y utilizada en el algoritmo EDUK. El más pequeño tal$${\ displaystyle \ alpha}define el umbral del artículo$${\ displaystyle i}escrito $${\ displaystyle t_ {i} = (\ alpha -1) w_ {i}}. En este caso, la solución óptima podría contener como máximo$${\ displaystyle \ alpha -1} Copias de $${\ displaystyle i}.

Dominio múltiple

los $${\ displaystyle i}-el elemento está dominado por un solo elemento$${\ displaystyle j}, Escrito como $${\ displaystyle i \ ll _ {m} j}, Si $${\ displaystyle i} está dominado por cierto número de copias de $${\ displaystyle j}. Formalmente,$${\ displaystyle w_ {j} \, x_ {j} \ \ leq w_ {i}}y $${\ displaystyle v_ {j} \, x_ {j} \ \ geq v_ {i}} para algunos $${\ displaystyle x_ {j} \ en Z _ {+}} es decir $${\ displaystyle J = \ {j \}, \ alpha = 1, x_ {j} = \ lfloor {\ frac {w_ {i}} {w_ {j}}} \ rfloor}. Este dominio podría usarse eficientemente durante el preprocesamiento porque puede detectarse con relativa facilidad.

Dominio modular

Dejar $${\ displaystyle b}ser el mejor elemento , es decir$${\ displaystyle {\ frac {v_ {b}} {w_ {b}}} \ geq {\ frac {v_ {i}} {w_ {i}}} \,} para todos $${\ displaystyle i}. Este es el artículo con la mayor densidad de valor. los$${\ displaystyle i}-th elemento está modularmente dominado por un solo elemento$${\ displaystyle j}, Escrito como $${\ displaystyle i \ ll _ {\ equiv} j}, Si $${\ displaystyle i} está dominado por $${\ displaystyle j} más varias copias de $${\ displaystyle b}. Formalmente,$${\ displaystyle w_ {j} + tw_ {b} \ leq w_ {i}}y $${\ displaystyle v_ {j} + tv_ {b} \ geq v_ {i}} es decir $${\ displaystyle J = \ {b, j \}, \ alpha = 1, x_ {b} = t, x_ {j} = 1}.

Variaciones [ editar ]

Artículo principal: Lista de problemas de mochila

Existen muchas variaciones del problema de la mochila que han surgido de la gran cantidad de aplicaciones del problema básico. Las principales variaciones se producen al cambiar el número de algunos parámetros problemáticos, como el número de elementos, el número de objetivos o incluso el número de mochilas.

Problema de mochila de objetivos múltiples [ editar ]

Esta variación cambia el objetivo del individuo que llena la mochila. En lugar de un objetivo, como maximizar la ganancia monetaria, el objetivo podría tener varias dimensiones. Por ejemplo, podría haber preocupaciones ambientales o sociales, así como objetivos económicos. Los problemas que se abordan con frecuencia incluyen optimizaciones de cartera y logística de transporte. ^[21] [22]

Como ejemplo, supongamos que maneja un crucero. Tienes que decidir cuántos comediantes famosos contratar. Este bote no puede manejar más de una tonelada de pasajeros y los artistas deben pesar menos de 1000 lbs. Cada comediante tiene un peso, genera negocios en función de su popularidad y solicita un salario específico. En este ejemplo, tienes múltiples objetivos. Desea, por supuesto, maximizar la popularidad de sus artistas mientras minimiza sus salarios. Además, desea tener tantos artistas como sea posible.

Problema de mochila multidimensional [ editar ]

En esta variación, el peso del artículo de la mochila $${\ displaystyle i} está dado por un vector D-dimensional $${\ displaystyle {\ overline {w_ {i}}} = (w_ {i1}, \ ldots, w_ {iD})} y la mochila tiene un vector de capacidad D-dimensional $${\ displaystyle (W_ {1}, \ ldots, W_ {D})}. El objetivo es maximizar la suma de los valores de los artículos en la mochila para que la suma de los pesos en cada dimensión$${\ displaystyle d} no excede $${\ displaystyle W_ {d}}.

La mochila multidimensional es computacionalmente más difícil que la mochila; incluso para$${\ displaystyle D = 2}, el problema no tiene EPTAS a menos que P$${\ displaystyle =}NOTARIO PÚBLICO. ^[23] Sin embargo, se muestra que el algoritmo en ^[24] resuelve instancias dispersas de manera eficiente. Una instancia de mochila multidimensional es escasa si hay un conjunto$${\ displaystyle J = \ {1,2, \ ldots, m \}} para {\ displaystyle m  tal que por cada artículo de mochila $${\ displaystyle i}, {\ displaystyle \ existe z> m} tal que $${\ displaystyle \ forall j \ in J \ cup \ {z \}, \ w_ {ij} \ geq 0} y $${\ displaystyle \ forall y \ notin J \ cup \ {z \}, w_ {iy} = 0}. Tales instancias ocurren, por ejemplo, cuando se programan paquetes en una red inalámbrica con nodos de retransmisión. ^[24] El algoritmo de ^[24] también resuelve instancias dispersas de la variante de opción múltiple, mochila multidimensional de opción múltiple.

El algoritmo IHS (Estante de altura creciente) es óptimo para la mochila 2D (cuadrados de empaque en un cuadrado de tamaño de unidad bidimensional): cuando hay como máximo cinco cuadrados en un empaque óptimo. ^[25]

Problema de mochila múltiple [ editar ]

Esta variación es similar al problema del embalaje del contenedor . Se diferencia del problema de embalaje de la papelera en que se puede seleccionar un subconjunto de artículos, mientras que, en el problema de embalaje de la papelera, todos los artículos deben empaquetarse en ciertas papeleras. El concepto es que hay múltiples mochilas. Esto puede parecer un cambio trivial, pero no es equivalente a aumentar la capacidad de la mochila inicial. Esta variación se utiliza en muchos problemas de carga y programación en la Investigación de operaciones y tiene un esquema de aproximación de tiempo polinómico . ^[26]

Problema de mochila cuadrática [ editar ]

Según lo descrito por Wu et al .:

El problema de la mochila cuadrática (QKP) maximiza una función objetivo cuadrática sujeta a una restricción de capacidad binaria y lineal. ^[27]

El problema de la mochila cuadrática fue discutido bajo ese título por Gallo, Hammer y Simeone en 1980. ^[28] Sin embargo, Gallo y Simeone ^[29] atribuyen el primer tratamiento del problema a Witzgall ^[30] en 1975.

Problema de suma de subconjuntos [ editar ]

El problema de la suma de subconjuntos es un caso especial de la decisión y problemas de 0-1 donde cada tipo de elemento, el peso es igual al valor:$${\ displaystyle w_ {i} = v_ {i}}. En el campo de la criptografía , el término problema de mochila se usa a menudo para referirse específicamente al problema de la suma de subconjuntos y se conoce comúnmente como uno de los 21 problemas completos de NP de Karp . ^[31]

La generalización del problema de suma de subconjuntos se denomina problema de suma de subconjuntos múltiples, en el que existen varios contenedores con la misma capacidad. Se ha demostrado que la generalización no tiene un FPTAS.