Algorithme pour trouver efficacement le matching complet (appairement) optimal ?

Bonjour,

Je cherche un algorithme qui permettrait de trouver efficacement un matching optimal. Plus précisément, voici mon problème:

On dispose de 2*n éléments que l'on souhaite regrouper en n paires. À chaque paire d'éléments (i, j) (i != j) est associé un coût c_ij, et on souhaite minimiser la somme des coûts des paires choisies. (toutes les paires (i, j) sont possibles)

Ce problème peut également être vu comme un problème de graphe où les éléments sont les noeuds et les paires sont les arrêtes. Sous cette forme on recherche donc un matching complet (chaque élément appartient à un arc du matching) optimal (la somme des arcs choisis est minimum).

Évidemment il est très facile de trouver un algo en O(n!) mais j'ai besoin de quelque chose de beaucoup plus efficace, alors je voudrais savoir s'il y a un algorithme connu pour le faire ? Idéalement un algo en complexité temporelle polynomiale... (je prie donc pour que ce ne soit pas un problème NP-Complet...)

Ce qui m'intéresse c'est surtout de connaître la valeur de la fonction objectif à l'optimum, mais avoir une borne inférieure (assez proche quand même évidemment :roll:) serait déjà pas mal :-)

Soit f(n) le nombre de paires possibles:
f(n)= (2n)*(2n+1)/2
donc f(n) est en n*n.
Trier le tableau des coûts correspondants par Quicksort
l'algo est donc en f(n)*log(f(n)).
On reste en n*n*log(n).
Puis on prend le plus petit élément du tableau trié et la paire correspondante, et on élimine du tableau trié tous les coûts correspondant à des paires référencant un des éléments de la première paire choisie.et ainsi de suite jusqu'à épuisement.
Les test seront donc au maximum en :
f(n)+(f(n)-1)+(f(n)-2) + ..... + 2 + 1
soit en f(n)*(f(n)+1)/2
donc en n puissance 4
comme n*n*log(n) est négligeable devant n*n*n*n
On doit rester en n puissance 4.

Bonjour,

Est-ce que chaque élément d'une paire appartient à un ensemble différent (graphe bipartite complet) ?

C'est polynomial.

Pour un graphe général, il y a l'algorithme de Gabow:
http://elib.zib.de/pub/Packages/math...hing/weighted/

Vu que tu sélectionne n paires, les problèmes de minimisation et maximisation sont équivalents.

Je ne pense pas qu'on puisse tirer parti du fait que ton graphe ait l'air complet (puisqu'on peut rendre un graphe non complet en un gaphe complet avec des arêtes de coût très grand).

Merci beaucoup pour vos réponses, je pense que je suis sur la bonne voie.

Zavonen: oui, j'avais aussi pensé à un algorithme similaire mais je me suis vite rendu compte qu'il n'était pas optimal:
suppose que tu as 4 noeuds A, B, C et D avec les coûts suivants:
A-B = 0
A-C = B-D = 1
C-D = 4
(les autres coûts sont supposés infinis)
ton algo choisit A-B et C-D pour un coût total de 4, alors qu'il existe une meilleure solution avec A-C et B-D pour un coût de 2.

sovitec: non il n'est pas biparti (je pensais que c'était évident d'après ma description)

Francis: merci pour ta réponse, cela semble être ce que je cherchais. Le site que tu donnes fournit une implémentation en C qui ne me paraît pas des plus claires, et comme c'est à utiliser dans un programme java ça ne me conviendra pas... Enfin cela m'a bien aidé à orienter ma recherche, même si dans la plupart des cas je suis tombé sur des articles de chercheurs généralement pas piqués des vers (en gros faut se farcir toute la théorie et ça j'en ai pas vraiment besoin...)

Pour ceux que cela intéresse, voici le fruit de mes recherches sur le net:

• Le mieux est de chercher "minimum weight perfect matching" (sans les guillemets)
• Une applet qui illustre le principe en 2D: (mais le code semble assez difficile à récupérer...)
  http://www.math.sfu.ca/~goddyn/Cours..._Matching.html
• Une autre implémentation en C pour l'heuristique du TSP:
  http://www.cs.utoronto.ca/~neto/research/lk/
• Scilab semble fournir également une implémentation dans sa boite à outil MetaNet.
• LEDA également: http://www.algorithmic-solutions.inf..._matching.html
• Une package java qui semble pouvoir faire ce que je veux (yapluka):
  Jicos et son interface Graph
• ... de nombreux pdf sont disponibles également

Je vais marquer ce sujet comme résolu mais si d'autres ont déjà eu une expérience avec ce problème, cela me ferait plaisir d'avoir encore des réponses ;)

Bonjour

Ton problème est équivalent à un problème d'affectation avec des coûts infinis sur la diagonale. C'est un problème polynomial résolu en O(n^3)
http://en.wikipedia.org/wiki/Assignment_problem "The assignment problem is finding a maximum weight matching in a weighted bipartite graph."

Citation:

---

Envoyé par CedricMocquillon

Bonjour

Ton problème est équivalent à un problème d'affectation avec des coûts infinis sur la diagonale. C'est un problème polynomial résolu en O(n^3)
http://en.wikipedia.org/wiki/Assignment_problem "The assignment problem is finding a maximum weight matching in a weighted bipartite graph."

---

Justement, là, le graphe n'est pas biparti... mais le problème est également résolu en O(n^3) avec les algorithmes cités ci-dessus. La principale différence, c'est que dans le cas du graphe biparti, il suffit de trouver des chemins augmentants alors que dans les graphes généraux, on a besoin de "blossoms" (circuit de longueur impaire)

Denis Lapoire vient de mettre en ligne un excellent cours sur la théorie des graphes qui traite de ce problème dans le chapitre 11.
http://lapoire.developpez.com/algorithmique/graphes/