algorithm - truco - ¿Cómo encontrar el mejor precio para una baraja de cartas coleccionables?

materiales para imprimir cartas de yugioh (8)

¡Interesante pregunta! :)

Entonces, si tenemos n tarjetas y m proveedores, el enfoque de fuerza bruta debería verificar hasta n ^ m combinaciones, cierto (un poco menos, ya que no todos los proveedores tienen cada tarjeta, pero supongo que eso no importa en la gran esquema de cosas;).

Supongamos por un segundo que cada proveedor tiene cada tarjeta y luego veamos cómo cambian las cosas si no lo hacen.

Encuentre la solución de un solo proveedor más barata.
Ordene las tarjetas por precio, encuentre la tarjeta más cara que es más barata en otro proveedor.
para todas las tarjetas del proveedor 1, muévalas al proveedor 2 si son más baratas allí.
Si el agregado del proveedor 2 no hace que el pedido sea más barato, deshacer y terminar, de lo contrario, repita desde el paso 2

Entonces, si un proveedor no tiene todas las tarjetas, debe comenzar con una situación de múltiples proveedores. Para cada proveedor, puede comenzar comprando todas las tarjetas que existen allí, y luego aplicar el algoritmo a las tarjetas restantes.

Obviamente, es posible que no pueda explotar todas las sutilezas en los precios con este método. Pero si asumimos que una gran parte de las diferencias de precio están compuestas por tarjetas individuales de alto precio, creo que puede encontrar una solución razonable de esta manera.

Ok, después de escribir todo esto, me di cuenta de que el supuesto n ^ m es realmente incorrecto. Una vez que haya elegido un conjunto de proveedores para comprar, simplemente puede elegir el proveedor más barato para cada tarjeta. Esta es una gran ventaja porque las opciones individuales de dónde comprar cada tarjeta no interfieren entre sí.

¿Qué significa esto para nuestro problema? Desde el primer momento, significa que la selección de distribuidores es el problema (en términos de complejidad computacional), no la asignación individual de sus opciones de compra. Así que en lugar de n ^ m, tienes 2 ^ m configuraciones posibles en el peor de los casos. Entonces, lo que necesitamos es una heurística para elegir proveedores en lugar de elegir tarjetas individuales. Lo que podría hacer que la heurística desde arriba sea incluso más justificable.

¡O el vendedor ambulante juega magia!

Creo que este es un desafío algorítmico bastante interesante. Curioso si alguien tiene alguna buena sugerencia para resolverlo, o si ya se puede resolver de una manera conocida.

TCGPlayer.com vende tarjetas de colección para una variedad de juegos, incluyendo Magic the Gathering . En lugar de solo vender tarjetas de su inventario, en realidad son un revendedor de múltiples proveedores (más de 50). Cada proveedor tiene un inventario diferente de tarjetas y un precio diferente por tarjeta . Cada proveedor también cobra una tarifa plana para el envío (generalmente). Dado todo eso, ¿cómo se puede encontrar el mejor precio para un mazo de cartas (por ejemplo, de 40 a 100 cartas)?

El solo hecho de encontrar el mejor precio para cada tarjeta no funciona porque si solicita 10 tarjetas de 10 proveedores diferentes, entonces pagará el envío 10 veces , pero si solicita las 10 de un solo proveedor, solo pagará el envío una vez .

La otra noche escribí un HTML Scraper simple (usando HTML Agility Pack ) que toma todos los precios diferentes para cada tarjeta, y luego encuentra a todos los proveedores que llevan todas las tarjetas en el mazo, totaliza el precio de las tarjetas de cada proveedor y Clasifica por precio. Eso fue muy fácil. Los precios totales terminaron estando cerca del precio mediano total de todas las tarjetas.

Noté que algunas de las tarjetas individuales terminaron siendo mucho más altas que el precio medio. Eso plantea la cuestión de dividir un pedido en varios proveedores, pero solo si se pueden hacer suficientes ahorros al dividir el pedido para cubrir el envío adicional (cada proveedor agregado agrega otro cargo de envío).

Lógicamente, parece que el mejor precio probablemente solo involucre a algunos proveedores diferentes, pero si las tarjetas son lo suficientemente caras ( y algunas lo son ) , en teoría, ordenar cada tarjeta de un proveedor diferente podría generar suficientes ahorros para justificar todo el envío adicional. .

Si fueras a abordar esto, ¿cómo lo harías? ¿ Fuerza bruta pura imaginando cada combinación posible de combinaciones de tarjeta / proveedor? Un proceso que es más probable que se realice en mi vida parece implicar una serie metódica de estimaciones sobre un número fijo de iteraciones. Tengo un par de ideas, pero tengo curiosidad por lo que otros puedan sugerir.

Estoy buscando más el algoritmo que el código real. Sin embargo, actualmente estoy usando .NET, si eso hace alguna diferencia.

¿Qué pasa con el uso de algoritmo genético? Creo que lo intentaré yo mismo. Puede manipular el grupo agregando un cromosoma con los precios más bajos y otro con los costos de envío más bajos.

Por cierto, ¿finalmente implementaste alguna de las soluciones presentadas aquí? ¿cúal? ¿por qué?

¡Aclamaciones!

En realidad escribí esto exactamente el año pasado. Lo primero que hago después de cargar todos los precios es eliminar mi grupo de tarjetas:

