Kompleksitas waktu dari algoritma Bellman-Held-Karp untuk TSP, ambil 2

Sebuah pertanyaan baru-baru ini membahas algoritma pemrograman dinamis klasik sekarang untuk TSP, karena independen untuk Bellman dan Held-Karp . Algoritma secara universal dilaporkan berjalan dalam waktu $O(2^n n^2)$ . Namun, seperti yang ditunjukkan oleh salah satu siswa saya baru-baru ini, waktu berjalan ini mungkin memerlukan model perhitungan yang sangat kuat.

Berikut adalah uraian singkat algoritmanya. Input terdiri dari grafik berarah dengan simpul dan fungsi panjang non-negatif . Untuk setiap simpul dan , dan setiap subset dari simpul yang tidak termasuk dan , misalkan menunjukkan panjang jalur Hamiltonian terpendek dari ke dalam subgraf diinduksi . Algoritma Bellman-Held-Karp didasarkan pada pengulangan berikut (atau sebagai ekonom dan ahli teori kontrol suka menyebutnya, "persamaan Bellman"):s t X s t L ( s , X , t ) s t G [ X ∪ { s , t } $G=(V,E)$ℓ : E → R$n$$\ell\colon E\to\mathbb{R}^+$$s$$t$$X$$s$$t$$L(s,X,t)$$s$$t$$G[X\cup\{s,t\}]$

Untuk setiap vertex , panjang optimal bepergian tur salesman adalah L (s, V \ setminus \ {s \}, s) . Karena parameter pertama s adalah konstan dalam semua panggilan rekursif, ada \ Theta (2 ^ nn) subproblem yang berbeda, dan setiap subproblem paling banyak bergantung pada n lainnya. Dengan demikian, algoritma pemrograman dinamis berjalan dalam waktu O (2 ^ nn ^ 2) .$s$$L(s,V\setminus\{s\}, s)$$s$$\Theta(2^n n)$$n$$O(2^n n^2)$

Atau apakah itu ?!

Model RAM integer standar memungkinkan manipulasi bilangan bulat konstan dengan bit $O(\log n)$ , tetapi setidaknya untuk operasi aritmatika dan logis , bilangan bulat yang lebih besar harus dipecah menjadi potongan-potongan berukuran kata. (Kalau tidak, hal - hal aneh dapat terjadi.) Apakah ini tidak benar untuk mengakses alamat memori yang lebih lama? Jika suatu algoritma menggunakan ruang superpolynomial, apakah masuk akal untuk mengasumsikan bahwa akses memori hanya membutuhkan waktu yang konstan?

Untuk algoritma Bellman-Held-Karp khususnya, algoritma harus mengubah deskripsi subset $X$ menjadi deskripsi subset $X\setminus\{v\}$ , untuk setiap $v$ , untuk mengakses tabel memoisasi. Jika himpunan bagian diwakili oleh bilangan bulat, bilangan bulat ini membutuhkan $n$ bit dan karenanya tidak dapat dimanipulasi dalam waktu yang konstan; jika mereka tidak diwakili oleh bilangan bulat, representasi mereka tidak dapat digunakan secara langsung sebagai indeks ke dalam tabel memoisasi.

Jadi: Apa waktu berjalan asimptotik aktual dari algoritma Bellman-Held-Karp?

Ini kurang dari jawaban matematis daripada jawaban filosofis, tapi saya lebih suka memikirkan model RAM yang memungkinkan manipulasi bilangan bulat waktu-konstan dengan sejumlah B bit yang tidak diketahui tetapi setidaknya sebesar , di mana S adalah jumlah ruang yang dibutuhkan algoritma. Karena, jika bilangan bulat tidak sebesar itu, bagaimana Anda bisa mengatasi memori Anda? Untuk algoritma waktu dan ruang polinomial sama dengan bit O (log n), tetapi untuk algoritma ruang eksponensial, ia menghindari masalah.$\log_2 S$

Tentu saja, jika S melebihi jumlah memori yang Anda miliki, algoritma Anda tidak akan berjalan sama sekali. Atau, itu akan berjalan dengan mem-paging informasi ke dalam dan keluar dari memori dan Anda harus menggunakan model hierarki memori daripada model RAM.

Ada diskusi tentang masalah ini dalam buku terbaru oleh Fedor V. Fomin dan Dieter Kratsch " Algoritma Eksponensial Eksak" di mana mereka menentukan waktu berjalan dalam model RAM unit-cost dan model RAM log-cost ( - jarak maksimum antara kota dan f ( n ) = O ∗ ( g ( n ) ) jika f ( n ) = O ( g ( n ) p o l y ( n ) ) ):$W$$f(n)=\mathcal{O}^{\ast}(g(n))$$f(n)=\mathcal{O}(g(n)poly(n))$

dan 2 n log W n O ( 1 ) (catatan, 2 n log W n O ( 1 ) ∉ O ∗ ( 2 n ) ), masing-masing.$\mathcal{O}^{\ast}(2^n)$$2^n\log Wn^{\mathcal{O}(1)}$$2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$