Discuter:Problème du sac à dos

Un article de Wikipédia, l'encyclopédie libre.

	Problème du sac à dos fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
AdQ	Cet article a été classé comme d'Avancement AdQ selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne	Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)

	Problème du sac à dos fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
AdQ	Cet article a été classé comme d'Avancement AdQ selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne	Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet.

Problème du sac à dos est apparu sur la page d'accueil de Wikipédia en tant qu'article mis en lumière le

1 et 2 septembre 2006.

Sommaire

1 Problème de traduction
2 Illustration
3 NP-complétude, algorithmes d'approximation
- 3.1 Illustration du glouton
4 Sur les boîtes déroulantes
5 Sur la démonstration de la NP-complétude
- 5.1 Ce qu'en dit le Garey/Johnson
6 Problème d'optimisation et problème de décision
7 Programmation dynamique avec utilisation mémoire en O(n+W)

[modifier] Problème de traduction

Comment traduire : en:bin packing problem, en:packing problem, en:covering problem et peut-être aussi en:baker's dozen, tous des articles reliés... ? Aussi : en:subset sum problem... en espagnol, on dit qqch comme problème de la somme d'un sous-ensemble. Gene.arboit 14 juillet 2006 à 17:06 (CEST)

Pour « covering », ce sera « couverture », sans hésiter : problème de couverture d'ensemble correspond à en:set covering problem. On peut penser à « vertex cover » aussi, qui est une couverture des sommets d'un graphe. Pour le « packing », je dirais « remplissage » mais je n'ai encore jamais entendu ces problèmes en version française. Si j'ai bien compris, le « bin packing » est un « packing » avec plusieurs objets à remplir, il n'aura peut-être pas un nom particulier. Pour le « subset sum », il est quelquefois présenté comme « problème de la somme de sous-ensembles » ce qui me semble juste être un traduction simple.

non c'est plutôt recouvrement Oxyde 7 août 2006 à 22:30 (CEST)

Est-ce que Problème de la couverture exacte devrait être renommé ? Ou est-ce que ~~problème de couverture d'ensemble~~ -> problème de recouvrement d'ensemble ? Gene.arboit 7 août 2006 à 23:49 (CEST)

[modifier] Illustration

Je trouve un peu dommage que, sur l'illustration, la solution optimale corresponde à un cas où le sac est plein (16 $ et 15 kg). Si on mettait la boîte à 12 kg à 4 $, 2 kg à 2 $ et 4 kg à 10 $, la solution optimale correspondrait à un cas où le sac n'est pas plein. J'ajouterais qu'on pourrait mettre des € à la place des $, mais là je chipote. --Julien Jorge 26 juillet 2006 à 10:34 (CEST)

- par contre pour les €, pas question, il n'y en a pas en Suisse, je préfère encore le $ :) Dake^@ 7 août 2006 à 22:50 (CEST)

[modifier] NP-complétude, algorithmes d'approximation

D'abord, je recopie mes remarques postées initialement sur la page de vote AdQ :

il y a quelques points qui me chagrinent : la partie histoire me laisse un peu sur ma faim (je ne connais pas, mais j'ai l'impression qu'on pourrait faire mieux ; en particulier, sur les motivations du problème, la réponse apportée par Utilisateur:Julien Jorge ne me satisfait pas) ; la démonstration de NP-complétude est frustrante puisqu'elle renvoie à une autre propriété de NP-complétude qui est wikipediennement inexistante à l'heure actuelle ; j'aurais aussi bien aimé qu'on tire la morale des divers points évoqués : NP-complets + algo approchés +algos exacts? en pratique, que parvient-on à calculer? et en combien de temps? je n'arrive vraiment pas à le voir et j'aurais aimé qu'on me l'explique (j'ai jeté un coup d'œil vite fait, il est tard, désolé si des choses m'ont échappé). Enfin, la rédaction pourrait être meilleure par endroits, il me semble.