Cada proveedor puede tener varias versiones de cada tarjeta, ya que hay reimpresiones. Encuentra el más barato.
Elimine cualquier tarjeta en la que el valor de la tarjeta sea mayor que el combo de tarjeta + envío más barato. Es decir, si puedo comprar la tarjeta más barata como una sola vez a un proveedor que si la agrego a un pedido existente de su tienda, la compraré al otro proveedor.
Elimine a cualquier proveedor cuya oferta pueda comprar más barato (por cada tarjeta) a otro proveedor. Básicamente, si otro proveedor lo supera en todas las tarjetas y en el total de envío, se habrá ido.

Desafortunadamente, esto todavía deja una enorme piscina. Luego hago un poco de clasificación y un poco de fuerza bruta sumando primero y un poco de poda y, finalmente, obtengo un resultado.

De todos modos, lo sintonicé hasta el punto de poder hacer 70 cartas y, dentro de un minuto, llegar al 5% del objetivo óptimo. Y en una hora, menos del 2%. Y luego, un par de días después, el resultado final real.

Voy a leer más sobre la planificación de las instalaciones. Gracias por ese consejo!

Esto es isomorfo al problema de la ubicación de las instalaciones no capacitadas.

tarjeta en el mazo: cliente
proveedor: posible ubicación de la instalación
tarifa de envío del proveedor: costo de abrir una instalación en un lugar
costo de una tarjeta con un proveedor en particular: "distancia" de un cliente a una instalación

La ubicación de las instalaciones es un problema bien estudiado en la literatura de optimización combinatoria.

Qué tal esto:

Calcule el precio promedio por tarjeta ordenada en todos los proveedores.
Para cada proveedor que tenga al menos una de las tarjetas, calcule el ahorro total para todas las tarjetas en el pedido como la diferencia entre el precio de cada tarjeta en ese proveedor y el precio promedio.
Comience con el proveedor con el mayor ahorro total y seleccione todas esas tarjetas de ese proveedor.
Continúe seleccionando proveedores con el siguiente ahorro total más alto hasta que tenga todas las tarjetas en el orden seleccionado. Omita a los proveedores que no tienen tarjetas que todavía necesita.
De la lista de proveedores seleccionados, redistribuya las compras de la tarjeta a los proveedores con el mejor precio para esa tarjeta.
De la lista restante de proveedores, y si la lista es lo suficientemente pequeña, podría forzar a los proveedores con un recuento bajo de tarjetas para ver si podría mover las tarjetas a otros proveedores para eliminar el costo de envío.

Sólo sería codicioso.

Suponga que va a comer el costo de envío y compre a todos los proveedores. Calcula el precio más bajo que obtienes. Luego, para cada proveedor, calcule cuánto le ahorra el hecho de poder comprarles algunas tarjetas a ellos. Ordene a los vendedores por envío - ahorros incrementales.

Comenzando con los proveedores que proporcionan el menor valor, elimine ese proveedor, redistribuya sus tarjetas a los otros proveedores y vuelva a calcular los ahorros incrementales. Lave, enjuague y repita hasta que su proveedor más marginal le esté ahorrando dinero.

Esto debería encontrar una buena solución, pero no se garantiza que encuentre la mejor solución. Sin embargo, es probable que encontrar la mejor solución absoluta sea NP-duro.

Yo mismo he reflexionado sobre esto. Considera lo siguiente:

Si le toma una semana descifrar, codificar, depurar y un algoritmo que solo proporciona un descuento del 1%, ¿lo haría?

La respuesta es probablemente "No" (a menos que esté gastando sus ahorros de toda la vida en tarjetas, en cuyo caso puede estar loco). =) ... o Amazon.com

En consecuencia, ya existe un algoritmo de aproximación fácil:

Wait until you''re buying lots of cards (reduce the shipping overhead). Buy the cards from 3 vendors: - the two with the cheapest-but-most-diverse inventories - a third which isn''t really cheap but definitely has every card you''d want. Optimize accordingly (for each card, buy from the cheaper one). Also consider local vendors you could just walk to, pre-constructed decks, and trading.

De acuerdo con la experiencia de primera y segunda experiencia, puedo decir que encontrará que puede obtener el precio medio con tal vez unos pocos dólares más de envío que de otra manera podría obtener, mientras que aún se mantiene alrededor de la mediana en cada uno. Descubrirá que es posible que deba pagar un poco más por las tarjetas con un número insuficiente de existencias, pero esto será muy poco, y los ahorros de envío lo compensarán.

Recuerdo el viejo adagio de programación: "Nunca optimices, hasta que sea absolutamente necesario; es probable que no lo necesites, o que hayas optimizado algo incorrecto". (Por ejemplo, su tiempo también es un recurso, y también tiene un valor monetario)

Edición: Dado esto, este es un problema asombrosamente genial y uno debería resolverlo si tiene tiempo.

mi algoritmo va así

para cada tarjeta, calcule el precio promedio disponible, es decir, la suma del precio disponible de cada proveedor se divide por el número de proveedores.
ahora para esa tarjeta, seleccione un proveedor que ofrezca un precio menor o igual al promedio.
Ahora para cada tarjeta tendremos la lista de proveedores. Ahora vaya a la intersección de esta manera, terminaremos con una serie de proveedores que proporcionarán la máxima cantidad de tarjetas a un precio promedio o inferior al promedio.

Todavía estoy pensando en los próximos pasos, pero estoy poniendo la idea aproximada por aquí

Ahora nos quedan las tarjetas que nos proporcionan una sola tarjeta. para dichas tarjetas, veremos la lista de precios de los proveedores ya listados en corto con un máximo de tarjetas y si la diferencia de precio es menor que el costo de envío, agregamos la tarjeta a esa lista de proveedores.

Sé que esto requerirá una gran optimización. pero esto es lo que he descubierto de forma ruda espero que esto ayude