Tambahan di bawah ini, menjelaskan persyaratan :k(k−1)
Jadi, jika Anda memeriksa istilah dalam ekspresi, Anda dapat membayangkan (sebagai analogi) istilah adalah enumerasi dari semua string biner yang mengandung 1 yang memiliki 1 di posisi pertama. Dengan kata lain, kita membiarkan setiap posisi dalam string biner mewakili pilihan apakah salah satu dari kota dalam masalah berada dalam subset persis yang kita pertimbangkan pada saat itu. Jadi, untuk 5 kota, 10101 sesuai dengan subset {1,3,5}.(n−1k)kn
Jadi, untuk menghitung semua subset dari {1, ..., }, kita cukup menghitung melalui setiap subset biner (yaitu menghitung melalui string biner) dengan ukuran = 2 (yaitu string biner dengan ukuran yang berisi dua 1), kemudian size = 3, lalu size = 4, ... lalu size = n. (Perhatikan bahwa ukuran = 1 himpunan bagian harus berisi hanya kota pertama, dan dengan demikian tidak relevan untuk menghitung jarak parsialnya, karena jarak dari 1 -> semua kota lain di himpunan bagian -> 1 persis 0.)nn
Pada setiap himpunan bagian dengan kota , kita harus mempertimbangkan hingga jalur parsial kandidat. Secara khusus, jalur optimal dan total dapat melintasi seluruh subset yang diberikan dan berakhir di salah satu kota , tidak termasuk kota pertama. Kemudian, untuk setiap kandidat sub-jalur, kami menghitung tur optimal hingga titik tersebut sebagai minimum dari yang sebelumnya, ukuran = sub-jalur ditambah jarak dari kota terminal untuk sub-jalur tersebut ke kota terminal untuk sub-jalur kandidat saat ini. Ini memberi perbandingan yang harus kita buat. Perbedaan antara istilah dankk−1k−1k−1(k−1)(k−2)(k−1)(k−2)k(k−1)Istilah dalam analisis yang dikaitkan adalah perbedaan notasi (saya akan menjumlahkan pada rentang yang berbeda, mengingat definisi saya tentang daripada yang mereka lakukan). Paling tidak, bagaimanapun, itu harus menggambarkan kompleksitas urutan kuadrat dari istilah itu.k
Betapa menarik - Saya baru saja menyelesaikan pengkodean algoritma yang tepat ini dalam C ++ beberapa menit yang lalu. (Jadi maafkan garis singgung dari teori murni ke dalam sedikit diskusi praktis. :))
Biayanya waktu dan ruang - setidaknya di bawah implementasi saya. Namun secara praktis, ketika kebutuhan ruang Anda tumbuh secepat itu, mereka menjadi jauh lebih menyakitkan daripada persyaratan waktu. Sebagai contoh, pada PC saya (dengan 4 GB RAM), saya dapat memecahkan contoh dengan hingga 24 kota - lebih dari itu, dan saya kehabisan memori.O(2nn2)O(2nn)
Tentu saja, saya bisa saja menjadi programmer yang buruk, dan Anda mungkin bisa melakukan lebih baik daripada saya dalam praktik. :)
Sunting: Sedikit lebih spesifik pada satu detail dari pertanyaan Anda: Istilah berasal dari fakta bahwa Anda harus, dalam kasus terburuk, menghitung jarak parsial, optimal dari subset sebelumnya (paling banyak ada dari mereka; catatan bahwa dijumlahkan lebih dalam analisis Anda terhubung) dengan yang sekarang. Ini membutuhkan, sekali lagi dalam kasus terburuk, perbandingan dengan himpunan bagian ukuran untuk total .k(k−1)nknO(k)k−1O(k2)
Juga, jika penjelasan saya tidak cukup jelas, berikut adalah beberapa catatan kuliah yang bagus dari Vazirani ( PDF ). Gulir ke bawah ke P. 188 untuk diskusi tentang TSP, termasuk analisis Held-Karp.
Catatan utama
Penting untuk dicatat bahwa kami menghitung dan menyimpan bukan
"jarak jalur optimal untuk
combination of k cities
"tetapi
"jarak jalur optimal untuk
combination of k cities
DAN untukend-point city from this combination
".Memahami hal itu akan membantu makna dua pengganda pertama dalam rumus berikut.
Fase pertama
Jumlah operasi pada fase pertama adalah:∑k>=2(n−1k−1)choose city combinationof size = k−1⋅(k−1)choose city to be the lastfrom k−1 citiesin chosen combination⋅((n−1)−(k−1))choose citythat is not in chosen combinationto add to path
Superskrip yang hilang berarti jumlahk=n−1
(n−1n−2)⋅(n−2)⋅1 n−1
for all k>=2 that is valid for binomial coefficient
. Jadi jangka waktu penjumlahan bukan nol yang berlaku yang terakhir adalah untuk Ini berarti bahwa jumlah kami tidak menangkap pilihan terakhir kota untuk terhubung ke kota pertama. Ada kota yang terhubung ke kota pertama. Jadi akhirnya kita akan menambahkan istilah ini ke penjumlahan.Biarkan mengubah rumus menjadi bentuk yang Anda berikan yang juga ada di halaman Wikipedia Held-Karp .
Fase kedua
Fase kedua adalah memulihkan jalur optimal dengan tanda yang telah kami buat di fase pertama bersamaan dengan jarak komputasi.
Untuk setiap jalur optimal "untuk
combination of k cities
DAN untukend-point city from this combination
" kami telah menyimpan kota kedua hingga terakhir.Untuk menelusuri jalur optimal kita perlu meminta beberapa struktur data untuk mengembalikan kota kedua-ke-terakhir "untuk
∑k>=2n−1k=(n)(n−1)2−1
combination of k cities
DAN untukend-point city from this combination
". Jadi struktur data ini harus sepertiMap<combination of k cities, Map<last city, second-to-last city>>
. Sebagai indekscombination of k cities
kita dapat menggunakan, misalnyabinary_string[city id]=1 if city id is in combination
,. Jadi kita perlu melihat semua elemencombination of k cities
untuk mengidentifikasi kombinasi dan mengindeks struktur data kita. Ini memberi kita jumlah operasi untuk fase kedua:sumber