Cómo optimizar el producto cartesiano

7

¿Hay una mejor manera de calcular el producto cartesiano? Dado que el producto cartesiano es un caso especial que difiere en cada caso. Creo que necesito explicar lo que necesito lograr y por qué termino haciendo un producto cartesiano. Por favor, ayúdeme si el producto cartesiano es la única solución para mi problema. Si es así, cómo mejorar el rendimiento.

Fondo:

Estamos tratando de ayudar a los clientes a comprar productos más baratos.

Digamos que el cliente ha pedido 5 productos (prod1, prod2, prod3, prod4, prod5).

Cada producto pedido ha sido ofrecido por diferentes proveedores.

Formato de representación1:

Proveedor1: ofrece prod1, prod2, prod4

vendor2 - ofrece prod1, prod5

vendor3 - ofrece prod1, prod2, prod5

vendor4 - ofrece prod1

vendor5 - ofrece prod2 vendor6 - ofrece prod3, prod4

En otras palabras

Formato de representación2:

Prod1: ofrecido por vendor1, vendor2, vendor3, vendor4

Prod2: ofrecido por vendor5, vendor3, vendor1

prod3 - ofrecido por vendor6

prod4: ofrecido por vendor1, vendor6

prod5: ofrecido por vendor3, vendor2

Ahora para elegir el mejor vendedor basado en el precio. Podemos ordenar los productos por precio y tomar el primero.

En ese caso elegimos

prod1 from vendor1

prod2 from vendor5

prod3 from vendor6

prod4 from vendor1

prod5 from vendor3

Complejidad:

ya que elegimos 4 proveedores únicos, debemos pagar 4 precios de envío.

También cada proveedor tiene una orden de compra mínima. Si no nos reunimos, también terminamos pagando ese cargo.

Para elegir la mejor combinación de producto. Tenemos que hacer el producto cartesiano de los productos ofrecidos para calcular el precio total.

total price computation algorithm:

foreach unique vendor 
if(sum(product price offered by specific vendor * quantity)<minimum purchase order limit specified by specific vendor)
totalprice +=sum(product price * quantity) + minimum purchase charge + shipping price
else
totalprice +=sum(product price * quantity) + shipping price
end foreach

En nuestro caso

{vendor1, vendor2, vendor3, vendor4}

{vendor1, vendor3, vendor5}

{vendor6}

{vendor1, vendor6}

{vendor2, vendor3}

La combinación de 4 * 3 * 1 * 2 * 2 = 48 debe calcularse para encontrar la mejor combinación.

{vendor1, vendor1, vendor6, vendor1, vendor2} = totalprice1,

{vendor1, vendor3, vendor6, vendor1, vendor2} = totalprice2,

.

.

{vendor4, vendor5, vendor6, vendor6, vendor3} = totalprice48

Ahora ordene el precio total calculado para encontrar la mejor combinación.

Problema real:

Si el cliente solicita más de 15 productos. Supongamos que cada producto ha sido ofrecido por 8 proveedores exclusivos, luego terminamos calculando 8 ^ 15 = 35184372088832 combinación. Lo que lleva más de un par de horas. Si el cliente solicita más de 20 productos, tardará más de un par de días.

¿Existe una solución para abordar este problema en un ángulo diferente?

    
pregunta Esen 25.04.2012 - 17:57

1 respuesta

2

Su problema está en la misma categoría que el famoso "problema del vendedor ambulante". Encontrar la mejor solución será muy costoso con un número creciente de proveedores y productos. Puede intentar implementar un algoritmo de seguimiento que intente recortar el espacio de la solución lo antes posible.

Algunas ideas son:

  1. Comience con el "mayor costo" = max (cantidad * min (precio))
  2. Intente minimizar el número de proveedores (= > intente obtener más productos de un proveedor que ya esté en la lista)
  3. agregue una solución si todos los artículos están ordenados
  4. rompa y regrese si la suma total actual es mayor que su mejor resultado
  5. ...
respondido por el mrab 25.04.2012 - 18:24

Lea otras preguntas en las etiquetas