Masalah Tukang Pos Cina: menemukan koneksi terbaik antara node derajat ganjil

Saya menulis sebuah Program, menyelesaikan Masalah Tukang Pos Cina (juga dikenal sebagai masalah inspeksi rute) dalam sebuah draph yang tidak diarahkan dan saat ini menghadapi masalah untuk menemukan tepi tambahan terbaik untuk menghubungkan node dengan derajat ganjil, sehingga saya dapat menghitung sirkuit Euler.

Mungkin ada (mempertimbangkan ukuran grafik yang ingin diselesaikan) kombinasi tepi yang sangat besar yang perlu dihitung dan dievaluasi.

Sebagai contoh ada node aneh derajat . Kombinasi terbaik adalah: $A, B, C, D, E, F, G, H$

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

di mana $AB$ berarti "ujung antara simpul $A$ dan simpul $B$ ".

Oleh karena itu pertanyaan saya adalah: adakah algoritma yang dikenal untuk memecahkan masalah itu dalam kompleksitas yang lebih baik daripada kekuatan kasar murni (menghitung dan mengevaluasi semuanya)?

€: Setelah beberapa upaya penelitian saya menemukan artikel ini , berbicara tentang "algoritma pencocokan panjang minimum Edmonds" tetapi saya tidak dapat menemukan pseudo-code atau pembelajar-deskripsi dari algoritma ini (atau setidaknya saya tidak mengenalinya, karena Google menawarkan banyak hits, algoritma yang cocok oleh J. Edmonds)

algorithms graph-theory graphs Sim
sumber

Wikipedia mengatakan bahwa ada algoritma untuk Masalah Tukang Pos Cina.

O (n^{3})

$O(n^3)$

hugomg

Saya tahu, tetapi saya masih penasaran ingin tahu bagaimana melakukan itu.

Sim

Catatan kuliah ini menangani Masalah Tukang Pos

Alex ten Brink

Sim, saya tertarik dengan perangkat lunak Anda karena saya menghadapi masalah pemetaan: help.openstreetmap.org/questions/13197/... Semoga sukses dengan proyek Anda. pm di pmbooks dot com

coba artikel yang saya tautkan menjelaskan algoritma pencocokan panjang minimum, tetapi karena kurangnya pengalaman dan kurangnya pseudo-code saya sayangnya tidak dapat mengimplementasikannya.

Sim

Jawaban:

Seperti dikomentari dalam komentar, Wikipedia memberikan pengurangan dari inspeksi rute ke kecocokan berat minimum . Vladimir Kolmogorov telah menerbitkan implementasi cepat dari versi tertimbang dari algoritma bunga Edmonds, di C ++ [1].

[1] V. Kolmogorov, Blossom V: Implementasi baru dari algoritma pencocokan sempurna biaya minimum . Komputasi Pemrograman Matematika , 1 (1): 43–67, 2009.

David Richerby
sumber

Dan jangan sebut itu "Masalah Tukang Pos Cina". Satu-satunya penghubung ke Cina adalah bahwa itu diperkenalkan oleh Mei-Ko Kwan dan kewarganegaraannya tidak relevan dengan masalah tersebut. Menyebutnya "Tionghoa" menunjukkan bahwa hal yang paling penting tentang dirinya adalah asal etnisnya. Kami tidak, misalnya, merujuk pada algoritma yang terkenal untuk menghitung jalur terpendek dalam grafik sebagai "algoritma Belanda" atau, lebih buruk lagi, "algoritma orang kulit putih". (Ya, saya keberatan dengan "teorema sisa Cina" karena alasan yang sama tetapi kuda itu melesat terlalu lama.)

David Richerby