Berapa panjang yang diharapkan dari jalur hamiltonian terpendek pada titik yang dipilih secara acak dari grid planar?

$k$ titik yang berbeda dipilih secara acak dari kisi . (Jelas dan merupakan bilangan konstan yang diberikan.) Sebuah grafik berbobot lengkap dibangun dari titik-titik ini sedemikian sehingga bobot tepi antara simpul dan simpul sama dengan jarak Manhattan dari dua simpul pada kisi asli. . $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Saya mencari cara yang efisien untuk menghitung panjang yang diharapkan dari jalur hamiltonian terpendek (berat total minimum) yang melewati node ini . Lebih tepatnya, pendekatan naif berikut tidak diinginkan: $k$

$\bullet$ Menghitung panjang jalur yang tepat untuk semua kombinasi k node dan mendapatkan panjang yang diharapkan.

$\bullet$ Menghitung panjang lintasan yang diperkirakan untuk semua kombinasi k k menggunakan heuristik dasar menggunakan pohon rentang minimum yang menghasilkan kesalahan hingga 50%. (Heuristik yang lebih baik dengan lebih sedikit kesalahan mungkin membantu)

graph-theory co.combinatorics planar-graphs hamiltonian-paths Javad
sumber

Saat ini, tidak ada harapan untuk algoritma yang efisien karena masalah jalur Hamiltonian tertimbang pada grid planar adalah NP-lengkap.

Mohammad Al-Turkistany

Ketika Anda berbicara tentang jalur hamiltonian, apakah Anda bertualang tentang jalur hamiltonian dengan bobot terkecil (alias masalah penjual keliling)?

a3nm

@ MohammadAl-Turkistany, kekerasan HAM PATH belum tentu menjadi hambatan, karena OP hanyalah perkiraan untuk poin acak.

Suresh Venkat

@ a3nm ya, dan saya memperbaikinya.

Suresh Venkat

Apa yang salah dengan menghitung panjang tur yang tepat untuk banyak sampel acak poin , dan menemukan ekspektasi dan standar deviasi? Seberapa besar Anda perlu untuk menjadi?

k

$k$

k, p, q

$k, p, q$

Peter Shor

Dengan asumsi bahwa dan cukup besar, orang akan berharap bahwa panjang yang diharapkan terutama akan tergantung pada kepadatan, dengan beberapa istilah koreksi tergantung pada perimeter. Jadi, untuk urutan pertama, akan menjadi fungsi dari bentuk berikut. $p$ $q$

L \approx (p q k)^{1 / 2} f (k / p q) + (p + q) g (k / p q) .

$L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$

Sekarang, Anda bisa menggunakan eksperimen pada masalah ukuran kecil untuk mencari tahu apa itu dan . Pertama, untuk memperkirakan , Anda ingin melakukan percobaan pada sampel tanpa batas: cara termudah untuk melakukan ini adalah dengan menggunakan grid dengan sisi kiri terhubung ke kanan dan atas ke bawah, membentuk torus. Untuk memperkirakan , Anda dapat menggunakan percobaan di grid. $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Untuk estimasi, Anda perlu menyelesaikan (tepatnya atau kurang-lebih) TSP yang relatif besar, karena semakin besar yang Anda gunakan untuk estimasi, semakin baik hasil Anda. Anda bisa menggunakan heuristik yang datang dalam beberapa persen, atau kode TSP yang tepat. Lihat di sini untuk beberapa heuristik yang baik. Pemecah Concorde TSP milik Bill Cook akan menemukan optimum yang tepat untuk mesin virtual yang cukup besar (ini adalah kode TSP terbaik yang tersedia), dan dapat digunakan tanpa biaya untuk penelitian akademis.

Peter Shor
sumber

Menggunakan terminologi dari TSPLIB , saya mencari SOP bukan TSP. Mengalikan dihitung untuk TSP dengan memberikan batas atas untuk SOP. Sayangnya, pemecah Concorde TSP tidak menangani SOP dan saya tidak dapat menemukan pemecah SOP daring.

E [L]

$E[L]$

(k - 1) / k

$(k-1)/k$

Javad

Saya kira untuk menghitung , kasus-kasus yang memiliki lebih besar dan lebih kecil terdistribusi secara merata di sekitar , jadi orang dapat datang dengan pendekatan konstruktif untuk menemukan pengaturan titik di grid yang (mungkin kira-kira) memberi . Menemukan pengaturan seperti itu jelas akan secara dramatis mengurangi biaya perhitungan.

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

Javad

Saya juga tidak begitu mengerti alasan untuk koefisien . Mengapa tidak ? Bagaimana formulasi pendekatan ini berubah untuk nilai dan ?

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

Javad

@Javad: Pertanyaan bagus. Saya salah, karena saya entah bagaimana memikirkan hal ketika saya menulis jawaban saya. Koefisien berasal dari asumsi saya bahwa grid memiliki satuan panjang tepi, sehingga seluruh wilayah adalah ukuran . Tepi rata-rata harus panjang , dan ada tepi , jadi jika Anda ingin tetap konstan, istilah pertama harus .

k^{2}

$k^2$

p \times q

$p\times q$

p \times q

$p \times q$

θ (\sqrt{p q / k})

$\theta(\sqrt{pq/k})$

k

$k$

f

$f$

\sqrt{p q k} f (k / p q)

$\sqrt{pqk} f(k/pq)$

Peter Shor

Untuk , perbedaan antara panjang TSP dan panjang SOP harus hampir diabaikan.

k \approx 10^{6}

$k \approx 10^6$

Peter Shor

Berapa panjang yang diharapkan dari jalur hamiltonian terpendek pada titik yang dipilih secara acak dari grid planar?

Jawaban: