Algoritmo de minimización del carrito de la compra

Question

Tengo una lista de products, que consiste en la lista de shops, que lo vendió.

{ 
    'Book A': [ShopA, ShopB, ShopC], 
    'Book B': [ShopC, ShopD], 
    'Movie C': [ShopA, ShopB, ShopD, ShopE], 
    ... 
} 

(precio difiere entre las tiendas)

Cada tienda es también tiene un coste de envío. Es un costo de envío "por pedido", no importa cuántos artículos hay en mi carrito. Y también difiere entre las tiendas.

Ej: si compro "libro A" de Shópa, "Libro B" de ShopC y "Cine C" de Shópa, el precio resultante es: Book A price in ShopA + Book B price in ShopC + Movie C price in ShopA + ShopC shipping cost + ShopA shipping cost

Si el costo de envío era cero o era por artículo y constante, entonces simplemente ordenaría las listas de ofertas por el campo price+shipping y obtendría el primer resultado de cada conjunto.

Necesito comprar todos los artículosvez y encontrar el precio mínimo y el conjunto resultante.

No soy muy bueno con los algoritmos de optimización y la programación dinámica, así que necesito una solución o simplemente un guiño en la dirección correcta.

Answer 1

Con tan pocos artículos, tengo una solución. Es dinámico

Procesaremos cada tienda de manera iterativa. En cada paso almacenamos el mejor precio actual con el que podemos cubrir todos los subconjuntos de artículos. Al principio, todos ellos son infinity en precio, excepto el subconjunto vacío que es 0 de precio. Tenga en cuenta que todos los subconjuntos son 2^Num_products en el recuento pero en su caso estos son sólo alrededor de 1000.

Ahora, ¿cómo procesar el siguiente para seguir tienda: Tenga en cuenta que cubre cada subconjunto de los productos con esta tienda (me refiero a que subconjunto la tienda puede proporcionar) y todo el resto de los productos están cubiertos por tiendas que ya observó, mejorando así los costos mínimos de cobertura de cada subconjunto. Este paso lleva 2^Num_products*2^Num_products=4^Num_products, todavía alrededor de un millón, que es aceptable. Usted hace esto para cada tienda y al final la respuesta es el costo de cubrir todos los elementos. La complejidad total de la solución propuesta es 4^Num_products * num_shops, que es de aproximadamente 50 millones, lo que está bien.

Tenga en cuenta que esto sigue siendo exponencial y esto no es sorprendente. Gracias a amit por su increíble prueba de NP.

EDITAR Adición de una explicación más detallada del algoritmo en pseudocódigo:

init: 
cost[subset] = infi 
cost[{}] = 0 
for shop in shops 
new_prices = costs.dup() 
for set : subsets 
    for covered_set : all_subsets(set) 
    price = covered_set == {} ? 0 : delivery[shop] 
    remaining = set 
    for element : covered_set 
     if shop do not sale element 
     break for, choose next covered_set 
     price += el_price[element] 
     remaining.remove(element) 
    price += costs[remaining] 
    new_prices[set] = min(new_prices[set], price) 
costs = new_prices 
return costs[all] 

Nota que aquí utilizo conjuntos como índice - esto se debe a que en realidad uso la representación máscara de bits de los subconjuntos por ejemplo 1101 es un subconjunto que contiene el 1º, 2º y el cuarto elemento. Por lo tanto, una iteración de todos los conjuntos es for (int i = 0; i < (1 << n); i++).

También hay una cosa más: si quieres ciclo de todos los subconjuntos de un subconjunto S que realmente puede hacerlo más rápido que la iteración de todos los subconjuntos del conjunto inicial y comprobar si el subconjunto es subconjunto de S. Si S también se representa con la máscara de bits bit_mask, esto para el ciclo hace el trabajo: for(int i = bit_mask; i > 0; i = (i - 1) & bitmask). Al usar este enfoque, disminuye la complejidad del algoritmo a 3^Num_products * num_shops. Sin embargo, esto es un poco más difícil de entender y probablemente necesites escribir a mano un ejemplo para asegurarte de que el ciclo que escribí en realidad cicla todos los subconjuntos de S. Sobre la complejidad, solo confía en mí.

EDIT2 Editado el estado de ruptura.También permítanme detallar el conjunto remaining y su cálculo: como dmzkrsk señaló que el pseudocódigo menciona la eliminación del conjunto, pero en realidad solo puede asignar remaining = set^covered_set (operación de bit nuevamente) en caso de usar máscaras de bits para representar los subconjuntos.

Answer 2

Este problema es NP Hard.
Mostraremos una reducción desde Hitting Set problem.
Golpear conjunto de problemas: Dada conjuntos S1,S2,...,Sn y un número k: selecciona una serie de S de tamaño k, tal que para cada Si hay un elemento s en S tal que es s en Si. [definición alternativa: la intersección entre cada Si y S no está vacía].

reducción:
Dada una instancia de golpear conjunto, en forma de (S1,...,Sn,k) crear una instancia de este problema:

All books cost nothing. In order to buy from each store you pay 1. 
The book i is sold by each store denoted in Si, minimal price for this instance is k. 

prueba:
Golpear Set -> Este problema : Suponga que hay un conjunto mínimo de golpes en (S1,...,Sn) del tamaño k. Deje que este conjunto de golpes sea S. Al comprar en cada tienda en S, podemos comprar todos nuestros libros al costo k, ya que los libros no cuestan nada [en nuestra construcción], y compramos todos los libros, y pagamos por el pedido en las tiendas exactamente k, por lo tanto, el precio total fue k.
Este problema -> Golpe conjunto: Suponga que hay un precio de k para el problema en la pregunta. Luego, desde la construcción del problema, y ​​dado que los libros no cuestan nada, tenemos que comprar en k diferentes tiendas para obtener todos los libros. Deje que estas tiendas sean S.Desde la construcción del problema, S es un conjunto de golpes para (S1,...,Sn)
Q.E.D.

Conclusión:
Por lo tanto, este problema "no es más fácil que" Golpear conjunto de problemas, y no hay una solución polinómica conocida para este problema, por lo que - su mejor tiro, si quieres solución óptima, es probablemente una exponencial, como backtracking [Verifique todas las posibilidades y devuelva la solución mínima].

Answer 3

Una buena heurística puede ser la optimización de la colonia de hormigas. Lo uso para resolver el problema del vendedor de viajes. Puede encontrar un ejemplo de trabajo de google tsp solver. Es una biblioteca de JavaScript que también utiliza una fuerza bruta y una solución de programación dinámica. El AOC se usa cuando tiene más ciudades para calcular el límite actual de 20 ciudades. Creo que puede usar la biblioteca para resolver su problema y solo necesita una pequeña reescritura. ¡Con 20 ciudades, el programa debe verificar 20! posibilites. En tu caso, es un poco más ligero, pero tal vez solo de una magnitud.

Answer 4

He tratado este problema exacto una vez. No encontré ninguna otra solución aparte de probar todas las combinaciones posibles de tiendas, pero hay una manera fácil de filtrar muchas de las tiendas en cada producto.

1. Calcule el precio más bajo (costo de envío incluido) de cada producto, llámenos best_price.

2. En cada producto, conservar únicamente las tiendas donde el precio de la tienda (sin gastos de envío) < = best_price (con coste de envío)

3. Prueba todas las combinaciones posibles de las tiendas para la más barato