Discussion :

[brennus]

salut
je ne sais pas si je suis au bon endroit et je m excuse d avance si ce ne pas le cas.

je souhaite separer une liste d' entier de facon a ce que la difference entre les sommes des nombres composants chacune des 2 listes resultantes de la separation soit la plus petite possible,je sais ca fait un peu barbare mais un exemple sera certainement plus simple a comprendre alors voila :

voici une liste a separer : 28,7,11,8,9,7,27.
voici le resultat escompte : 48 (compose avec 28,11,9) et 49(compose avec 7,8,7,27)
je n est pas forcement besoin des 2 listes resultantes

voila j espere que j ai ete suffisament clair et je vous remercie d avance

[FrancisSourd]

Cela peut être vu comme un problème d'ordonnancement à deux machines.
Les deux listes correspond aux activités exécutées sur les deux machines. Avec la partition donnée, la première machine termine à 48 et la deuxième à 49. Minimiser l'écart correspond aussi à minimiser la date de fin au plus tard.

Ce problème est NP-complet au sens faible mais se résout très bien par programmation dynamique (c'est très proche du schéma de programmation dynamique du problème de sac à dos qu'on trouve dans beaucoup de livres d'algorithmique).

Il faut considérer le sous-problème P(i,t) dans lequel on considère les i premiers nombres de la liste (v_1, v_2, ... v_n) et l'on veut que ces i nombres soient partitionnés de manière à ce que les deux listes ont une somme inférieure à t. On affecte Vrai ou Faux à P(i,t) selon que c'est faisable ou pas.
On a alors la récurrence
P(i,t) = P(i-1,t-v_i) ou P(i-1,t)
La complexité est O(nV) où n est le nombre de valeurs et V la somme des valeurs v_i.

C'est très condensé comme réponse, J'espère que c'est relativement clair.

[Admin]

La compléxité n'est pas O(n²V) plutot ?

[FrancisSourd]

La compléxité n'est pas O(n²V) plutot ?

Sauf erreur de ma part, c'est bien du O(nV): le tableau est de taille n*V et chaque case est remplie en O(1) en utilisant la formule de récurrence. C'est donc bien du O(nV).

[Admin]

D'ac ! je ne suis pas particulièrement doué en algorithmie, mais très intéressé.

J'avais trouvé le O(n²V) sur une documentation mais la technique ne devait pas etre la meme.

Voila la doc en question :
http://www.loria.fr/~jcohen/enseignement/SacADos.pdf

[FrancisSourd]

J'avais trouvé le O(n²V) sur une documentation mais la technique ne devait pas etre la meme.

Voila la doc en question :
http://www.loria.fr/~jcohen/enseignement/SacADos.pdf

C'est juste la définition du V qui change: dans la doc en question, V est la valeur maximale (Vmax) alors que mon V est la somme des valeurs (Vsum). On a bien sûr Vsum <= nVmax et donc ce qui est en O(n*Vsum) est en O(n²Vmax).

[brennus]

C'est très condensé comme réponse, J'espère que c'est relativement clair.

desole je suis peut etre lent a comprendre mais je n ai pas compris

[FrancisSourd]

Est-ce que tu connais la programmation dynamique? Si non, fais une recherche sur le web (il y a par exemple le lien de Gaël Donat) ou prend un livre d'algorithmique. Ce que je dit devrait ensuite te paraître plus clair.

Sinon, qu'est-ce que tu ne comprends pas exactement?

[2Eurocents]

Bonjour,

je souhaite separer une liste d' entier de facon a ce que la difference entre les sommes des nombres composants chacune des 2 listes resultantes de la separation soit la plus petite possible,je sais ca fait un peu barbare mais un exemple sera certainement plus simple a comprendre alors voila :

voici une liste a separer : 28,7,11,8,9,7,27.
voici le resultat escompte : 48 (compose avec 28,11,9) et 49(compose avec 7,8,7,27)
je n est pas forcement besoin des 2 listes resultantes

Ce problème m'a amusé ... au point que je me suis testé à essayer de le résoudre , voire à programmer ce que j'ai imaginé (en PERL) ... et ça marche.

Je ne me lancerai pas dans une analyse de complexité de ce que j'ai pondu car je n'en maîtrise plus les moyens théoriques depuis que j'ai terminé mes études.


N'ayant pas peur de l'explosion combinatoire, ni des importants niveaux de récursion, j'ai tenté l'approche par une fonction récursive.

On peut réduire notre problème à une fonction recevant un objectif à atteindre (la moitié de la somme des valeurs) et une liste de valeurs.

Si l'objectif est atteint (égal à 0), on retourne une valeur nulle, pour le signaler, et une liste vide (qui servira à reconstituer la chaine de valeurs retenues, par aggrégations successives lors du dépilage des appels récursifs).

Il suffit, pour chaque valeur de la liste, d'appeler cette même fonction avec un objectif diminué de cette valeur et une liste amputée de cette valeur et de toutes celles précédemment testées à ce niveau.

Si le retour de la fonction est nul, on retourne 0 et la liste retournée par la fonction, à laquelle on ajoute l'élément présentement testé, et qui contribue au succès.


Cette démarche, assez résumée, ici, est efficace si une solution exacte peut être trouvée.

Elle peut être grandement accélérée si la liste des valeurs est triée par ordre décroissant au préalable, et cela garantit que la solution retenue est celle qui emploie le moins de valeurs.

D'autres optimisations peuvent être faites (j'ai testé 8)) en évitant les appels récursifs pour toutes les valeurs de la liste supérieures à l'objectif.

