algoritmo para encontrar la combinación óptima de productos y tiendas para minimizar el costo

Hola Stackoverflow personas,algoritmo para encontrar la combinación óptima de productos y tiendas para minimizar el costo

que corren un sitio que encuentra sus usuarios el lugar más barato para comprar libros. Esto es fácil para un solo libro, pero para libros múltiples a veces puede ser más barato comprar un libro en una tienda y otro libro de otra tienda.

Actualmente encuentro la tienda más barata que vende todos los libros en la lista de usuarios, pero quiero tener un sistema más inteligente. Aquí hay algo más de información:

El precio de un libro es constante para una tienda.
El precio del envío puede variar, dependiendo del número de libros o el valor total de los libros.
Cada objeto de tienda puede tomar una variedad de libros y devolver el costo de envío.
Con frecuencia, no todas las tiendas venden todos los libros.

No estoy seguro si es genial para acceder a mi sitio aquí, pero aparece en mi perfil de usuario.

Me gustaría poder encontrar la combinación más barata de tiendas y libros.

Me temo que requiere un enfoque de fuerza bruta, y con 35 tiendas, el número de combinaciones será enorme para una cantidad modesta de libros. Tengo la sensación de que el número de combinaciones es (# talleres)^(# libros) - pero no 100%

La pregunta es, ¿qué enfoque debo usar? ¿Encaja este problema en una clase conocida de problemas? Si se requiere fuerza bruta, ¿cuál es una buena forma de hacer esto en Ruby y puedo priorizar tiendas para probar primero?

Fuente

2010-01-08 dkam

Desafortunadamente, este es un ejemplo de un problema de optimización combinatoria que no tiene una solución fácil. Tienes razón de que realmente lo haces, en general, necesitas un enfoque de fuerza bruta. ¡Sin embargo! Sospecho que hay una estructura especial en este problema que ayudará. Por ejemplo, el costo de envío no cambiará aleatoriamente a medida que cambie la combinación de libros; probablemente aumentará sub-linealmente y/o se saturará a medida que agrega libros.

Aquí es lo que recomiendo, entonces:

Desconectado, estimo las políticas de envío de cada tienda, por lo que, dada libros (y quizás sus pesos) se puede estimar el costo de envío de sin refiriéndose a sus sitios.
Para cada tienda, calcule cuánto costaría cada libro, si está disponible.
Sin conexión, acceda a cada tienda o conjunto de tiendas y calcule, utilizando sus políticas de envío fuera de línea, cuánto costará el total.
Elija la tienda (o tiendas) con el costo más barato. Si hay varios que son similares, calcule la respuesta exacta.

Eso debería comenzar, y le impedirá hacer una búsqueda completa.

Fuente

2010-01-08 05:13:15 Peter

Hola, gracias por la respuesta. 1-3 ya están en su lugar. Un método por tienda se utiliza para determinar el costo de envío. Una de las dificultades es que el valor de envío puede determinarse por el número de libros o el precio total del pedido, lo que hace que la vida sea un poco compleja. Determinar qué tienda individual envía todos los libros al menor costo es fácil, es descubrir que uno de los libros debe comprarse en la tienda A, mientras que el resto debe comprarse en la tienda B. – dkam

Brute Force casi siempre puede ser reemplazado por una buena heurística, es decir, un algoritmo que se sabe que funciona de manera no óptima pero "suficientemente buena".

Aunque no estoy 100% seguro, supongo que se relaciona con el Knapsack problem que es (como se supone que todos debemos ahora jaja ..) NP-completo.

¡No tengo nada mejor que ofrecer en este momento, pero buena suerte!

Fuente

2010-01-08 05:14:14 moritz

Esta es una variación de lo que se llama clásicamente el "Problema de asignación". El AP clásico tiene algunas soluciones estándar, incluido el algoritmo Munkres (también conocido como "húngaro") y el algoritmo JVC (Junker Volgenant Castanon iirc).

La idea básica es calcular el costo de cada tarea (es decir, el costo de comprar cada libro en cada tienda) y luego seleccionar el conjunto de tareas que minimiza el costo total. Esto se puede hacer en tiempo polinomial, creo.

El hecho de que el costo de envío de cada vendedor dependa del pedido total hace que las cosas sean mucho más complicadas. Es posible que pueda utilizar un enfoque híbrido que no tenga en cuenta los costos de envío originalmente, luego lo hace para agregar pedidos una vez que haya identificado algunas asignaciones prometedoras.

¡Buena suerte, suena como un problema divertido!

Fuente

2010-01-08 05:15:20

Intente utilizar el enfoque de programación dinámica. Puede leer al respecto aquí: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg También puede leer sobre esto en la wikipedia o en el libro "Introducción a los algoritmos" (Cormen).

Es un problema bastante estándar.

Fuente

2010-01-08 05:16:15 Hypuk