Chinesischer Postbote Problem: Finden der besten Verbindungen zwischen Knoten ungeraden Grades

Ich schreibe ein Programm, löse das chinesische Postbotenproblem (auch als Routeninspektionsproblem bekannt) in einem ungerichteten Draph und stehe derzeit vor dem Problem, die besten zusätzlichen Kanten zu finden, um die Knoten mit ungeradem Grad zu verbinden, damit ich eine Eulersche Schaltung berechnen kann.

Möglicherweise gibt es (in Anbetracht der Größe des Diagramms, das gelöst werden soll) eine enorme Kombination von Kanten, die berechnet und ausgewertet werden müssen.

Als Beispiel gibt es den ungeraden Grad - Knoten . Die besten Kombinationen könnten sein:$A, B, C, D, E, F, G, H$

1. $AB$ , , ,E $CD$$EF$$GH$
2. $AC$ , , ,E H $BD$$EH$$FG$
3. $AD$ , , ,E G $BC$$EG$$FH$
4. $AE$ ....

wobei "Kante zwischen Knoten und Knoten " bedeutet.A $AB$$A$$B$

Daher lautet meine Frage: Gibt es einen bekannten Algorithmus, um dieses Problem in einer Komplexität zu lösen, die besser ist als reine Brute Force (Berechnung und Bewertung aller)?

€: Nach einigen Recherchen habe ich diesen Artikel gefunden, in dem es um den "Edmonds 'Minimum-Length-Matching-Algorithmus" geht, aber ich kann keinen Pseudocode oder Lernbeschreibungen dieses Algorithmus finden (oder zumindest erkenne ich sie nicht als Google bietet viele Treffer und Matching-Algorithmen von J. Edmonds)

Wie in den Kommentaren erwähnt, reduziert Wikipedia die Routeninspektion auf Übereinstimmungen mit minimalem Gewicht . Vladimir Kolmogorov hat eine schnelle Implementierung der gewichteten Version von Edmonds 'Blütenalgorithmus in C ++ veröffentlicht [1].

[1] V. Kolmogorov, Blossom V: Eine neue Implementierung eines Algorithmus zur perfekten Anpassung bei minimalen Kosten . Mathematical Programming Computation , 1 (1): 43–67, 2009.