Gene.arboit semble avoir pris les choses en main sur ces remarques. J'en rajoute :

toujours sur la preuve de NP-complétude : ce qui est fait pourrait peut-être être mis dans une boîte déroulante? Sachant que ce n'est qu'une réduction à un autre problème, il me semble que c'est susceptible d'effrayer le lecteur pour pas grand-chose.
En quoi l'algo glouton fournit-il une résolution approchée (même mauvaise)? Le fait-on tourner plusieurs fois? Et les bons algos approchées, est-ce que l'idée globale, c'est de faire une seule tentative et on va trouver une approx suffisamment bonne, ou est-ce qu'il y aura plusieurs tentatives? Plus généralement, je ne vois pas en quoi l'algo glouton montre ici ce qu'est, au moins dans le principe, une résolution approchée... Que se passe-t-il si on fait une réso approchée à distance garantie k<1? (ou plutôt, quelles sont les valeurs de k acceptables?)

C'est tout pour le moment.Salle 7 août 2006 à 22:02 (CEST)

pour la réduction, je suis tout à fait d'accord. Cette partie est nécessaire pour que l'article soir complet, mais c'est exactement le genre de partie qui peut effrayer le novice. Dès que je trouve comment faire une boîte déroulante je m'en occupe.

pour les algos approchés, on ne les fait tourner qu'une seule fois, simplement parce que, pour une instance donnée, ils génèreront toujours la même solution. Peut-être que l'on devrait détailler la phrase "La solution X retournée par l'algorithme glouton peut être d'aussi mauvaise qualité que possible". Si on fait une résolution approchée à distance garantie k<1, on peut tomber dans un temps de résolution incroyablement long, pouvant rejoindre le temps d'une exploration complète des solutions (

2 n

solutions à tester). C'est ce qu'exprime l'article algorithme d'approximation avec le modèle utilisan le rapport epsilon. --Julien Jorge 7 août 2006 à 23:45 (CEST)