Une autre optimisation, encore, consiste à arrêter, à un niveau, les appels récursifs si l'on a déjà testé des valeurs dont la somme est à concurrence de l'objectif

Une dernière amélioration peut être faîte pour trouver la meilleure approximation en retenant les résultats de tous les appels récursifs à un niveau et en retournant le meilleur si aucune solution exacte n'a été trouvée.

Cet alogrithme fonctionne très très bien sur de grosses listes (> 10000 valeurs) de nombres aléatoires.

Son principal défaut est un test systématique à réaliser dans le cas d'une liste contenant des valeurs toutes identiques et en nombre impair (101 fois la valeur 1000 par exemple).

Voila ...

A toi d'essayer de tirer quelque chose de tout ça ... moi j'y suis arrivé 8)

[2Eurocents]

J'ai continué à jouer avec cet algorithme, et l'implémentation que j'en ai fait en Perl...

Je tente de le pousser dans ses derniers retranchements et je cherche des listes de données le prenant en défaut ... Si vous avez des idées de cas tests ...

Je n'ai rien trouvé de plus efficace qu'une liste de valeurs identiques non partitionnable (nombre impair de valeurs paires). Les optimisations (arrêt de l'exploration dès que possible) permettent cependant de ne tester que 30% de toutes les combinaisons possibles.

Pour des valeurs aléatoires, plus il y a de valeurs, plus l'algorithme a de chance de trouver la solution exacte, ce qui accélère grandement le traitement, puisqu'on s'arrête alors, contrairement au cas des solutions approchées.

Plus les valeurs sont différentes, plus l'algorithme converge vite, même vers une solution approchée (cas d'un nombre impair de valeurs paires).

C'est assez amusant, finalement

[FrancisSourd]

Je tente de le pousser dans ses derniers retranchements et je cherche des listes de données le prenant en défaut ... Si vous avez des idées de cas tests ...

Pour avoir des instances difficiles il faut théoriquement que les valeurs aillent jusqu'à 2^n (n étant le nombre de valeurs). Comme tu l'as vu, si les valeurs sont bornées, la probabilité d'avoir un partage équitable tend vers 1 lorsque n tend vers l'infini.

Puisque cela t'amuse, voici un livre téléchargeable gratuitement sur des problèmes voisins:
http://www.or.deis.unibo.it/knapsack.html