Discussion :

[Sylvain Togni]

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]

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]

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]

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]

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]

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.