สมมติว่าเรามีกราฟแบบไม่มีทิศทาง (undirected graph) ที่มีน้ำหนัก (weighted) จำนวน n โหนด (โหนดหมายเลขตั้งแต่ 0 ขึ้นไป) กราฟนี้รับเข้ามาในรูปแบบรายการขอบ (edge list) โดยแต่ละขอบ e มีความน่าจะเป็นสำเร็จในการเดินทางผ่านขอบนั้นคือ probability[e] เรายังมีโหนดเริ่มต้น (start) และโหนดสิ้นสุด (end) เราต้องหาเส้นทางที่มีความน่าจะเป็นสำเร็จสูงสุดในการเดินทางจาก start ไป end และคืนค่าความน่าจะเป็นสำเร็จนั้น ถ้าไม่พบเส้นทางใดเลย ให้คืนค่า 0
เช่น ถ้าข้อมูลเข้าเป็นแบบนี้
ผลลัพธ์จะเป็น 0.24 เพราะมีเส้นทาง 2 เส้นทางจากโหนด 0 ไป 2 เส้นทางหนึ่งมีความน่าจะเป็น 0.2 อีกเส้นทางผ่านโหนด 1 มีความน่าจะเป็น 0.4 × 0.6 = 0.24 ซึ่งเป็นค่าสูงสุด
ขั้นตอนการแก้ปัญหา
- สร้างกราฟ g จาก edge list ที่กำหนด ใช้ค่าความน่าจะเป็นเป็นน้ำหนัก
- สร้างคิว q สำหรับเก็บโหนดและความน่าจะเป็นสะสม
- ใส่ (start, 1) เข้าไปในคิว q
- สร้าง map visited เพื่อบันทึกความน่าจะเป็นสูงสุดที่พบจนถึงแต่ละโหนด
- วนลูป بينماคิว q ไม่ว่าง:
- นำ (node, prob) ตัวแรกออกจากคิว
- ถ้า visited[node] > prob ให้ข้ามรอบนี้ (พบเส้นทางดีกว่าแล้ว)
- มิฉะนั้น อัปเดต visited[node] = prob
- วนลูปผ่านโหนดติดกัน adj และความน่าจะเป็น nextProb ใน g[node]:
- ถ้า visited[adj] < prob × nextProb ให้ใส่ (adj, prob × nextProb) เข้าไปในคิว
- คืนค่า visited[end]
ตัวอย่างโค้ด
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
