0/1 mochila con peso del artículo dependiente?
La mochila estándar 0/1 requiere que el peso de cada artículo sea independiente de los demás. Entonces DP es un algoritmo eficiente hacia la solución. Pero ahora me encontré con un similar pero extensiones de este problema, que
El peso de los nuevos elementos depende de los elementos anteriores que ya están en mochila.
Por ejemplo, tenemos 5 elementos a, b, c, d y e con peso w_a, ..., w_e. elemento b y c tienen peso dependencia.
Cuando b ya está en la mochila, el peso del elemento c se más pequeño de w_c porque puede compartir espacio con b, es decir, weight(b&c) < w_b + w_c. Simétricamente, cuando c ya está en la mochila, el peso de b será menor que w_b.
Esta incertidumbre resulta en un fallo del algoritmo DP original, ya que depende de la corrección de iteraciones anteriores que pueden no corregirse ahora. He leído algunos periódicos sobre mochila, pero ellos o bien tienen dependencias sujetas a ganancias (problema de mochila cuadrática), o tienen peso variable que sigue una distribución aleatoria ( problema de mochila estocástica). También tengo conocimiento de la pregunta anterior Variación de Mochila 1/0 con Bordes ponderados , pero solo hay una respuesta muy genérica disponible, y ninguna respuesta sobre cuál es el nombre de esta mochila.
Una solución existente:
También he leído uno solución aproximada en un documento sobre las optimizaciones de DBMS, donde group the related items as one combined item for knapsack. Si se utiliza esta técnica en nuestro ejemplo, los elementos para mochila serán a, bc, d, e, por lo tanto, no hay más dependencias entre dos de estos cuatro elementos. Sin embargo, es fácil construir un ejemplo que no obtiene un resultado óptimo, como cuando an item with "small weight and benefit" is grouped with another item with "large weight and benefit". En este ejemplo, el elemento" pequeño "no debe seleccionarse en solución, sino que se selecciona junto con el elemento" grande" elemento.
Pregunta:
¿Hay algún tipo de técnicas de resolución eficientes que puedan obtener un resultado óptimo, o al menos con alguna garantía de error? ¿O estoy tomando la dirección equivocada para modelar este problema?
3 answers
¿No podrías tener artículos a, b, c, bc, d y e? Posiblemente con una restricción que b y bc no pueden ser ambos en la mochila y de manera similar con c y bc? Mi entendimiento es que esa sería una solución correcta ya que cualquier solución que tenga b y c puede mejorarse sustituyendo ambas por bc (por definición). Las limitaciones a la membresía deben hacerse cargo de cualquier otro caso.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-08-11 14:33:40
Este es un problema muy interesante y he estado trabajando en esto durante un tiempo. Lo primero a considerar es que el problema de la mochila binaria con los pesos/valor de los elementos dependientes no es trivial en absoluto. Puede considerar el uso de redes bayesianas, modelos de Markov y otras técnicas similares para resolver este problema. Sin embargo, cualquier enfoque práctico a este problema tiene que hacer algunas suposiciones ya sea sobre el modelo de optimización o su entrada. Aquí hay un ejemplo de la formulación del binario problema de mochila con elementos dependientes del valor. https://arxiv.org/pdf/1702.06662.pdf
En este trabajo, los autores han propuesto modelar la entrada (dependencias relacionadas con el valor) utilizando gráficos difusos y luego utilizando el modelo de programación lineal de enteros propuesto para resolver el problema de optimización. Se ha aceptado la publicación de una versión ampliada de la obra, que pronto estará disponible en línea.
Por favor, no dude en ponerse en contacto conmigo si necesita más información. También puedo proporcionarle el código fuente del modelo si es necesario.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-14 07:58:08
Al final logré resolver el problema con el método B&B propuesto por @Holt. Aquí está la configuración clave:
(0) Antes de ejecutar el algoritmo B&B, agrupar todos los elementos depende de su dependencia. Todos los elementos de una partición tienen dependencia de peso con todos los demás elementos del mismo grupo, pero no con los elementos de otros grupos.
Ajustes para B & B:
(1) Límite superior: asumir que el elemento actual tiene el peso mínimo , es decir, asumir todas las dependencias existir.
(2) Límite inferior: suponga que el elemento actual tiene el peso máximo, es decir, asuma que no existen todas las dependencias.
(3) Peso actual: Calcule el peso actual real.
Todos los cálculos anteriores se pueden hacer en un tiempo lineal jugando con los grupos que obtenemos en el paso 0. Específicamente, al obtener esos pesos, escanear solo los elementos en el grupo actual (el grupo en el que se encuentra el elemento actual) es suficiente : los elementos en otros grupos no tienen dependencias con la actual, por lo que no cambiará el peso real del elemento actual.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-08-04 14:52:17