Réponse sur algo approché : effectivement, lecture déficiente de ma part sur l'article lié, désolé. je viens de voir qu'un dessin avait été ajouté pour expliquer l'algo glouton ; très bien, mais c'est peut-être dommage de prendre un cas où il fournit précisément la solution optimale (si je ne me suis pas planté dans mon calcul, si c'est le cas, oublions cette remarque).

En fait, ce que je me demande, c'est alors : en quoi est-ce que l'algo glouton est un bon exemple des algos d'optimisation réellement efficaces sur ce problème?Salle 8 août 2006 à 00:02 (CEST)

Justement, l'algo glouton est très mauvais. Cependant, les algos gloutons en général sont facilement implémentables et suivent toujours le même schéma (quel que soit le problème auquel on les applique). Du coup, on les utilise souvent pour avoir une idée de ce que l'on peut au moins avoir comme qualité de solution ; ça peut permettre d'accélérer la résolution exacte. Par contre, les algos d'approximation efficaces sont, eux, plutôt dificiles à implémenter et à comprendre. Mais peut-être que l'on peut en mettre un. --Julien Jorge 8 août 2006 à 00:15 (CEST)

Je ne les connais pas, donc, je ne peux pas répondre ; mais le problème avec la formulation actuelle, c'est qu'on a un peu l'impression de se faire couillonner : ils me proposent l'algo glouton comme exemple d'algo approché, mais je sens bien que ça n'a rien à voir avec la vraie solution. Au pire, je pense que le lecteur (moi en l'occurrence) sera plus content si on lui dit carrément : les algos d'approximation efficaces sont, eux, plutôt dificiles à implémenter et à comprendre, et renvoyer la description de l'un d'entre eux dans un autre article.Salle 8 août 2006 à 00:20 (CEST)

[modifier] Illustration du glouton

Je reviens sur ce qu'à dit Salle sur l'illustration de l'algo glouton. En effet, la solution trouvée est optimale ; c'est un peu dommage. Je crois que l'instance suivante serait plus intéressante :

indice	valeur	poids	efficacité
1	10 $	9 kg	1,11
2	7 $	12 kg	0,58
3	3 $	7 kg	0,43
4	2 $	5 kg	0,4
5	1 $	2 kg	0,5

La solution optimale est 12 $ et 14 kg mais le glouton va trouver 11 $ et 11 kg (selon le tri : 1, 2, 5, 3, 4).

De plus, on pourrait utiliser cette même instance pour l'illustration en tête de l'article, histoire de faire un lien. --Julien Jorge 8 août 2006 à 00:44 (CEST)

Merci, j'avais la flemme de trouver une bonne instance du problème :) Je vais corriger ce soir. Dake^@ 8 août 2006 à 09:15 (CEST)

En fait je me rends compte que j'avais mal interprété la notion d'efficacité en ne tenant compte que de la valeur. Dake^@ 8 août 2006 à 09:17 (CEST)

[modifier] Sur les boîtes déroulantes

Ca me convient très bien comme ça, mais étant à l'origine de la demande, et ne voulant pas être accusé de sabotage d'AdQ, je dois prévenir que certains utilisateurs ont une position de principe contre les boîtes déroulants. Sinon, j'en profite pour réitérer mes demandes :

L'algorithme glouton donne-t-il une bonne idée de ce qu'est un algorithme de résolution approchée, Quelle type de stratégie pourrait-on utiliser pour un tel algorithme? Et si les réponses sont trop compliquées, dire au moins explicitement qu'elles sont trop compliquées pour cet article et qu'on renvoit le lecteur ailleurs.
NP-complétude, et algos exacts, et algos approchés... En pratique qu'est-ce qu'on fait? Dans quelle mesure les algos exacts évoqués fournissent-ils une amélioration par rapport à l'algo brutal, puisque la NP-complétude semble suggérer qu'on ne peut pas trouver vraiment mieux?

Salle 9 août 2006 à 01:16 (CEST)

En fait c'est plutôt le rôle des articles algorithmes d'approximation, heuristique et métaheuristique de donner une bonne idée de ce qu'est un algorithme de résolution approchée ;-) Mais je vais essayer de retrouver un algo d'approximation pour le sac à dos qui illustrerait un peu l'article.

Pour ce qui est de ce que l'on fait en pratique, j'ai bien noté votre remarque (trois fois déjà !). J'essaierai de trouver quelques valeurs et de synthétiser pour les intégrer à l'article. --Julien Jorge 9 août 2006 à 10:37 (CEST)

[modifier] Sur la démonstration de la NP-complétude

(Retranscription d'une remarque faite sur la discussion de l'article en AdQ - "Touriste" parle en fond jaune clair et "Julien Jorge" parle en fond jaune foncé) :

Plus embêtant, en une bonne dizaine de minutes voire davantage, je n'ai pas du tout réussi à comprendre la preuve du 3-2 (j'aurais bien aimé la réécrire, mais j'ai pas réussi à voir où l'auteur voulait en venir -je décroche essentiellement au tour de passe-passe du "puis en" où on perd dramatiquement des contraintes à première vue, comment peut-ce n'être pas catastrophique je n'ai pas pigé... Mais bon de toutes façons, dans la mesure où j'arrive en principe d'habitude à lire des démonstrations et malgré mon manque de confiance en moi, je crois qu'il faut incriminer l'article plutôt que le lecteur. (Au-delà du fait que je n'ai pas compris, je ne suis pas certain que ce soit judicieux d'utiliser de façon apparemment désordonnée (ou dont je n'ai pas compris la motivation) des sommations pour j dans U et des sommations pour j dans S_i pour exprimer le même cardinal |S_i|) --Touriste 10 août 2006 à 00:26 (CEST)

Et transfert de la discussion qui s'ensuit :

je reviens sur les commentaires du vote contre de Touriste :

« je n'ai pas du tout réussi à comprendre la preuve du 3-2 [...] je décroche essentiellement au tour de passe-passe du "puis en" où on perd dramatiquement des contraintes à première vue »

Si j'ai bien compris, votre commentaire porte sur

$\sum_{i=1}^n x_iy_{ij} \le 1, \forall j \in U$

puis en

$\sum_{j \in U}\sum_{i=1}^n x_iy_{ij} \le |U|$

Si on renomme le terme $\sum_{i=1}^n x_iy_{ij}$ par, disons,

A j

, est-ce que je me trompe en voyant l'équivalence suivante :

$A_j \le 1, \forall j \in U \Leftrightarrow \sum_{j \in U} A_j \le |U|$

Je reprends doucement mais je n'arrive pas à voir d'où viendrait la moitié de l'équivalence qui remonte de droite à gauche. Peut-être d'un contexte extérieur, mais lequel ?

Voyons je prends un exemple simplissime pour voir où nous ne parvenons pas à communiquer.

U = {1,2,3,4}

S = {{1,2},{2,3},{3,4}}

Dans cet exemple,

(x 1, x 2, x 3) = (1,1,0)

me semble être une solution du problème du sac à dos que vous proposez d'associer au problème de couverture exacte qui ne fournit PAS une solution du problème de couverture exacte ; pour ce vecteur, on a bien $\sum_{j \in U} A_j \le |U|$ et on a même l'égalité très précisément

1 + 2 + 1 + 0 = 4

mais on n'a pas $A_j \le 1, \forall j \in U$ puisque

A 2 = 2

. Et donc la résolution sans plus de précautions du problème de sac à dos associé ne fournit pas de couverture exacte (évidemment

(x 1, x 2, x 3) = (1,0,1)

serait elle une solution sympathique, mais je ne vois pas comment votre méthode de recherche la fait apparaître préférentiellement à celle qui ne marche pas). --Touriste 10 août 2006 à 11:27 (CEST)

Et bien vous avez tout à fais raison, il n'y a pas l'équivalence. Du coup c'est super problématique puisqu'on n'a pas l'équivalence KP -> EC. Je vais essayer de revenir sur tout ça ce soir. Merci. --Julien Jorge 10 août 2006 à 12:00 (CEST)

« je ne suis pas certain que ce soit judicieux d'utiliser de façon apparemment désordonnée (ou dont je n'ai pas compris la motivation) des sommations pour j dans U et des sommations pour j dans S_i pour exprimer le même cardinal |S_i|) »

Je ne suis pas sûr de voir de quelle partie vous parlez. Je ne vois pas de somme de j dans U et de j dans S_i qui expriment tout deux le cardinal S_i. Searait-ce

$\sum_{i=1}^n (x_i\sum_{j \in S_i}y_{ij}) \le |U|$ ? Peut-être que ce qui vous choque c'est que j'ai changé l'ensemble sur lequel porte la somme sur j en la rentrant dans la somme sur i ? Si c'est le cas, je vais tenter d'éclairer votre idées avec cette petite égalité :

soit $i \in \{1, \dots, n\}$ donné. D'après la définition de

y i j

, on a $\sum_{j \in U} y_{ij} = \sum_{j \in S_i} y_{ij}$ .

J'avais bien vu cette identité, les deux étant égaux à

| S i |

; justement je ne comprends pas l'intérêt en si peu de lignes de désigner le même entier sous quatre notations différentes (

| S i |

w i

, $\sum_{j \in U} y_{ij}$ et $\sum_{j \in S_i} y_{ij}$ . Deux voire trois c'est inévitable, mais tant que ça est-ce vraiment essentiel ? (Bon ça s'est secondaire, de toutes façons) --Touriste 10 août 2006 à 11:27 (CEST)

Le but n'est pas d'embrouiller le lecteur avec des notations et des transformations magiques de formules. Si je traîne du début à la fin de la preuve ces valeurs

y i j

et ces sommes aux domaines variables c'est justement pour faire apparaître explicitement les variables

w i

et la structure du problème de sac à dos. --Julien Jorge 10 août 2006 à 10:50 (CEST)

[modifier] Ce qu'en dit le Garey/Johnson

Bon, partons du problème formulé ainsi :

INSTANCE : soient

un ensemble fini $U$
une "taille" $s(u)\in Z^+$
une "valeur" $v(u)\in Z^+$ pour chaque $u\in U$
une contrainte de taille $B\in Z^+$
une valeur objectif $K\in Z^+$

QUESTION: existe-t-il un sous-ensemble $U'\subseteq U$ tel que : $\sum_{u\in U'}s(u)\le B$ et $\sum_{u\in U'}v(u)\le K$

Allons maintenant à ce qui nous intéresse. Garey et Johnson donnent une idée de la preuve :

« Se restreindre à PARTITION en autorisant seulement les instances dans lesquelles $s (u) = v (u)$ pour tout $u\in U$ et $B=K=\frac{1}{2}\sum_{u\in U}s(u)$ »

Je pense que cette idée de preuve suffit. Benoît Guédas 10 août 2006 à 12:50 (CEST)

[modifier] Problème d'optimisation et problème de décision

En essayant d'améliorer des détails, et sans livre sous la main, j'essaie d'apprendre au passage le sujet, que je ne connaissais pas.

Et je découvre au moins une imprécision qui n'est sûrement pas gênante pour quelqu'un qui connaît la théorie de la complexité, mais qui est quand même une imprécision, qui a bien handicapé le lecteur naïf que je viens d'être.

Je lis dans l'article : «Le problème est NP-complet,» alors que je lis dans la version anglaise «The decision version of the knapsack problem described above is NP-complete» ce qui est indéniablement plus précis... et en fait j'ai eu besoin de passer par la version anglaise pour être éclairé.

L'auteur de la nouvelle version de la démonstration expose sommairement ce qu'est la réduction du problème d'optimisation à un problème de décision, très sommairement -au bon rythme pour une démonstration esquissée, d'ailleurs. En fait je n'ai vraiment été éclairé qu'en allant lire l'exemple de réduction étudié dans en:Function problem ; bref je pense qu'il faudrait être plus précis dans l'article - la phrase «Le problème est NP-complet,» ne me semble pas d'un standard de précision suffisante pour un article mathématique de qualité. Je ne me risque pas à le faire tout seul sans livres sous la main, parce qu'il y a des mots barbares à utiliser autour du concept précis de «réduction», avec bien sûr les exigences de temps polynomial - j'écrirais des trucs vaseux si je n'ai pas des définitions précises sous la main, donc je laisse ça à ceux qui connaissent le sujet, désolé. Touriste * (Discuter) 27 août 2006 à 17:10 (CEST)

En toute rigueur, le problème est NP-complet sous la forme d'un problème de décision et NP-difficile (c'est à dire sans que la partie appartenance à NP de la preuve) sous la forme d'un problème d'optimisation. Il y a une correspondance entre les deux dans la mesure où trouver la solution optimale pourrait être de résoudre itérativement le problème de décision en faisant augmenter la valeur de k petit à petit. Je vais tenter d'ajouter ces précision de manière claire.--Julien Jorge 27 août 2006 à 20:27 (CEST)

