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 ) serait déjà pas mal :-)