Algorithme de minimisation du panier d'achat

Ce problème est NP Hard .
Nous allons montrer une réduction du Frapper le problème défini .
Frapper Défini Problème FORT>: Ensembles données S1, S2, ..., SN CODE> et un numéro k code>: Chose Set S code> de la taille k code>, tel que pour chaque si code> il y a un élément s code> dans s code> tel que s code> est dans si code>. [Définition alternative: l'intersection entre chaque SI code> et s code> n'est pas vide].

réduction: strong>
Compte tenu d'une instance de frappe définie, sous la forme de (S1, ..., sn, k) code> Créer une instance de ce problème: p>

All books cost nothing. In order to buy from each store you pay 1. 
The book i is sold by each store denoted in Si, minimal price for this instance is k.

Une bonne heuristique peut être l'optimisation de la colonie de fourmis. Je l'utilise pour résoudre le problème du vendeur de voyage. Vous pouvez trouver un exemple de travail à partir de Google Tsp Solver. C'est une bibliothèque JavaScript qui utilise également une force brute et une solution de programmation dynamique. L'AOC est utilisé lorsque vous avez plus de villes à calculer, puis à la limite actuelle de 20 villes. Je crois que vous pouvez utiliser la bibliothèque pour résoudre votre problème et il a juste besoin d'une petite réécriture. Avec 20 villes, le programme doit vérifier 20! posibilites. Dans votre cas, il est un peu plus léger mais peut-être seulement une magnitude.

avec tant de petits articles que j'ai une solution. C'est dynamique.

Nous traiterons chaque magasin de manière itérative. À chaque étape, nous stockons le meilleur prix actuel avec lequel nous pouvons couvrir tous les sous-ensembles d'articles. Au début, tous sont Infinity Code> dans le prix sauf pour le sous-ensemble vide qui est 0 code> du prix. Notez que tous les sous-ensembles sont 2 ^ num_products code> dans le décompte, mais dans votre cas, il ne s'agit que d'environ 1000. P>

MAINTENANT Comment traitons-nous la prochaine boutique: considérez que vous couvrez tout le possible. Sous-ensemble des produits avec ce magasin (je veux dire sous-ensemble que le magasin peut réellement fournir) et tout le reste des produits couverts par des magasins que vous avez déjà observés, améliorant ainsi les coûts minimes de couvrant chaque sous-ensemble. Cette étape prend 2 ^ num_products * 2 ^ num_products = 4 ^ Num_Products code>, toujours environ un million qui est garanti. Vous faites cela pour chaque magasin et à la fin de la réponse est le coût de la couverture de tous les éléments. Toute la complexité de la solution proposée est 4 ^ Num_Products * Num_shops code> qui est d'environ 50 millions qui est bon à partir. P>

Notez que cela reste exponentiel et cela n'est pas surprenant. Merci d'amiter pour son incroyable preuve de NP dur. p>

EDIT EDIT FORT> Ajout d'une explication plus poussée de l'algorithme de pseudocode: p>

init:
 cost[subset] = infi
 cost[{}] = 0
for shop in shops
 new_prices = costs.dup()
 for set : subsets
   for covered_set : all_subsets(set)
     price = covered_set == {} ? 0 : delivery[shop]
     remaining = set
     for element : covered_set
       if shop do not sale element
         break for, choose next covered_set
       price += el_price[element]
       remaining.remove(element)
     price += costs[remaining]
     new_prices[set] = min(new_prices[set], price)
 costs = new_prices
return costs[all]