J'ajoute que même si cette information peut-être intégrée à l'article, ceci est expliqué dans théorie de la complexité (ici) et me semble y a plus sa place (je parle de la correspondance optimisation <-> décision). Bon, ça ne prend pas trop de place donc on peut envisager de le remettre ici. Manproc 27 août 2006 à 20:59 (CEST)

Oui ce passage de Théorie de la complexité m'était passé sous les yeux, mais il est franchement peu précis et éclairant pour quelqu'un qui ne connaît pas le problème. Notamment il n'évoque pas la nécessité de faire la transformation du problème d'optimisation vers le problème de décision en temps polynomial (et c'est là que je manque d'ailleurs de la technicité pour modifier moi-même l'article) ; parce que si on ne borne pas d'une façon ou d'une autre le nombre d'opérations nécessaires pour faire la réduction, il est manifeste même à un profane que ça ne doit pas être bien intéressant. Touriste * (Discuter) 27 août 2006 à 21:04 (CEST)

C'est une réflexion pertinente et vraie, mais au final, dans le cadre de la théorie de la complexité, la transformation de problèmes (opti -> décision) ne représente pas grand chose : c'est tout à fait trivial. En revanche, ta réflexion s'applique tout à fait dans le cadre de la réduction : transformer un problème en un autre doit être polynomial (ce pourquoi on parle de réduction polynomiale) sous peine de reporter le problème ailleurs (d'où aussi des discussions intéressantes sur le codage de l'information).

Manproc 27 août 2006 à 22:33 (CEST)

J'ai ajouté les détails dont vous parlez, sur le lien optimisation <-> décision et une phrase pour parler de la complexité de la transformation. Pourriez-vous en faire une relecture ? (à la veille du verdict, c'est pas le moment d'y mettre des bétises ;-)). Peut-être faudrait-il aussi un lien "plus de détails sur théorie de la complexité" ?--Julien Jorge 27 août 2006 à 23:03 (CEST)

Ça me va plus ou moins, mais faire assurer une relecture à quelqu'un de bonne volonté mais qui ne connaît pas le sujet, c'est dangereux :-) Le problème vient plutôt des articles en amont que de l'article lui-même : il me semble qu'on n'a pas sous la main toutes les définitions nécessaires en cascade pour comprendre vraiment ce qu'on dit -j'ai une vague intuition, mais les détails... Par exemple si je pars me référer à Complexité_algorithmique pour comprendre ce que veut précisément dire le «algorithme polynomial» utilisé dans l'article, je ne suis pas plus avancé qu'en utilisant l'idée intuitive que j'en ai : certainement le nombre d'opérations doit être borné par une fonction polynomiale des données, mais que sont exactement les données ? Beuh. Je décroche quand on doit appliquer l'algorithme de décision plusieurs fois, le nombre de fois étant de l'ordre de grandeur du log en base 2 de

