Problème du facteur chinois: trouver les meilleures connexions entre les nœuds de degré impair

J'écris un programme, résolvant le problème du facteur chinois (également connu sous le nom de problème d'inspection d'itinéraire) dans un graphique non orienté et actuellement confronté au problème pour trouver les meilleurs bords supplémentaires pour connecter les nœuds à un degré impair, afin que je puisse calculer un circuit eulérien.

Il peut y avoir (compte tenu de la taille du graphe à résoudre) une énorme combinaison d'arêtes qui doivent être calculées et évaluées.

A titre d'exemple , il existe des noeuds de degré impair . Les meilleures combinaisons pourraient être: $A, B, C, D, E, F, G, H$

, , , $AB$ $CD$ $EF$ $GH$
, , , $AC$ $BD$ $EH$ $FG$
, , , $AD$ $BC$ $EG$ $FH$
.... $AE$

où signifie "bord entre le nœud et le nœud ". $AB$ $A$ $B$

Par conséquent, ma question est: existe-t-il un algorithme connu pour résoudre ce problème dans une complexité meilleure que la force brute pure (les calculer et les évaluer tous)?

€: Après quelques efforts de recherche, j'ai trouvé cet article, parlant de "l'algorithme de correspondance de longueur minimale d'Edmonds", mais je ne trouve aucun pseudo-code ou description d'apprenants de cet algorithme (ou du moins je ne les reconnais pas, comme Google offre beaucoup de hits et des algorithmes de correspondance par J. Edmonds)

algorithms graph-theory graphs Sim
la source

Wikipedia sait qu'il existe un algorithme

O (n^{3})

$O(n^3)$ pour le problème du facteur chinois.

hugomg

Je sais, mais je suis toujours curieux de savoir comment faire ça.

Sim

Ces notes de cours traitent du problème du facteur chinois: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf

Alex ten Brink

Sim, je suis intéressé par votre logiciel car je suis confronté à un problème de cartographie: help.openstreetmap.org/questions/13197/… Bonne chance avec votre projet. pm at pmbooks dot com

essayez l'article que j'ai lié, il décrit un algorithme de correspondance de longueur minimale, mais en raison de mon manque d'expérience et du manque de pseudo-code, je n'ai malheureusement pas pu l'implémenter.

Sim

Réponses:

Comme indiqué dans les commentaires, Wikipedia propose une réduction de l'inspection des itinéraires aux correspondances de poids minimum . Vladimir Kolmogorov a publié une implémentation rapide de la version pondérée de l'algorithme Blossom d'Edmonds, en C ++ [1].

[1] V. Kolmogorov, Blossom V: Une nouvelle implémentation d'un algorithme d'appariement parfait à moindre coût . Calcul de programmation mathématique , 1 (1): 43–67, 2009.

David Richerby
la source

Et n'appelons pas cela le "problème du facteur chinois". Le seul lien avec la Chine est qu'elle a été introduite par Mei-Ko Kwan et que sa nationalité est sans rapport avec le problème. Le nommer «chinois» suggère que la chose la plus importante à son sujet est son origine ethnique. Par exemple, nous ne nous référons pas à l'algorithme bien connu pour calculer les chemins les plus courts dans les graphiques comme "l'algorithme néerlandais" ou, pire encore, "l'algorithme de l'homme blanc". (Oui, je m'oppose au "théorème du reste chinois" pour la même raison, mais ce cheval a boulonné il y a trop longtemps.)

David Richerby