algorithm - ruta - ¿Mochila 0/1 con peso dependiente del artículo?
problema de la mochila caracteristicas (3)
¿No podría tener los elementos a , b , c , bc , d y e ? Posiblemente con una restricción de que b y bc no pueden estar tanto en la mochila como 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 c puede mejorarse sustituyendo ambas por bc (por definición). Las restricciones en la membresía deben hacerse cargo de cualquier otro caso.
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 artículos depende de los elementos anteriores que ya se encuentran en la mochila.
Por ejemplo , tenemos 5 elementos a , b , c , d y e con peso w_a , ..., w_e . El artículo b y c tienen dependencia de peso.
Cuando b ya está en la mochila, el peso del artículo c será menor que w_c porque puede compartir algo de espacio con b , es decir, el 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 da como resultado una falla del algoritmo DP original, ya que depende de la corrección de las iteraciones anteriores que pueden no ser correctas ahora. He leído algunos artículos sobre mochila, pero tienen dependencias sujetas a beneficios ( problema de mochila cuadrática ) o tienen un peso variable que sigue una distribución aleatoria ( problema de mochila estocástica ). También tengo conocimiento de la pregunta anterior 1/0 Variación de mochila con bordes ponderados , pero solo hay una respuesta muy genérica disponible, y no hay respuesta sobre cuál es el nombre de esta mochila.
Una solución existente:
También he leído una solución aproximada en un artículo sobre optimizaciones de DBMS, donde group the related items as one combined item for knapsack . Si usamos esta técnica en nuestro ejemplo, los artículos 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 obtenga 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 la solución, sino que se selecciona junto con el elemento "grande".
Pregunta:
¿Existe algún tipo de técnica de solución eficiente que pueda obtener un resultado óptimo, o al menos con alguna garantía de error? ¿O estoy tomando la dirección equivocada para modelar este problema?
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 en una partición tienen dependencia de peso con todos los demás elementos en el mismo grupo, pero no con elementos en otros grupos.
Ajustes para B&B:
(1) Límite superior: suponga que el elemento actual tiene el peso mínimo , es decir, suponga que existen todas las dependencias.
(2) Límite inferior: suponga que el elemento actual tiene el peso máximo , es decir, suponga 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, basta con escanear solo los elementos del grupo actual (el grupo en el que se encuentra el elemento actual): elementos en otros grupos no tienen dependencias con la actual, por lo que no cambiará el peso real del elemento actual.
Este es un problema muy interesante y he estado trabajando en esto por un tiempo. Lo primero que hay que tener en cuenta es que el problema de la mochila binaria con el valor / peso de los elementos dependientes no es en absoluto trivial. Puede considerar el uso de redes bayesianas, modelos de Markov y otras técnicas similares para resolver este problema. No obstante, cualquier enfoque práctico de este problema tiene que hacer algunas suposiciones sobre el modelo de optimización o su entrada. Este es un ejemplo de la formulación del problema de la mochila binaria 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 usar el modelo de programación lineal de enteros propuesto para resolver el problema de optimización. Una versión extendida del trabajo ha sido aceptada para publicación y 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.