Discussion :

[Fabricer66]

Bonjour,

J'ai une liste de nombres que je souhaite répartir en un minimum de groupes dont la somme des nombres contenus est inférieur à une valeur prédéfinie.

Typiquement, ce type d'algorithme permet de répartir des fichiers à archiver sur plusieurs CD.

J'ai tenté une approche "systématique" consistant à identifier toutes les combinaisons possible et rechercher celle qui propose le nombre minimum de groupes. après les premiers tests, pour une trentaine de nombres à répartir, il faudrait à mon PC 1,78414E+23 années... Je suis un peu à cours de temps...

Je pense donc qu'il doit y avoir une solution plus "intéligente" que de chercher toutes les combinaisons et j'éspère que l'intélligence artificielle peut m'aider.


Pour l'exemple, j'essaie de faire des groupes de totaux inférieurs ou égaux à 428 avec les nombres suivants :

52,44, 48, 64, 28, 40, 28, 64, 104, 40, 36, 60, 28, 60, 28, 32, 44, 56, 60, 28, 288, 32, 24, 40, 52, 52, 48, 32, 36, 52, 52, 56


merci d'avance.

Fabrice

[ToTo13]

Bonjour,

dans ton problème, qui est un ce que l'on nomme un problème du "sac à dos", il n'y pas de solution miracle (problème NP-complet) mais on s'en sort souvent très bien avec des méta heuristiques.
Je te conseille de tout simplement commencer par tester la méthode la plus simple qui consiste trier les nombres par ordre décroissant, puis de les positionner dans les différents groupes (les gros sont les plus dur à placer ).
Ca fonction parfois pas trop mal.

Sinon, regarde du coté du "recuit simulé" ou "méthode tabou".

[Fabricer66]

Merci pour la réponse.

Je vais tester les solutions que tu me proposes. Elles devraient couvrir la majorité des cas d'une façon assez satisfaisante.

Je crains quand même que la solution consistant à positionner les plus gros ne donne pas toujours la meilleure solution.

[Scorpi0]

Ton exemple n'est typiquement pas le genre de problème ou un optimal est indispensable.

Si au lieu de graver 30 CD, tu en grave 31, ce n'est pas forcément une grosse perte, surtout si la solution à 30 CD te prend plusieurs années à calculer.

Dans les problème NP-complets, mieux vaut une bonne solution rapidement qu'une solution parfaite dans 1 an.

Ça m'étonnerait d'ailleurs que les sites comme google map ou mappy te propose toujours l'optimum dans ton chemin !

[PRomu@ld]

Ça m'étonnerait d'ailleurs que les sites comme google map ou mappy te propose toujours l'optimum dans ton chemin !

Et bien en théorie rien ne les empêche de te le donner de manière exacte (c'est peut-être ce qu'ils font), le problème n'est pas NP-Complet (plus court chemin dans un graphe).

[ToTo13]

Je crains quand même que la solution consistant à positionner les plus gros ne donne pas toujours la meilleure solution.

Attention... Problème NP-Complet <=> Pas de solution à coup sûr.
Je dis juste que le rapport efficacité/simplicité est très convenable.

[JeitEmgie]

Merci pour la réponse.

Je vais tester les solutions que tu me proposes. Elles devraient couvrir la majorité des cas d'une façon assez satisfaisante.

Je crains quand même que la solution consistant à positionner les plus gros ne donne pas toujours la meilleure solution.

un algorithme simple qui ne donne pas de trop mauvais résultats :

0. préambule: tous les fichiers > taille du media sont segmentés, et on tient compte d'une taille minimum de segment (contrainte : cette taille doit être inférieure à la moitié de la taille du media de destination…)

1. trier la liste des fichiers par taille
2. tous les fichiers dont la taille est telle que l'espace résiduel sur le media est inférieur à la taille du plus petit fichier peuvent être "sortis" chacun sur un media
3. tant qu'il y a des fichiers à répartir
créer un nouveau media
ajouter le plus gros fichier
(et l'enlever de la liste des fichiers à répartir)
tant que le media n'est pas "plein" (càd tant qu'on trouve un fichier à mettre dessus, donc que la taille résiduelle est > à la taille du plus petit fichier…)
ajouter le fichier qui remplit le mieux l'espace disponible (et l'enlever de la liste des fichiers à répartir)
ftant
4. à la fin reste une optimisation optionnelle possible
si la taille occupée du dernier media est inférieure à la somme des espaces disponibles (on ne prend que les espaces disponibles > taille minimun de segment admise) alors il est possible de répartir le contenu du dernier media en segmentant les fichiers attribués pour les mettre sur les autres…

