สมมติว่าเรามีกราฟการถ่วงน้ำหนักแบบไม่ระบุทิศทางที่มี n โหนด (โหนดจะมีหมายเลขตั้งแต่ 0 เป็นต้นไป) กราฟนี้กำหนดให้เป็นอินพุตโดยใช้รายการขอบ สำหรับแต่ละขอบ e มีความน่าจะเป็นที่จะประสบความสำเร็จในการสำรวจความน่าจะเป็นของขอบนั้น[e] เรายังมีโหนดเริ่มต้นและสิ้นสุด เราต้องหาเส้นทางที่มีความน่าจะเป็นสูงสุดของความสำเร็จตั้งแต่ต้นจนจบและส่งกลับความน่าจะเป็นที่ประสบความสำเร็จ หากเราไม่พบเส้นทางใด ๆ ให้คืนค่า 0
ดังนั้นหากอินพุตเป็นแบบ
ผลลัพธ์จะเป็น 0.24 เนื่องจากมีสองเส้นทางจากโหนด 0 ถึง 2 หนึ่งเส้นทางที่มีความน่าจะเป็น 0.2 อีกเส้นทางผ่านโหนด 1 มีความน่าจะเป็น 0.4*0.6 =0.24 ซึ่งเป็นค่าสูงสุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
g :=สร้างกราฟจากรายการขอบที่กำหนดและใช้ค่าความน่าจะเป็นเป็นน้ำหนัก
-
q :=โครงสร้างข้อมูลคิว
-
แทรก (เริ่ม 1) ลงใน q
-
เยี่ยมชม :=แผนที่สำหรับเก็บโหนดที่เยี่ยมชม
-
ในขณะที่ q ไม่ว่างให้ทำ
-
(node, prob) :=รายการแรกของ q และลบออกจาก q
-
ถ้าเข้า[node]> prob แล้ว
-
ไปทำซ้ำต่อไป
-
-
มิฉะนั้น
-
เยี่ยมชม[โหนด] :=ปัญหา
-
-
สำหรับแต่ละโหนดที่อยู่ติดกัน adj และความน่าจะเป็น nextProb ใน g[node] ทำ
-
ถ้าเคยไป[adj]
-
แทรก (adj, prob * nextProb) ต่อท้าย q
-
-
-
-
กลับมาเยือน[จบ]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
from collections import defaultdict, deque def solve(edges, probability, start, end): g = defaultdict(list) for i in range(len(edges)): src, dst = edges[i][0], edges[i][1] prob = probability[i] g[src].append((dst, prob)) g[dst].append((src, prob)) q = deque() q.append((start, 1)) visited = defaultdict(int) while q: node, prob = q.popleft() if visited[node] > prob: continue else: visited[node] = prob for adj, nextProb in g[node]: if visited[adj] < prob * nextProb: q.append((adj, prob * nextProb)) return visited[end] edges = [[0,1],[1,2],[0,2]] probability = [0.5,0.5,0.2] start = 0 end = 2 print(solve(edges, probability, start, end))
อินพุต
[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2
ผลลัพธ์
0.25