k

, mais alors la donnée c'est

k

, je croyais que c'était

n

. Je ne sais pas si j'arrive à faire passer mon inquiétude ou si vous êtes aussi perplexe devant mes réflexions que je le suis devant l'article...

Donc je me plains (mais ce n'est pas la faute de l'article, c'est la faute de tout son environnement) de ne pas savoir exactement ce qu'est la «polynomial-time Turing reduction» (je cite l'article anglophone en:Function problem où j'ai vu un peu comment ça marche mais sans savoir décoder les définitions qui sont derrière). Passons au concret après mes lamentations. Je pense que ce que vous avez ajouté, c'est trop ou trop peu, et plutôt trop. Il n'est pas question d'exposer DANS cet article ce qu'est une «polynomial-time Turing reduction» et l'expliquer "à moitié" comme vous avez essayé de le faire, ça ne me fait rien comprendre de plus que ce que je comprenais tout seul, tout en augmentant plutôt ma perplexité. Je préfèrerais que

1) on définisse très précisément le problème de décision associé. J'ai modifié un peu au pif la définition que vous donniez, qui ne me paraissait pas pouvoir être ça ; il faut être certain qu'on met quelque chose de juste.

2) dire qu'on peut ramener le problème d'optimisation au problème de décision en utilisant une formule mathématiquement très précise (sans doute la traduction française du «polynomial-time Turing reduction» mais là je n'en sais rien) et en s'attelant dans le futur à écrire les pages qu'il faut pour qu'on sache un jour ce que ça veut dire.

Tiens un petit point qui me chiffonne et qui ne semble précisé ni dans l'article anglais ni dans l'article français, quoiqu'il soit implicite. Les poids et les valeurs sont-ils supposés entiers ou réels ? Je suppose qu'ils sont implicitement entiers pour que le problème ait un sens informatique, mais c'est seulement une vague intuition ça aussi. Encore un truc où je vous embête, qui devrait être précisé dans l'article. Allez je crois que c'est tout pour mes critiques si peu constructives pour l'instant. Touriste * (Discuter) 27 août 2006 à 23:36 (CEST)

Pour le 1), j'avais en effet exprimé les choses à l'envers. Votre correction est bien.

