Giả sử chúng ta có một đồ thị vô hướng có trọng số với n nút (được đánh số từ 0), đồ thị này được cung cấp dưới dạng danh sách cạnh, mỗi cạnh e có xác suất thành công khi đi qua cạnh đó là probability[e]. Chúng ta cũng có nút bắt đầu và nút kết thúc, nhiệm vụ là tìm đường đi có xác suất thành công lớn nhất từ start đến end và trả về xác suất đó. Nếu không tìm thấy đường đi nào, trả về 0.
Ví dụ, với đầu vào như hình minh họa:
Kết quả sẽ là 0.24 vì có hai đường đi từ nút 0 đến 2: một đường trực tiếp với xác suất 0.2, đường còn lại qua nút 1 có xác suất 0.4 × 0.6 = 0.24, đây là giá trị lớn nhất.
Thuật toán giải quyết
Chúng ta thực hiện theo các bước sau:
- Xây dựng đồ thị g từ danh sách cạnh, sử dụng xác suất làm trọng số.
- Khởi tạo hàng đợi q.
- Đưa cặp (start, 1) vào q (xác suất ban đầu là 1).
- Sử dụng bản đồ visited để lưu xác suất lớn nhất đã biết đến mỗi nút.
- Lặp lại cho đến khi q rỗng:
- Lấy cặp (node, prob) đầu tiên khỏi q.
- Nếu visited[node] > prob, bỏ qua vòng lặp này.
- Ngược lại, cập nhật visited[node] = prob.
- Duyệt qua các nút liền kề adj và xác suất nextProb trong g[node]:
- Nếu visited[adj] < prob × nextProb, đưa (adj, prob × nextProb) vào cuối q.
- Trả về visited[end].
Ví dụ triển khai
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))Đầu vào
[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2
Đầu ra
0.25