Partition de poids minimum d'un ensemble

**Sylvain Togni** · 18/07/2007, 19h32

Bonjour,

J'ai un ensemble E = {o1, o2, ..., oN} de N objets,
ainsi que M couples (sous-ensemble, poids), par exemple
({o3, o7}, 10)
({o2, o3, o8}, 20)
...
Je cherche quels couples choisir pour former une partition de E de poids minimum .

Y'a t-il un algo connu pour faire ça ?
Toute idée, pointeur sont les bienvenus, merci.

**PRomu@ld** · 19/07/2007, 08h47

Ca ressemble très fortement à un problème d'arbre couvrant de poids minimum. Regardes du coté des algos de Prim et Kruskall.

**Sylvain Togni** · 19/07/2007, 19h05

Oui, je crois notamment avoir trouvé une bijection entre mon problème et la recherche du plus court chemin dans un graphe. Malheureusement, cela mène à un algorithme très peu efficace car le graphe en question a un trop grand nombre de sommets. Mais je vais quand même essayer de m'inspirer de ce genre d'algo.

**PRomu@ld** · 19/07/2007, 19h11

Je ne vois pas trop le rapport entre les plus courts chemins et ce que tu demande, mais bon ... . Pour ce qui est des algos de plus court chemin, tu peux t'inspirer de Bellman Ford (ou Djikstra suivant certaines hypothèses)

As-tu essayé de voir du coté des algos de que je t'ai proposé ?

**souviron34** · 20/07/2007, 01h23

ya un truc que je comprends pas..

Si tu connais tes poids, ta somme est déterminée, non ??

Ou alors c'est les poids que tu veux déterminer ??

Si c'est le cas, un algo (physique

), consiste à faire une résolution par approximations successives (dychotomie).

Une résolution mathématique consiste en une méthode du Simplex...

**Sylvain Togni** · 20/07/2007, 10h05

En fait les sous-ensembles sont en très grand nombre et se chevauchent plus ou moins tous. Il faut que j'en choisisse quelques uns pour former exactement (sans chevauchement) l'ensemble E.

Les algorithmes d'arbres couvrants ne m'aident pas beaucoup, ils construisent la solution par descente de gradient (meilleur choix local), ce qui ne fonctionne pas dans mon cas.

Les algorithmes de plus court chemin (entre le noeud "ensemble vide" et le noeud "ensemble E") me permette de résoudre mon problème mais au prix d'un temps de calcul très élevé.

J'ai pourtant l'intuition qu'il doit exister un algorithme assez peu couteux à ce problème.

**PRomu@ld** · 20/07/2007, 10h10

(meilleur choix local), ce qui ne fonctionne pas dans mon cas.

Il me semble que tu si tu as un optimum local, ça te donne un optimum global. Tu as réellement essayé Kruskall ?

mais au prix d'un temps de calcul très élevé.

Quel algo de base à tu utilisé ?

**Sylvain Togni** · 20/07/2007, 10h28

Envoyé par PRomu@ld

Il me semble que tu si tu as un optimum local, ça te donne un optimum global.

Hélas non, par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
E = {o1, o2, o3}
C1 = ({o1}, 1)
C2 = ({o2}, 3)
C3 = ({o2, o3}, 10)
C4 = ({o1, o3}, 4)

Si je commence par choisir C1, ensuite mon seul choix possible c'est C3 qui coute 10. C2 + C4 est meilleur.

Envoyé par PRomu@ld

Quel algo de base à tu utilisé ?

Pour l'instant je parcours récursivement toutes les solutions, en essayant tous les choix possibles, ce qui explose dès que N ou M dépasse 100.

**PRomu@ld** · 20/07/2007, 10h45

Si je commence par choisir C1, ensuite mon seul choix possible c'est C3

En fait non, si tu pars de Kruskall (désolé, j'y tiens

), le choix s'effectue en prenant les arêtes de poids minimum.

Tu commences par C1 puis C2 puis C4. Or, le problème est que tu ne dois pas avoir de recouvrement.

Une méthode (je ne sais pas si elle est correcte), serait de ne pas considérer les singletons dans un premier temps, puis de les reprendre une fois que l'algorithme est terminé pour voir ce que l'on peut faire. L'idée serait en fait, de faire un arbre couvrant dans une première etape, et ensuite, à chaque commet où tu as plusieurs arrêtes, tu regardes, si tu ne peux pas éliminer les doublons par ces singletons.

Une autre idée, qui me vient à l'esprit, serait peut-être de s'inspirer du problème du sac à dos (ton problème y ressemble en fait), et à l'aide de la programmation dynamique tu peux peut-être trouver une solution acceptable en terme de temps (si tes coefficients sont entiers)

**Nemerle** · 20/07/2007, 11h38

Je partirais plus sur Prim...

Tu construis le graphes d'intersection de tes ensembles {o1,...,on}:

- les noeuds sont o1,...,on
- il y a une arrete entre op et oq ssi l'intersection d'op et oq est non vide

A partir de là, tu peux dejà, avant de commencer les calculs, regarder la gueule de ce graphe: composantes connexes, racines éventuelles,....

Ensuite, tu appliques Prim ou Kruskall... (cf par ex http://perso.ens-lyon.fr/eric.thierry/ALGO2/cours5.pdf

Mais je paries que tes difficultés proviennent simplement du fait que tu parcours récursivement toutes les possibilités, sans tenir compte de la tête de ton graphe !

**Sylvain Togni** · 20/07/2007, 12h33

Merci, j'ai trouvé, mon problème fait parti des problèmes de "set cover". C'est un mélange du problème "weighted set cover" (chaque sous-ensemble à un poids) et "exact cover" (les sous-ensembles choisis doivent être disjoins).

La mauvaise nouvelle c'est que c'est NP-complet (voire NP-hard).