Problem chińskiego listonosza: znalezienie najlepszych połączeń między węzłami nieparzystego stopnia

Piszę program, rozwiązując problem chińskiego listonosza (znany również jako problem z inspekcją trasy) w niedokierowanym drafcie i obecnie napotykam problem, aby znaleźć najlepsze dodatkowe krawędzie do łączenia węzłów o dziwnym stopniu, dzięki czemu mogę obliczyć obwód Eulera.

Może istnieć (biorąc pod uwagę rozmiar wykresu, który chce zostać rozwiązany) ogromna kombinacja krawędzi, które należy obliczyć i ocenić.

Przykładowo istnieje nieparzystych stopnia węzłów . Najlepsze kombinacje mogą być: $A, B, C, D, E, F, G, H$

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

gdzie oznacza „krawędź między węzłem i węzłem ”. $AB$ $A$ $B$

Dlatego moje pytanie brzmi: czy istnieje znany algorytm rozwiązania tego problemu w złożoności lepszej niż czysta brutalna siła (obliczanie i ocenianie ich wszystkich)?

€: Po pewnym wysiłku badawczym znalazłem ten artykuł, mówiąc o „algorytmie dopasowania minimalnej długości Edmondsa”, ale nie mogę znaleźć żadnego pseudokodu lub opisów tego algorytmu dla uczących się (a przynajmniej ich nie rozpoznaję jako Google oferuje wiele trafień pasujących algorytmów J. Edmondsa)

algorithms graph-theory graphs Sim
źródło

Wikipedia twierdzi, że istnieje algorytm dla problemu chińskiego listonosza.

O (n^{3})

$O(n^3)$

hugomg

Wiem, ale wciąż jestem ciekawy, jak to zrobić.

Sim

Te uwagi do wykładu dotyczą

Alex ten Brink

Sim, interesuję się twoim oprogramowaniem, ponieważ mam problem z mapowaniem: help.openstreetmap.org/questions/13197/... Powodzenia w twoim projekcie. pm at pmbooks dot com

wypróbuj artykuł, który połączyłem, opisuje algorytm dopasowania minimalnej długości, ale z powodu mojego braku doświadczenia i braku pseudokodu niestety nie byłem w stanie go wdrożyć.

Sim

Odpowiedzi:

Jak zauważono w komentarzach, Wikipedia ogranicza przegląd tras do dopasowań o minimalnej wadze . Vladimir Kolmogorov opublikował szybką implementację ważonej wersji algorytmu kwitnienia Edmondsa w C ++ [1].

[1] V. Kołmogorow, Blossom V: Nowa implementacja algorytmu perfekcyjnego dopasowania minimalnego kosztu . Mathematical Programming Computation , 1 (1): 43–67, 2009.

David Richerby
źródło

I nie nazywajmy tego „problemem chińskiego listonosza”. Jedyny związek z Chinami polega na tym, że został wprowadzony przez Mei-Ko Kwana, a jego narodowość nie ma znaczenia dla problemu. Nazwanie go „chińskim” sugeruje, że najważniejsze w nim jest jego pochodzenie etniczne. Na przykład nie odnosimy się do dobrze znanego algorytmu obliczania najkrótszych ścieżek na wykresach jako „algorytmu holenderskiego” lub, co gorsza, „algorytmu białego człowieka”. (Tak, sprzeciwiam się „twierdzeniu o chińskiej reszcie” z tego samego powodu, ale ten koń

spieprzył się