Pour le 2), la réduction en temps polynomial concerne la transformation couverture d'ensemble -> sac à dos. Pour la correspondance « décision » <-> « optimisation », je ne crois pas qu'il y ait un critère plus particulier que celui décrit (mais là je ne suis pas sûr). Pour moi, il ne s'agit que de deux façons de voir le même problème (mais bon, je me trompe peut-être).

Pour la définition d'« algorithme polynomial », votre intuition est très bien. En général il s'agit de la taille des données, ça peut aller de la taille de leur représentation en machine, jusqu'à leur nombre. Le temps de résolution doit être borné par un polynôme des variables, que ce soit n, W ou n'importe quelle valeur qui serait donnée par l'utilisateur. En gros, un polynôme de toute quantité qui est propre à l'instance.

Pour ce qui est de revoir les pages « pour qu'on sache un jour ce que ça veut dire », mon avis est que le domaine de la complexité algorithmique peut être très très ardu. Je pense notamment aux preuves de NP-complétude qui, en plus d'être longues à écrire, nécessitent beaucoup de rigueur, une bonne compréhension des problèmes à lier et de l'imagination pour "trouver" une instance sur laquelle montrer le lien entre les problèmes. Peut-être que des mathématiciens-informaticiens sauraient nous décrire tout ça en termes simples, mais je peux vous dire que ce que je vois sur Wikipédia est bien plus compréhensible que ce que j'ai vu dans des bouquins (notamment sur le lien entre la complexité et les machines de Turing).

