Laluan dengan Kebarangkalian Maksimum

1514. Laluan dengan Kebarangkalian Maksimum

Kesukaran:Sederhana

Topik:Tatasusunan, Graf, Timbunan (Baris Gilir Keutamaan), Laluan Terpendek

Anda diberi graf berwajaran tidak terarah bagi n nod (0-diindeks), diwakili oleh senarai tepi di mana tepi[i] = [a, b] ialah tepi tidak berarah yang menghubungkan nod a dan b dengan kebarangkalian kejayaan merentasi tepi itu succProb[i].

Memandangkan dua nod bermula dan tamat, cari jalan dengan kebarangkalian maksimum kejayaan untuk pergi dari awal ke akhir dan kembalikebarangkalian kejayaannya.

Jika tiada jalan dari mula hingga akhir,kembali 0. Jawapan anda akan diterima jika ia berbeza daripada jawapan yang betul paling banyak1e-5.

Contoh 1:

• Input:n = 3, tepi = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], mula = 0, tamat = 2
• Output:0.25000
• Penjelasan:Terdapat dua laluan dari mula hingga akhir, satu mempunyai kebarangkalian berjaya = 0.2 dan satu lagi mempunyai 0.5 * 0.5 = 0.25.

Contoh 2:

• Input:n = 3, tepi = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], mula = 0, tamat = 2
• Output:0.30000

Contoh 3:

• Input:n = 3, tepi = [[0,1]], succProb = [0.5], mula = 0, tamat = 2
• Output:0.00000
• Penjelasan:Tiada laluan antara 0 dan 2.

Kekangan:

• 2 <= n <= 10^4
• 0 <= mula, tamat < n
• mula != tamat
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == tepi.panjang <= 2*10^4
• 0 <= succProb[i] <= 1
• Terdapat paling banyak satu tepi antara setiap dua nod

Petunjuk:

1. Mendarab kebarangkalian akan mengakibatkan ralat ketepatan.
2. Ambil kebarangkalian log untuk menjumlahkan nombor dan bukannya mendarabnya.
3. Gunakan algoritma Dijkstra untuk mencari laluan minimum antara dua nod selepas menafikan semua kos.

Penyelesaian:

Kami boleh menggunakan versi algoritma Dijkstra yang diubah suai. Daripada mencari jalan terpendek, anda akan memaksimumkan kebarangkalian kejayaan.

Mari kita laksanakan penyelesaian ini dalam PHP:1514. Laluan dengan Kebarangkalian Maksimum

 
 Penjelasan: 
 
 
Perwakilan Graf: Graf diwakili sebagai senarai bersebelahan di mana setiap nod menghala ke jirannya bersama-sama dengan kebarangkalian kejayaan tepi yang menghubungkannya.
 
Max Probability Array: Tatasusunan maxProb digunakan untuk menyimpan kebarangkalian maksimum untuk mencapai setiap nod dari nod permulaan.
 
Baris Keutamaan: Timbunan maksimum (SplPriorityQueue) digunakan untuk meneroka laluan dengan kebarangkalian tertinggi dahulu. Ini penting untuk memastikan bahawa apabila kami sampai ke nod destinasi, kami telah menemui laluan dengan kebarangkalian maksimum.
 
 
Algoritma:
 
 
Inisialisasikan kebarangkalian nod permulaan sebagai 1 (kerana kebarangkalian untuk kekal pada permulaan ialah 1).
 
Gunakan baris gilir keutamaan untuk meneroka nod, mengemas kini kebarangkalian maksimum untuk mencapai setiap jiran.
 
Jika nod destinasi tercapai, kembalikan kebarangkalian.
 
Jika tiada laluan wujud, kembalikan 0.
 
 
 
 
 Output: 
 
Untuk contoh yang disediakan:
 
 
$n = 3; $edges = [[0,1],[1,2],[0,2]]; $succProb = [0.5,0.5,0.2]; $start_node = 0; $end_node = 2;
        

         Salin selepas log masuk
        
       

Keluaran akan menjadi 0.25.

Pendekatan ini memastikan penyelesaian yang cekap menggunakan algoritma Dijkstra sambil mengendalikan spesifik pengiraan kebarangkalian.

Hubungi Pautan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Laluan dengan Kebarangkalian Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!