Cette variante du problème de la somme des sous-ensembles est-elle plus facile à résoudre ?

StackOverflow https://stackoverflow.com/questions/376003

Question

J'ai un problème lié au problème de somme de sous-ensemble et je me demande si les différences facilitent les choses, c'est-à-direrésoluble dans un délai raisonnable.

Étant donné une valeur V, une taille d'ensemble L et une séquence de nombres [1,N] S, combien de sous-ensembles de taille L de S totalisent moins de V ?

Ceci diffère du problème de la somme des sous-ensembles de trois manières :

  1. Je me soucie du nombre de sous-ensembles moins qu'une valeur donnée, pas combien il y en a égal.
  2. Les tailles des sous-ensembles sont fixes.
  3. je m'en soucie combien définit la somme à moins de V, pas seulement s'il en existe.

Existe-t-il un algorithme raisonnablement efficace pour résoudre ce problème ?

Modifier:Évidemment, cela peut être fait en O(N choisissez L) en utilisant un algorithme de génération de combinaison.Ce qui m'intéresse vraiment, ce sont des hacks intelligents pour l'accélérer considérablement au-delà de cela.

Était-ce utile?

La solution

(La version décisionnelle de) votre problème est toujours NP-complet.L'idée est que si nous pouvions résoudre votre problème, alors (pour chaque taille de sous-ensemble, disons) nous pourrions demander combien d'ensembles totalisent moins de V et combien totalisent moins de V-1, et la différence de ces deux nombres serait dites-nous s'il y a des sous-ensembles dont la somme est exactement V - nous pourrions ainsi résoudre le problème de la somme des sous-ensembles.[Ceci n'est pas une preuve complète, car c'est un Réduction de Turing, pas un plusieurs réductions.]

Cependant, il existe un simple programmation dynamique solution qui s'exécute dans le temps O(nLV).[La raison pour laquelle cela ne prouve pas que P=NP est que V pourrait être exponentiel dans la taille d'entrée :avec n bits, vous pouvez représenter des valeurs jusqu'à 2n.Mais en supposant que votre V n'est pas exponentiel, ce n'est pas un problème.]

Soit num[v][k][i] le nombre de sous-ensembles de taille k des i premiers éléments de S qui totalisent v.Vous pouvez les calculer comme (pour chaque i) :

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

où S[i] est le ième élément de votre séquence.(Tout ensemble de taille k dont la somme est v n'utilise pas S[i], donc il est compté dans num[v][k][i-1], ou utilise S[i], ce qui signifie que le reste de le sous-ensemble a k-1 éléments, utilise uniquement les i-1 premiers nombres de la séquence et totalise v-S[i].) Enfin, comptez num[v][L][|S|] pour chaque v inférieur à V ;c'est votre réponse.

De plus, vous pouvez omettre le troisième indice si vous le faites avec soin (exécutez votre boucle vers le bas pour chaque i, etc.) ;Je ne l'ai inclus que pour plus de clarté.

Autres conseils

Je ne suis pas prêt à présenter une preuve, mais il semble que cela pourrait se prêter à un schéma de programmation dynamique :dressez un tableau de la liste des sous-ensembles de taille 2, utilisez-les pour ordinateur des sous-ensembles de taille 3, etc., de sorte que vous n'ayez besoin d'examiner qu'une petite collection de prospects.

Une optimisation qui me vient à l’esprit est la suivante :Commandez votre séquence (si ce n'est pas déjà le cas).Choisissez les premiers éléments L-1 dès le début, puis choisissez le dernier élément de telle sorte qu'il s'agisse de la valeur la plus grande possible (la valeur la plus grande suivante dans la séquence donnerait une somme trop grande).Supprimez le reste de la séquence, car ces éléments ne pourront de toute façon jamais faire partie d'un sous-ensemble valide.

Après cela, je suppose que c'est à nouveau une recherche complète.Mais là encore, d’autres optimisations pourraient également être possibles.

La solution de programmation dynamique au problème de la somme des sous-ensembles génère un tableau qui contient cette réponse (c'est-à-dire un tableau booléen de V par N où V est le nombre maximum d'éléments et N est le nombre maximum d'éléments pouvant être dans un ensemble qui satisfait le contraintes;chaque booléen étant vrai si <=N éléments totalisent <=V).Donc, si N * V n'est pas trop grand pour vous, il existe un algorithme suffisamment rapide.La solution de somme de sous-ensemble n'est que l'élément d'ensemble le plus élevé de ce tableau pour lequel le nombre d'éléments est <= N/2.

S'il ne s'agit que d'entiers positifs, vous pouvez effectuer une étape de vérification si tu as besoin;

Prenez la somme des plus petits entiers L-1 de l’ensemble.Si c'est une somme X, alors n-X doit être inférieur au plus grand élément si le problème est censé avoir une solution.À bien y penser, vous pouvez éliminer les autres L de cette façon...

Eh bien, d'abord, puisque vous spécifiez size=L, même si vous ne pouvez penser à rien d'intelligent et utilisez simplement la force brute, vous aurez (N choisissez L) des sommes séparées dans le pire des cas, donc c'est un peu mieux que n^^L (enfin, L+1, comme vous additionneriez alors chaque sous-ensemble).

Cela ressemble à une catégorie de problème n choisissez k.La génération de k-sous-ensembles de n est traitée dans le manuel de conception d'algorithmes de Skiena, et le livre suggère d'énumérer les sous-ensembles pertinents dans l'ordre lexicographique (de manière récursive, par exemple).Faites ensuite votre somme et votre comparaison sur chaque sous-ensemble.

Si vous disposez d'un ensemble trié, vous pouvez probablement supprimer les solutions impossibles de l'espace des solutions.

Peut-être que la formulation de la programmation dynamique se prête à un PTAS ou à un FPTAS.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top