"Kerabat" dari masalah jalur terpendek

10

Pertimbangkan grafik tidak langsung yang terhubung dengan bobot tepi non-negatif, dan dua simpul dibedakan . Di bawah ini adalah beberapa masalah lintasan yang semuanya dari bentuk berikut: temukan lintasan , sedemikian sehingga beberapa fungsi bobot tepi pada lintasan adalah minimum. Dalam hal ini mereka semua adalah "saudara" dari masalah jalan terpendek; dalam yang terakhir fungsi hanyalah jumlah.s,tst

Catatan: Kami mencari jalur sederhana, yaitu tanpa simpul berulang. Karena saya tidak menemukan nama standar untuk masalah ini dalam literatur, saya menamainya sendiri.

Jalan dengan kesenjangan berat minimum: menemukan jalan, sehingga perbedaan antara terbesar dan terkecil bobot tepi di jalan adalah minimum.st

Jalur halus: temukan jalur , sehingga ukuran langkah terbesar pada jalur adalah minimum, di mana ukuran langkah adalah nilai absolut dari perbedaan berat antara dua sisi yang berurutan .st

Jalur dengan ketinggian minimum: Mari kita mendefinisikan ketinggian jalur dengan jumlah ukuran langkah di sepanjang jalur (lihat definisi ukuran langkah di atas). Temukan jalur dengan ketinggian minimum.st

Jalur dengan bobot prima minimum: dengan asumsi bahwa semua bobot tepi adalah bilangan bulat positif, temukan jalur , sehingga bobotnya adalah bilangan prima. Jika ada jalur seperti itu, temukan jalur dengan bobot prima sekecil mungkin.st

Pertanyaan: apa yang diketahui tentang masalah jalur ini? (Dan yang lain yang dapat disusun dalam semangat yang sama, menerapkan fungsi bobot yang berbeda.) Secara umum, adakah panduan yang fungsi bobot tepi dapat diminimalkan dalam waktu polinomial, dan mana yang sulit NP?

Catatan: menarik, misalnya, bahwa sementara jumlah bobot mudah untuk diminimalkan (itu adalah masalah jalur terpendek klasik), tetapi meminimalkan rata - rata bobot yang terkait erat pada jalur adalah NP-hard. (Tetapkan bobot 2 untuk semua insiden tepi ke dan , dan bobot 1 untuk yang lainnya. Lalu jalur bobot rata-rata min akan menjadi jalur terpanjang ).stst

Andras Farago
sumber

Jawaban:

8

Inilah jawaban untuk masalah pertama:

Jalan dengan kesenjangan berat minimum: menemukan jalan, sehingga perbedaan antara terbesar dan terkecil bobot tepi di jalan adalah minimum.st

Sebuah makalah dari tahun 1984 menunjukkan bahwa setiap kali kita dapat memutuskan kelayakan (apakah ada solusi dalam kasus tidak tertimbang) untuk beberapa masalah optimasi kombinatorial dalam waktu polinomial, maka kita juga dapat menemukan dalam waktu polinomial solusi yang meminimalkan perbedaan antara yang terbesar dan terkecil koefisien biaya (dalam kasus tertimbang):

S. Martello, WR Pulleyblank, P. Toth, D. de Werra
Masalah optimisasi yang seimbang
Riset Operasi Surat 3, 1984, Halaman 275-278

Ini menyiratkan algoritma waktu polinomial untuk pertanyaan Anda.

Gamow
sumber
1
Ini juga dapat dilakukan dengan pencarian brute force pada semua pasang sisi yang dapat membentuk max dan min, dan urutan / orientasinya.
Yonatan N
3

Jalur dengan celah berat minimum : Ini dapat diselesaikan dalam waktu , di manaadalah jumlah tepi (dengan asumsi paling tidak linear dalam jumlah simpul). Anda dapat mengulangi bobot minimum, dan melakukan pencarian biner (atau pembaruan efisien) melebihi bobot maksimum, dan memeriksa konektivitas. Saya tidak tahu apakah ini bisa diperbaiki.O~(|E|2)|E||E|

Path dengan ketinggian minimum (dalam terminologi Anda): Ini dapat diselesaikan dalam waktu . Anda dapat menghitung jarak (seperti jumlah ukuran 'langkah') ke semua tepi secara analog dengan jalur terpendek biasa tertimbang. Perhatikan bahwa simpul yang berulang tidak dapat mempersingkat jalur. Untuk menangani simpul derajat tinggi secara efisien (seperti dalam menghindari waktu ), Anda dapat membagi simpul derajat menjadi jalur simpul .O~(|E|)|E|2kk1

