Bonjour Land Stackoverflow Personnes,
Je gère un site qui trouve ses utilisateurs l'endroit le moins cher pour acheter des livres. Ceci est facile pour un livre unique, mais pour plusieurs livres, il peut parfois être moins cher d'acheter un livre sur un magasin et un autre livre d'un autre magasin.
Actuellement, je trouve le magasin le moins cher qui vend tous les livres de la liste de l'utilisateur, mais je veux avoir un système plus intelligent. Voici quelques informations supplémentaires:
Je ne sais pas si c'est cool de créer un lien vers mon site ici, mais il est répertorié dans mon profil d'utilisateur.
J'aimerais pouvoir trouver la combinaison la moins chère de magasins et de livres.
Je crains que cela nécessite une approche de force brute - et avec 35 magasins, le nombre de combinaisons sera énorme pour un nombre modeste de livres. J'ai l'impression que le nombre de combinaison est (#shops) ^ (# livres) - mais pas 100%
La question est, quelle approche dois-je utiliser? Ce problème correspond-il dans une classe de problèmes bien connue? Si une force brute est requise, qu'est-ce qui est un bon moyen de le faire dans Ruby et puis-je donner la priorité aux magasins d'essayer d'abord?
6 Réponses :
Malheureusement, il s'agit d'un exemple de problème d'optimisation combinatoire qui n'a pas de solution facile. Vous avez raison que vous ayez réellement 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 de l'expédition ne changera pas de manière aléatoire lorsque vous modifiez la combinaison de livres - elle augmentera probablement sous-linéairement et / ou saturera à mesure que vous ajoutez des livres.
Voici ce que je recommande, alors:
Cela devrait vous aider à démarrer et vous gardera une recherche complète.
Salut, merci pour la réponse. 1-3 sont déjà en place. Une méthode par magasin est utilisée pour déterminer les frais d'expédition. L'une des difficultés est que la valeur d'expédition peut être déterminée par nombre de livres ou prix total de l'ordre - ce qui rend la vie un peu complexe. Déterminer quels boutique expédie tous les livres pour le coût le plus bas est facile - il est de savoir que l'un des livres devrait être acheté à la boutique A, tandis que le reste de la boutique B.
La force brute peut presque toujours être remplacée par une bonne heuristique, c'est-à-dire un algorithme connu pour n'effectuer pas optimal mais suffisamment bon ».
Bien que je ne sois pas sûr à 100%, je suppose que cela se rapporte avec le Problème de Knapsack Ce qui est (comme nous sommes tous supposés maintenant haha ..) NP-complète.
Je n'ai rien de mieux à offrir maintenant, mais bonne chance!
Ceci est une variation de ce que l'on appelle classiquement le "problème d'attribution". L'AP classique compte quelques solutions standard, y compris les munkres (AKA "Hongroise") algorithme et l'algorithme JVC (Junker Volgenant Castanon IIRC).
L'idée de base consiste à calculer un coût pour chaque affectation (c'est-à-dire le coût d'achat de chaque livre à 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 le coût d'expédition de chaque détaillant dépend de l'ordre total rend les choses considérablement plus difficiles. Vous pourrez peut-être utiliser une approche hybride qui ne considère pas les coûts d'expédition à l'origine, puis pour les commandes globales une fois que vous avez identifié quelques tâches prometteuses.
bonne chance, sonne comme un problème amusant!
Essayez d'utiliser une approche de programmation dynamique. Vous pouvez en lire ici: http://www.topoder.com/tc ? Module = statique & d1 = tutoriels & d2 = dynprog Aussi, vous pouvez en lire sur Wikipedia ou dans "Introduction aux algorithmes" (Cormen).
C'est un problème assez standard.
Le knapack non borné à l'aide de la programmation dynamique est votre réponse.