algorithme pour trouver la combinaison optimale des produits et des magasins pour minimiser les coûts

Question

Bonjour à Stackoverflow personnes,

Je gère un site qui trouve ses utilisateurs le moins cher d'acheter des livres. C'est facile pour un seul livre, mais pour plusieurs livres, il peut parfois être moins cher d'acheter un livre dans un magasin et un autre livre dans un autre magasin.

Je trouve actuellement le magasin qui vend moins cher tous les livres dans la liste de l'utilisateur, mais je veux avoir un système plus intelligent. Voici quelques informations supplémentaires:

• Le prix d'un livre est constant pour un magasin.
• Le prix de la livraison peut varier en fonction du nombre de livres ou de la valeur totale des livres.
• Chaque objet de la boutique peut prendre une série de livres et renvoyer les frais de port.
• Souvent, tous les magasins ne vendent pas tous les livres.

Vous ne savez pas si c'est cool de créer un lien vers mon site ici, mais il est répertorié dans mon profil utilisateur. Je voudrais être en mesure de trouver la combinaison la moins chère de magasins et de livres.

Je crains qu'il exige une approche de la force brutale - et avec 35 magasins, le nombre de combinaisons seront énormes pour un petit nombre de livres. Je sens le nombre de combinaisons est (#shops)^(livres de #) - mais pas à 100%

La question est, quelle approche devrais-je utiliser? Ce problème correspond-il à une catégorie de problèmes bien connue? Si la force brute est requise, quelle est la meilleure façon de le faire dans Ruby et puis-je donner la priorité aux boutiques pour essayer en premier?

Answer 1

Malheureusement, ceci est un exemple d'un problème d'optimisation combinatoire qui n'a pas de solution facile. Vous avez raison de dire qu'en général, vous avez besoin d'une approche de force brute. Toutefois! Je soupçonne qu'il y a une structure spéciale dans ce problème qui aidera. Par exemple, le coût d'expédition ne change pas au hasard lorsque vous modifiez la combinaison de livres - il augmentera probablement sub-linéairement et/ou saturera au fur et à mesure que vous ajoutez des livres.

Voici ce que je recommande, puis:

1. Hors ligne, estimer les politiques d'expédition de chaque magasin, de sorte que, des livres donnés (et peut-être leur poids), vous pouvez estimer le coût d'expédition sans se référant à leurs sites.
2. Pour chaque magasin, calculez le coût de chaque livre, s'il est disponible.
3. En mode hors connexion, parcourez chaque magasin ou ensemble de magasins et estimez, en utilisant vos règles d'expédition hors connexion, le coût total.
4. Choisissez le magasin (ou magasins) le moins cher. Si plusieurs sont similaires, calculez la réponse exacte.

Cela devrait vous aider à démarrer et vous évitera une recherche complète.

Answer 2

Brute Force peut presque toujours être remplacé par une bonne heuristique, qui est un algorithme qui est connu pour effectuer pas encore optimale « assez bon ».

Bien que je ne sois pas sûr à 100%, je suppose que cela se rapporte à la Knapsack problem qui est (comme nous sommes tous censés maintenant haha ​​..) NP-complète.

Rien de mieux à offrir en ce moment, mais bonne chance!

Answer 3

Ceci est une variante de ce que l'on appelle classiquement le "problème d'affectation". L'AP classique a quelques solutions standard, y compris l'algorithme Munkres (alias «hongrois») et l'algorithme JVC (Junker Volgenant Castanon iirc). L'idée de base est de calculer un coût pour chaque affectation (c'est-à-dire, le coût d'achat de chaque livre dans chaque magasin), puis sélectionnez l'ensemble des affectations qui minimisent le coût total. Cela peut être fait en temps polynomial, je crois.

Le fait que les frais d'expédition de chaque détaillant dépend de la commande totale rend les choses beaucoup plus délicates. Vous pourriez être en mesure d'utiliser une approche hybride qui ne tient pas compte des frais d'expédition à l'origine, puis pour les commandes globales une fois que vous avez identifié quelques missions prometteuses.

Bonne chance, cela ressemble à un problème amusant!

Answer 4

Essayez d'utiliser l'approche de programmation dynamique. Vous pouvez lire à ce sujet ici: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Vous pouvez aussi le lire sur wikipedia ou dans le livre "Introduction to Algorithms" (Cormen).

C'est un problème assez courant.

Answer 5

cela peut-il être un problème lp? http://en.wikipedia.org/wiki/Linear_programming