n개의 노드(노드에는 0부터 번호가 지정됨)가 있는 무방향 가중치 그래프가 있다고 가정합니다. 이 그래프는 에지 목록을 사용하여 입력으로 제공되며, 각 에지 e에 대해 해당 에지 확률[e]을 통과할 확률이 있습니다. 우리는 또한 시작과 끝 노드를 가지고 있습니다. 우리는 시작에서 끝으로 가는 최대 성공 확률을 가진 경로를 찾고 성공 확률을 반환해야 합니다. 경로를 찾을 수 없으면 0을 반환합니다.
따라서 입력이 다음과 같으면
노드 0에서 2까지의 두 경로가 있기 때문에 출력은 0.24가 됩니다. 하나는 확률 0.2이고 다른 하나는 노드 1을 통한 확률이 0.4*0.6 =0.24이며 이것이 최대값입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
g :=주어진 에지 목록에서 그래프를 만들고 확률 값을 가중치로 사용
-
q :=큐 데이터 구조
-
q에 삽입(시작, 1)
-
Visited :=방문한 노드를 담을 맵
-
q가 비어 있지 않은 동안 수행
-
(node, prob) :=q의 첫 번째 항목 및 q에서 삭제
-
방문한 경우[노드]> prob, 다음
-
다음 반복으로 이동
-
-
그렇지 않으면
-
방문[노드] :=확률
-
-
g[node]의 각 인접 노드 adj 및 확률 nextProb에 대해 수행
-
방문한 경우[adj]
-
q
끝에 (adj, prob * nextProb) 삽입
-
-
-
-
재방문[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