Teka-teki dari 60 tahun yang lalu! Penyelidik dari Universiti Copenhagen menyelesaikan masalah "jalan terpendek sumber tunggal".

"Dalam graf berwajaran G=(V,E), berat setiap tepi ialah nombor nyata. Selain itu, bucu dalam V juga diberikan, dipanggil sumber.

Kira panjang laluan terpendek dari punca ke semua bucu lain Ini ialah masalah laluan terpendek sumber tunggal (SSSP). >

Selama lebih setengah abad, penyelidik di seluruh dunia telah berusaha untuk menyelesaikan masalah ini. Kini, teka-teki algoritma ini akhirnya berjaya diselesaikan oleh pasukan penyelidik dari Jabatan Sains Komputer di Universiti Copenhagen.

Algoritma SSSP berat negatif: pantas dan cekap

Pautan kertas: https:/ /arxiv. org/abs/2203.03456

Dalam temu bual, penyelidik Christian Wulff-Nilsen berkata bahawa penyelesaian mereka adalah kejayaan pertama yang telah wujud selama lebih daripada 30 tahun

Õ(n(4/3) log W) kekangan masa operasi ialah algoritma gabungan SSSP dengan pemberat negatif.

Terdapat dua algoritma klasik tentang SSSP: algoritma Dijkstra (algoritma Dijkstra) dan algoritma Bellman-Ford (algoritma Bellman-Ford), kedua-duanya Semua mempunyai had mereka sendiri .

Algoritma Dijkstra mempunyai masa operasi terpendek dan boleh mencapai masa hampir linear

O(m + n log n), tetapi tepi berat negatif tidak boleh dikira.

Algoritma Bellman-Ford boleh mengira tepi berat negatif, tetapi masa operasi terlalu lama, mencecah

O(mn). Pada masa ini, algoritma SSSP tercanggih untuk menyelesaikan tepi berwajaran negatif bergantung pada pengoptimuman berterusan yang kompleks dan algoritma algebra dan grafik dinamik. Ini membawa kepada fakta bahawa walaupun generasi sarjana terkemudian terus mengoptimumkan algoritma, masa pengiraannya masih memerlukan Õ(n(4/3) log W). Kekangan masa pengiraan ini telah wujud selama tiga puluh tahun.

Menghadapi batasan ini, Wulff-Nilsen menimbulkan dua soalan:

1) Bolehkah operasi algoritma kelebihan berwajaran negatif mencapai masa hampir linear?

2) Bolehkah ini dicapai dengan alatan mudah?

Adakah terdapat kaedah yang memerlukan masa dan kualiti?

Jangan beritahu saya, ia benar-benar wujud.

Algoritma yang dicadangkan oleh Wulff-Nilsen ialah algoritma penskalaan imej, yang dipertingkatkan oleh algoritma penguraian imej ringkas Penguraian Diameter Rendah. Biasanya, algoritma penguraian ini hanya digunakan untuk penguraian graf bagi tepi bukan berwajaran negatif, dan salah satu sumbangan penyelidikan ini adalah untuk mengaplikasikannya pada imej tepi berwajaran negatif untuk mengukuhkan algoritma penskalaan rekursif SSSP tepi berwajaran negatif.

Proses derivasi

Wulff-Nilsen adalah berdasarkan algoritma harga Johnson. Cadangkan: Dalam imej

G = (V, E, w), biarkan Φ menjadi sebarang fungsi: V→ Z. Biarkan w(Φ) menjadi fungsi berat:

takrif: , : . Dalam imejG = (V, E,w) dan imej G' = (V, E,w'), jika: 1) Jarak terpendek dalam imej G ialah The jarak terpendek dalam imej G' adalah sama dan begitu juga sebaliknya; ' Apabila mengandungi cincin berat negatif, imej G adalah sama dengan imej G'. Corollary 2.7 Pertimbangkan sebarang imej

dan fungsi harga Φ. Dalam u, v ∈ V, . Dan dalam mana-mana cincin

C

, . Oleh itu,

G dan adalah sama. Jika , , maka G dan G' adalah sama. Tujuan algoritma ini adalah untuk mengira fungsi harga

Φ

apabila GΦ adalah bukan negatif, dengan mengandaikan tiada kitaran berat negatif. Kemudian anda boleh menjalankan algoritma Dijkstra pada . Selepas itu, Wulff-Nilsen mula memperkenalkan rangka kerja algoritmanya.

Pertama, Wulff-Nilsen mengandaikan bahawa terdapat algoritma Dijkstra (G, s), memasukkan graf tanpa tepi berat negatif G

, bucu

s ∈ V, s dalam G mengeluarkan pepohon laluan terpendek. Masa berjalan ialah O(m + n log n).

Jika G ialah DAG (graf asiklik berarah), hitung fungsi harga Φ supaya Mempunyai bukan -berat tepi negatif adalah mudah: hanya gelung pada v1, ..., vn topologi dan tetapkan Φ(vi) supaya semua pemberat tepi masuk adalah bukan negatif.

