J'essaie de trouver un algorithme raisonnable pour ce problème:
Disons que vous avez un tas de balles. Chaque balle a au moins une couleur, mais peut également être multicolore. Chaque balle a un poids et une valeur associée à celle-ci. Il y a aussi une bouquet de boîtes qui ne sont chacune une seule couleur. Chaque boîte a un nombre maximum de balles qu'il peut contenir. L'objectif est de maximiser la somme de la valeur dans les cases tout en restant sous un peu de poids total, w et la seule règle est:
Pour placer une balle dans une boîte, elle doit au moins avoir la couleur de la boîte sur elle
(par exemple, vous pouvez mettre une balle bleue et verte dans une boîte bleue ou une boîte verte, mais pas dans une boîte rouge.)
J'ai du dôme certaines recherches et cela semble semblable au problème du sac à dos et aussi semblable à être satisfaits par l'algorithme hongrois, mais je ne saurais pas sembler de le réduire à un problème.
Je suis juste curieux, c'est qu'il y a une sorte d'algorithme de programmation dynamique pour ce type de problème pour le rendre satisfaisable en temps polynomial, ou s'il s'agit du problème du vendeur itinérant dans le déguisement. Cela aiderait-il si je savais qu'il y avait au plus x couleurs? Toute aide est grandement appréciée. Je pourrais également formaliser un peu le problème avec des noms variables si cela vous aiderait. Merci!
Voici un exemple simple:
Poids maximum: 5
boules:
1 ballon rouge - (valeur = 5, poids = 1)
1 balle bleue - (valeur = 3, poids = 1)
1 boule verte / rouge / bleue - (valeur = 2, poids = 4)
1 boule verte / bleue - (valeur = 4, poids = 1)
1 ballon rouge / bleu - (valeur = 1, poids = 1)
1 rouge (contient 1 balle)
1 bleu (maintient 2 balles)
1 vert (contient 1 balle)
Solution optimale:
ballon rouge en boîte rouge
Boule bleue et boule rouge / bleue dans une boîte bleue
Boule verte / bleue dans la boîte verte
Valeur totale: 13 (5 + 3 + 1 + 4)
Poids total: 4 (1 + 1 + 1 + 1)
Remarque: Même si la balle verte / rouge / bleue était plus précieuse que la balle rouge / bleue, son poids nous aurait posé sur la limite.
Un point de clarification: les balles de même combinaison de couleurs n'auront pas nécessairement les mêmes poids et valeurs. Par exemple, vous pourriez avoir une balle rouge avec valeur 3 et 1 poids 1 et une autre boule rouge avec valeur 2 et poids 5.
edit 2:
Nous pouvons assumer des poids et des valeurs entier si cela nous aide à proposer un algorithme de programmation dynamique.
5 Réponses :
Ceci est au moins aussi complexe que le problème du sac à dos - envisagez un cas où toutes les balles sont rouges et il n'y a qu'une seule boîte rouge.
Dans le cas où des balles qui ont la même combinaison de couleurs doivent avoir les mêmes poids et les mêmes valeurs envisager un cas lorsque vous avez des balles rouges / bleues, rouge / vert, etc. Boules et une seule boîte rouge.
Yep +1. L'aspect multicolore des balles pourrait rendre la solution de programmation dynamique habituelle un peu plus compliquée.
Pour clarifier: les balles de même combinaison de couleurs n'auront pas nécessairement les mêmes poids et valeurs. Par exemple, vous pourriez avoir une balle rouge avec valeur 3 et poids 1 et une autre boule rouge avec valeur 2 et poids 5.
Quoi qu'il en soit, vous pouvez représenter toute instance de Knapsack avec ce problème afin qu'il soit NP-dur.
@Obrok: Je vois. Je suppose que j'espérais que, puisque vous puissiez utiliser une programmation dynamique pour résoudre le problème du butin en polynôme (en supposant que les poids et les valeurs sont des entiers), vous pourrez peut-être utiliser une technique similaire ici.
C'est un pseudo-polynôme en fait - cela signifie dans ce cas de polynôme polnomial dans la somme des poids - ce qui pourrait être très grand, même pour de petits problèmes! Un algorithme dynamique efficace n'est pas susceptible d'exister pour ce problème - l'état est très complexe - chaque type de balle et de boîte doit être traité séparément, il est donc peu probable que les nœuds de recherche dans l'arbre de recherche se répètent.
Ah, merci pour la clarification. C'est ce que j'avais peur de.
@Kenny Cette preuve n'exclut pas la possibilité d'une solution de programmation dynamique (pseudo-polynôme). Knapsack est faiblement NP-complet . Pour établir complètement une telle inexistence, nous devons réduire un problème de NP-complet (avec des exigences supplémentaires sur la réduction elle-même).
La réduction du sac à dos est la suivante. Compte tenu de votre instance Knapsack, vous créez une instance des balles et des bacs Problème: Pour chaque élément de l'instance de KNAPSACK, vous avez une balle avec le même poids et la même valeur que l'élément. Ensuite, vous avez une boîte représentant le sac à dos. Les balles et la boîte sont tous bleues. La capacité de la boîte est la limite donnée dans le problème du sac à dos. Étant donné une solution à votre problème, nous avons un ensemble de balles dans la boîte dont le poids total est au plus la limite de sacs à dos et dont la valeur totale est maximisée.
Le meilleur que vous puissiez faire dans cette situation est d'obtenir une approximation de la solution optimale - le problème du sac à dos n'est pas satisfable en temps polynomial lui-même. Vous pourrez peut-être toujours obtenir de bien (bien que cela ne soit pas garanti optimal) entraîne du temps polynôme si vous pouvez générer un bon algorithme pour cela.
Ce problème est NP-complet, car il subsume le problème du knapsack.
C'est-à-dire que ce n'est pas seulement similaire au problème du sac à dos: s'il y a un bol, toutes les balles ont la couleur de ce bol, et le nombre maximum de balles dans le bol est le nombre total de balles, puis le problème est exactement le problème du knapsack.
Si un algorithme pourrait résoudre ce problème en temps polynomial, il pourrait résoudre n'importe quel problème de sacs à dos en temps polynomial. Mais, étant donné que le problème du knapack est complet, ce problème est aussi.
Je conviens qu'avec une case, cela réduit à Knapsack, mais je ne vois pas comment je pourrais utiliser les mêmes techniques pour résoudre ce problème lorsqu'il y a plusieurs boîtes avec différentes couleurs. Étant donné que les balles peuvent avoir plus d'une couleur, elles pourraient potentiellement installer dans des boîtes différentes, de sorte que les "knapacks" individuels ne sont pas indépendants.
Votre question était "est le problème résoluble en temps polynomial". C'est le pire cas: si vous pouvez composer tout problème possible , il ne peut pas résoudre en temps de polynôme, la réponse est "non". Une autre façon de le mettre: Si vous trouvez un algorithme qui peut résoudre ce problème en temps polynomial, vous avez prouvé que p = np. Et pendant que nous ne savons pas sûr que c'est impossible, il ne semble pas très probablement ...
Merci, j'aurais dû clarifier plus tôt: j'espère qu'une solution «pseudo-polynomial» pourrait également être possible / pratique.
S'il n'y a pas de liaison sur le nombre de cases, ce problème est fortement np-dur par réduction de 3-partition (configurez n / 3 boîtes et faites toutes les choses de couleur arc-en-ciel avec valeur = poids).
Si le nombre de cases est constant, il y a un algorithme de temps pseudo-polynomial via une programmation dynamique, où chaque état DP consiste à faire progresser chaque boîte.
Pouvez-vous élaborer un peu comment cet algorithme DP fonctionnerait en supposant un nombre constant de boîtes? Merci!
Considérez les articles un par un. À chaque étape, gardez une table indexée par des tuples décrivant la manière dont chaque boîte est pleine. Par exemple, l'index (2, 2, 3) signifierait que la première boîte comporte 2 unités d'éléments, le second, 2 aussi et le troisième, 3. Chaque entrée de table est la valeur maximale pouvant obtenir sur les éléments considérés Jusqu'à présent, chaque boîte est remplie au niveau spécifié par l'indice de cette entrée.
Quels numéros de taille sont vos chiffres réels de boîtes, de balles, de couleurs?
Bonjour Knapsack-Problème? Si des balles peuvent avoir des poids arbitraires, il me semble donc pour moi. Vous n'avez même pas besoin de couleurs pour cela :)
@Aakashm: Démarivement petit: le nombre de cases est de l'ordre de 10. Le nombre de balles par boîte est de l'ordre de 10. Le nombre total de couleurs possibles est de l'ordre de 10. Le nombre de couleurs par balle est Habituellement, un maximum de 5 (cas commune n'est qu'une ou deux couleurs par balle). Le nombre total de balles disponibles est de l'ordre de 1000.
@Voo: Pouvez-vous m'aider à voir comment cela se réduit à Knapack? Il semble que chacune de mes boîtes individuelles soit un sac à dos de tri, mais chaque boîte avait une limite de capacité, pas une limite de poids, et je dois rester sous un poids pour la somme de toutes les cases tout en maximisant la valeur.
@Kenny, il suffit de supposer que des balles peuvent avoir des poids arbitraires, si c'est vrai - l'explication des personnes qui répondaient déjà est la même chose que je donnerais.
Afin de résoudre un problème en temps polynomial, vous devez être capable de gérer toutes les instances du problème. L'ajout d'une limite de capacité n'a pas d'importance, car vous pouvez configurer le problème avec une limite de capacité si élevée, cela n'est pas pertinent (par exemple, définissez-le sur le nombre total de balles)
En d'autres termes: l'ajout d'une limite de capacité peut rendre le problème de sac à dos plus difficile, mais il ne peut pas faciliter la tâche.
Je suppose que j'espérais une solution de "période pseudo-polynomial". J'aurais dû clarifier. De toute évidence, ce problème est au moins aussi compliqué que le sac à dos.