Jalur dengan berat prima minimum: Jika bobot dalam biner, ini harus NP lengkap: Gunakan tepi berat 1, kecuali untuk tepi bobot awal tinggi sehingga hanya jalur Hamilton yang memiliki bobot prima (bobot adalah jumlah bobot tepi) . (Sebuah peringatan adalah bahwa kita belum membuktikan bahwa bilangan prima yang cukup besar (bahkan tanpa kesenjangan prima minimum) dapat dengan cepat ditemukan tanpa keacakan.) Bahkan untuk bobot yang tidak waspada, saya tidak berharap itu berada dalam P.
Bobot prima minimum yang memungkinkan self- persimpangan: Di P untuk bobot unary. Jika, sebagai pengganti himpunan bilangan prima, kami menggunakan himpunan bilangan acak dengan kerapatan , maka dengan probabilitas 1, ia berada diSΘ(n/logn)PSbahkan untuk bobot biner: Cukup untuk melacak banyak bobot jalur terendah (bergantung pada ) secara polinomial di setiap titik. Namun, dengan bobot utama, kita mungkin harus mendiversifikasi pembagi perbedaan berat (bukan hanya melacak bobot terendah), dan tidak jelas apakah itu cukup.S

Jalur paling halus: NP selesai. Jika kita mengizinkan persimpangan-sendiri, ini akan dipecahkan dalam waktu , tetapi untuk versi tanpa persimpangan-sendiri, berikut adalah pengurangan dari 3-SAT dengan variabel. Memiliki simpul , ditambah simpul untuk setiap klausa. Untuk setiap variabel ( ), tambahkan lintasan halus (menggunakan simpul tambahan jika perlu) dari ke yang melewati semua klausa dengan kemunculan positif , dan lintasan yang sama untuk klausa denganO~(|E|)ns=v0,v1,...,t=vnxii<nvivi+1xi¬xi. Tetapkan bobot tepi pertama dan terakhir dari setiap jalur ke 1 (atau konstanta lain), tetapi jika tidak pilih bobot sedemikian rupa sehingga tidak ada jalur lain yang mulus. Akhirnya, duplikat semua simpul klausa dan tepi yang berdampingan; dengan cara ini setiap klausa dapat dikunjungi paling banyak dua kali, yang cukup untuk 3-SAT.

Dmytro Taranovsky
sumber
Saya pikir, jalan paling halus adalah di P, karena transformasi berikut. Biarkan menjadi simpul derajat . Ganti dengan klik ukuran , sedemikian sehingga setiap tepi yang semula berbatasan dengan sekarang berakhir pada simpul yang berbeda dari klik itu. Jika adalah dua tepi asli tersebut, maka tetapkan bobotke tepi di klik. Lakukan transformasi ini untuk setiap simpul , dan tetapkan 0 bobot ke tepi grafik asli. Maka berat minimumvdvdevvee,f|w(e)w(f)|(ve,vf)vs,tstjalur dalam grafik baru memberikan jalur paling halus dalam aslinya, setelah membatalkan transformasi.
Andras Farago
@AndrasFarago Masalah dengan argumen Anda adalah bahwa beberapa jalur sederhana dalam grafik yang diperluas telah berulang simpul dalam grafik asli. Saya suka bahwa masalah jalur paling halus terlihat sederhana.
Dmytro Taranovsky
@ Dmytro Taranovsky Sepertinya, Anda benar, mungkin memang terjadi bahwa setelah kembali ke grafik asli kita bisa mendapatkan simpul berulang di jalan (tetapi tidak ada tepi yang berulang). Namun, jika setiap derajat di grafik asli paling banyak 3, maka tidak ada pengulangan yang bisa terjadi. Ini berarti, masalah Smoothest Path ada di P setidaknya untuk grafik dengan derajat maksimum . 3
Andras Farago
Maaf, dalam grafik yang ditransformasikan, kita perlu menemukan jalur dengan bobot maksimum terkecil (yang juga ada di P), daripada bobot total terkecil. Berat total akan mengarah ke Path dengan Ketinggian Minimum (dalam grafik dengan derajat maks , sehingga simpul yang berulang tidak termasuk). 3
Andras Farago