En tout cas, merci pour vos contributions sur l'article. Ça fait très plaisir de voir des votants qui ne restent pas les bras croisés et qui participent.--Julien Jorge 28 août 2006 à 00:21 (CEST)

[modifier] Programmation dynamique avec utilisation mémoire en O(n+W)

J'aimerais avoir plus d'informations a propros de l'optimisation de l'espace mémoire en O(n+W) Sur la page anglaise il est noté ceci though with some slight modifications we can reduce the space complexity to O(C). O(W) en français En faisant quelques tests je suis arrivé à une occupation mémoire en O(W). A partir de ça j'arrive à récupérer le gain optimal mais impossible de récupérer la liste des objets utilisés pour obtenir ce gain. Donc voilà j'aimerais plus d'infos là-dessus et savoir si ce n'est pas une erreur.

-- par poof65 ~~ le 5 février 2007 à 02:40 (CET)

On remarque que chaque tour de boucle de l'algorithme présenté dans l'article ne necessite que les valeurs de la colonne précédente (i-1) ou actuelle (i) et d'une case située plus haut (c ou c-w[i]). Du coup on peut n'utiliser qu'une seule colonne et écrire les nouvelles valeurs par dessus les précédentes. On obtient un algorithme avec une consommation mémoire en O(W).

Le problème de cette méthode, comme vous le faite remarquer, est qu'une fois que l'on a la valeur optimale, on ne peut plus déduire l'état des variables de la solution. --Julien Jorge 5 février 2007 à 19:56 (CET)

Merci, donc dans l'article on peut remplacer O(n+W) par O(W) ?

-- par poof65 ~~ le 5 février 2007 à 02:40 (CET)

et bien... je ne me souviens plus de l'algo en O(n + W), mais je crois qu'il permet encore de déduire l'état des variables dans les solutions optimales. Ce serait donc une réelle amélioration du O(nW). Alors que l'algo en O(W) pert de l'information. On pourrait donc ajouter l'information de l'existance du O(W), mais en aucun cas pour remplacer celle du O(n + W). --Julien Jorge 6 février 2007 à 01:11 (CET)