notez qu'exigez que les segments d'un fichier soient sur des media les plus consécutifs possibles complique passablement le problème (en particulier dans la phase d'optimisation, cela peut même la faire échouer… càd se retrouver avec un ou plusieurs fichiers qu'on aura quand même pas pû répartir sur les autres media et donc le nombre de media nécessaires sera toujours le même… on aura segmenter des fichiers pour rien… à moins d'admettre quand dernier ressort on accepte alors un ordre de segments différent…) et refuser les fichiers dont la taille est supérieure à celle du media le simplifie seulement un peu…

PS
et évidemment n'oubliez pas que tous les calculs doivent se faire en nombre de secteurs utilisés sur le media de destination et non en bytes…
cela ne change rien à la logique de l'algorithme choisi, mais par contre cela évitera les mauvaises surprises…

[Fabricer66]

Merci à tous pour votre aide.

[CedricMocquillon]

Alors oui le problème de sac à dos est un problème NP-Difficile mais c'est un problème NP-Difficile au sens ordinaire (ou faible). Cela veut dire que l'on peut le résoudre à l'aide d'un algorithme pseudo-polynomial qui est de O(nW) avec n le nombre d'élément et W la capacité du sac. A ta place je commencerai donc par tester cet algorithme (disponible sur wikipedia) et si (et seulement si je dirai) le temps de résolution est trop long pour toi, tourne toi alors vers une heuristique. C'est quand même dommage de proposer directement une heuristique pour un problème qui en pratique est bien résolu à l'optimal. Mais sinon pour en revenir à ton problème, pour moi ce n'est pas un problème de sac à dos mais un problème de bin packing (en effet, tu cherches à minimiser le nombre de bin nécessaire pour mettre tes n objets), ce qui n'est pas le même problème et qui je crois est NP-Difficile au sens fort (cette fois). Pour les méthodes de résolution qui vont bien, cf wikipedia (désolé, je n'ai pas cherché d'autre liens plus pertinents). Dans tout les cas, fais une recherche sur le web, c'est pas en 5 ou 10 min de réflexion que tu trouveras une méthode efficace alors qu'il y a des universitaires qui planchent dessus depuis de nombreuses années alors autant en profiter

[fiduce]

Bien que tardivement, je suis assez d'accord avec le contributeur précédent.

Ce problème est rattaché à toute une famille de problèmes abondamment traitée dans la littérature. Les "garbage collectors" (ramasse miettes, avec blocs figés) posent, par exemple, le même genre de problème (sauf que les "CD" n'ont alors pas tous la même taille et qu'on cherche à dégager la plus grande place vide possible d'un seul tenant).

Bourrer un CD au maximum est assez facile. Mais ça ne permet pas d'aboutir à la solution optimale quand il y a de quoi remplir de nombreux CD.

Bourrer au maximum un premier CD (et donc trouver l'optimum du problème quand toute la compil tient sur au maximum 2 CD) est un objectif relativement abordable : il s'agit d'un problème de partition qui se programme très bien (avec efficacité) en algorithmique dynamique, tenant compte de la complexité "pseudo-polynomiale" (sachant que les nombres donnés en exemple sont petits).

La mauvaise idée serait de transposer bètement l'algorithme pseudo-polynomial dans un espace multi-dimensionnel (les vecteurs devenant des matrices à 2 dimensions pour bourrer jusqu'à 3 CD, puis des matrices à 3 dimensions pour 4 CD, etc) : les temps de traitement exploseraient.

Dans tous les cas, on fait bien de commencer par calculer la taille totale des fichiers à caser (somme de la taille des fichiers) qu'on divise par la capacité d'un CD pour obtenir le nombre de CD cibles minimum (si on trouve une solution qui passe dans ce nombre de CD, on peut arrêter de chercher).

Première idée : Bourrer successivement plusieurs CD.

"Bourrer au maximum" un premier CD, puis réitérer l'algorithme avec les morceaux qui restent (en bourrant un second CD) jusqu'à plus soif.

Problème : pour notre problème global, on peut trouver un agencement plus efficace que celui qui consiste à bourrer séquentiellement chaque CD.

Idée : essayer de "favoriser les fichiers les plus gros dans les premiers CD" en introduisant un critère supplémentaire.

On passe donc à un problème de sac à dos (problème "KNAPSACK" : toujours pseudo-polynomial) en introduisant une valeur "profit" (pour rester conforme à la littérature sur ce sujet) pour chaque fichier. On calcule ce "profit" de façon à favoriser les gros fichiers par rapport aux petits : en définissant le profit comme une fonction non-linéaire de la taille (par exemple la taille au carré), on favorise (outrageusement) les plus gros paquets.

Rappel : le problème du sac à dos consiste à bourrer un sac/CD en y mettant le sous-ensemble de fichiers qui génère le plus de "profit" (sans dépasser la capacité du sac/CD). On a donc deux valeurs par fichier : sa taille et son "profit". La taille sert de contrainte forte. Le profit est le critère à optimiser.

L'astuce consiste à moduler la non-linéarité du profit en déroulant plusieurs fois l'algorithme avec, par exemple, la formule :
profit = exp( coef * ln(taille) )

coef variant entre 1 et 2 (voire plus haut).

Pour mémoire, si coef vaut 1, on a (profit=taille).
Si coef vaut 2, on a (profit=taille²).

On commence par dérouler tout l'algorithme (bourrage optimisé knapsack du premier CD, bourrage optimisé knapsack du second CD avec ce qu'il reste, etc) avec un coef valant 1 (c'est à dire profit = taille ... le problème du sac à dos est alors dégradé en problème de bourrage maximum). On obtient un premier nombre de CD résultat.

Puis, si on n'a pas atteint le nombre cible/minimum de CD, on recommence en augmentant légèrement le coefficient (par exemple, on passe à 1,05).

On suppose que le nombre de CD résultat doit décroître (on fait une "descente" vers l'optimum). On s'arrête donc si, au cours d'un essai ultérieur (avec un coef plus élevé), on aboutit à une augmentation du nombre de CD. On s'arrête aussi une fois arrivé à 2 (profit = taille au carré).

On continue ainsi par pas de 0,05 ... jusqu'à arriver à (coef = 2) ou à une croissance du nombre de CD résultat.
On peut aussi se dire que, quand le nombre de CD n'évolue pas alors qu'on a augmenté le coef, le dernier CD doit toutefois être moins rempli (quand on se rapproche d'une meilleure solution, le dernier CD disparait). Ca permet de s'arrêter plus (trop ?) tôt.

Evidement, il y a de nombreuses suppositions fausses dans cette technique (qui n'est pas une heuristique dans le sens où rien ne garantit qu'on atteindra l'optimum, même si on fait évoluer coef par pas très petit) ... mais avec la base obtenue, on peut, si on n'est toujours pas satisfait, essayer d'appliquer une heuristique de voisinage.

En pratique, en très peu d'itérations (une seule même), on arrive à quelque chose de très correct. On peut également moduler le coefficient de calcul des profits après chaque CD bourré (au lieu de le faire une seule fois par solution trouvée), en calculant celui-ci en fonction de variables statistiques calculées sur la distribution des tailles de fichiers restant à placer. Mais on entre alors encore davantage dans une phase de tatonnement.

Exemple :
Taille des CD : 20
Fichiers : 6, 6, 6, 11, 11, 11

Si on bourre le premier CD avec coef=1 on obtient : 6 + 6 + 6
Il reste trois autres CD chargés à 11. Total 4 CD.

Il faut un coef de 1,15 pour que la solution à trois CD de 11+6 prenne le dessus.

[cedriku]

C'est clairement un probleme de bin packing en 1 dimension. Suivant l'echelle de temps que tu veux laisser au programme (plutot de l'ordre de la milliseconde, seconde, minute... ?) et du nombre de nombres devant etre casés, tu peux envisager une methode exacte (=qui trouve la solution optimale). Apres il peut etre interessant de savoir si la repartition de tes nombre est homogene ou pas car certaines methodes fonctionnent bien lorsque les nombres sont a peu pres egaux et d'autres fonctionnent bien lorsque les nombres sont eloignés.