Matlamat masalah laluan terpendek sumber tunggal adalah untuk mencari laluan terpendek dari nod permulaan yang diberikan kepada semua nod lain dalam rangkaian.

Rangkaian diwakili sebagai graf yang terdiri daripada nod dan sambungan antara mereka, dipanggil tepi.

Setiap tepi mempunyai arah (contohnya, ini boleh digunakan untuk mewakili jalan sehala) dan berat yang mewakili kos perjalanan sepanjang itu tepi. Jika semua pemberat tepi adalah bukan negatif, masalah itu boleh diselesaikan dalam masa yang hampir linear menggunakan algoritma Dijkstra klasik.

Keputusan baharu menyelesaikan masalah ini dalam masa yang hampir sama dengan algoritma Dijkstra, tetapi juga membenarkan pemberat kelebihan negatif.

Selepas itu, Wulff-Nilsen menyebut dua algoritma paling penting dalam alatan gabungan: ScaleDown dan SPmain .

Algoritma ScaleDown berjalan secara berperingkat, dan pada peringkat terakhir ia menggunakan ElimNeg () untuk mengira fungsi hargaΦ2. Jika ElimNeg ditamatkan, ia akan mengembalikan fungsi harga ψ′, biarkan semua nilai tepi ​​tidak Negatif; dengan kata lain, kerana , , oleh itu tidak mengandungi pemberat negatif.

Ini bermakna untuk semua , memenuhi syarat (kerana ). Ini membuktikan ketepatan output ScaleDown.

Jika algoritma ditamatkan, maka untuk semua dan , adalah integral dan untuk semua ,.

Ini bermakna untuk semua , . Oleh itu graf G* mempunyai pemberat bukan negatif.

Dengan aruhan, dengan mengandaikan bahawa teori itu berlaku untuk , untuk ScaleDown dalam baris 5 daripada algoritma Panggilan ke memenuhi atribut input yang diperlukan.

Oleh itu, melalui Output dan ScaleDown, anda boleh mendapatkan .

Sejak , jika biar C menjadi untuk sebarang kitaran berat negatif dalam , kerana semua nilai dalam ialah gandaan 2n, dan ; Kami juga tahu bahawa , , jadi

tidak konsisten dengan Corollary 2.7.

Oleh itu kita boleh membuat kesimpulan bahawa jika

mengandungi kitaran berat negatif, algoritma tidak akan ditamatkan .

Ini boleh membuktikan ketepatan algoritma SPmain.

Pada ketika ini, dua algoritma paling penting dalam penyelesaian SSSP berat negatif Wulff-Nilsen telah terbukti benar. Algoritma baharu berjaya memperkenalkan pemberat negatif sambil memastikan masa hampir linear.

​

60 tahun kemudian, pencarian jawapan bukan sekadar teka-teki

Tahun lepas, Wulff -Nilsen membuat satu lagi kejayaan dalam bidang yang sama, melibatkan cara mencari laluan terpendek dalam rangkaian yang berbeza masa. Penyelesaiannya kepada teka-teki baru-baru ini berdasarkan kerja ini.

Beliau percaya bahawa menyelesaikan masalah SSSP boleh membuka jalan kepada algoritma yang bukan sahaja dapat membantu kenderaan elektrik mengira dengan serta-merta laluan terpantas ke destinasi mereka, tetapi juga memastikan bahawa Cara paling cekap tenaga untuk melakukan ini.

Wulff-Nilsen menjelaskan: “Algoritma kami menambah pemberat negatif, satu dimensi yang tidak dimiliki oleh algoritma sebelumnya adalah apabila memandu di pergunungan. dengan dimensi berat negatif, sistem navigasi boleh mengesyorkan laluan dengan banyak jalan menurun untuk pemilik kenderaan elektrik, supaya kenderaan elektrik boleh dicas semasa menuruni bukit >Wulff-Nilsen juga berkata bahawa algoritma mereka bukan sahaja boleh digunakan untuk kenderaan elektrik perancangan laluan, tetapi juga untuk memantau spekulasi dalam industri kewangan. Beliau berkata: "Secara prinsipnya, algoritma ini boleh digunakan untuk memberi amaran awal kepada pengguna seperti bank pusat, memberi amaran kepada spekulator yang membuat spekulasi dalam pembelian dan penjualan pelbagai mata wang. Kini, ramai penjenayah menggunakan komputer untuk melakukan jenayah, tetapi kerana algoritma kami adalah begitu pantas, mungkin Ia digunakan untuk memantau dan mengesan kelemahan sebelum ia dieksploitasi Pada tahun 1959, apabila Dijkstra mula-mula mencadangkan masalah jarak terpendek, dia mungkin tidak memikirkannya selama lebih daripada 60 tahun telah sentiasa mengoptimumkan penyelesaian kepada masalah ini. Anda juga mungkin terkejut bahawa jawapan kepada teka-teki itu mempunyai konotasi yang begitu kaya.

Mungkin, inilah daya tarikan sains.

Atas ialah kandungan terperinci Teka-teki dari 60 tahun yang lalu! Penyelidik dari Universiti Copenhagen menyelesaikan masalah "jalan terpendek sumber tunggal".. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!