최대 확률의 경로

1514. 최대 확률의 경로

난이도:보통

주제:배열, 그래프, 힙(우선순위 대기열), 최단 경로

n개 노드(0-인덱스)의 무방향 가중치 그래프가 제공됩니다. 이는 간선 목록으로 표시됩니다. 여기서 edge[i] = [a, b]는 통과 성공 확률로 노드 a와 b를 연결하는 무방향 간선입니다. 그 가장자리 succProb[i].

두 개의 노드 시작과 끝이 주어지면 처음부터 끝까지 이동하여성공 확률.

으로 돌아가는 최대 성공 확률이 있는 경로를 찾습니다.

처음부터 끝까지 경로가 없으면0을 반환합니다. 귀하의 답변은 정답과 최대1e-5

.

만큼 다를 경우 승인됩니다.예 1:

• 입력:
n = 3, 가장자리 = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], 시작 = 0, 끝 = 2
• 출력:
0.25000
• 설명:
처음부터 끝까지 두 가지 경로가 있습니다. 하나는 성공 확률 = 0.2이고 다른 하나는 0.5 * 0.5 = 0.25입니다.

예 2:

• 입력:
n = 3, 가장자리 = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], 시작 = 0, 끝 = 2
• 출력:
0.30000

예 3:

• 입력:
n = 3, 가장자리 = [[0,1]], succProb = [0.5], 시작 = 0, 끝 = 2
• 출력:
0.00000
• 설명:
0과 2 사이에는 경로가 없습니다.

제약조건:

2 0 <= 시작, 끝 < ㄴ
시작 != 끝
0 a !=b
0 <= succProb.length == edge.length <= 2*10^4
0 <= succProb[i] <= 1
두 노드 사이에는 최대 하나의 가장자리가 있습니다

힌트:

확률을 곱하면 정밀도 오류가 발생합니다.
숫자를 곱하는 대신 로그 확률을 사용하여 숫자를 합산하세요.
Dijkstra의 알고리즘을 사용하여 모든 비용을 무시한 후 두 노드 사이의 최소 경로를 찾습니다.

해결책:

Dijkstra 알고리즘의 수정된 버전을 사용할 수 있습니다. 최단 경로를 찾는 것이 아니라 성공 확률을 극대화하게 됩니다.

이 솔루션을 PHP로 구현해 보겠습니다:1514. 최대 확률의 경로

으아아아

설명:

1. 그래프 표현

   : 그래프는 각 노드가 이웃을 가리키는 인접 목록과 이를 연결하는 가장자리의 성공 확률로 표현됩니다.

2. 최대 확률 배열

   : 배열 maxProb는 시작 노드에서 각 노드에 도달할 최대 확률을 저장하는 데 사용됩니다.

3. Priority Queue

   : 최대 힙(SplPriorityQueue)은 확률이 가장 높은 경로를 먼저 탐색하는 데 사용됩니다. 이는 대상 노드에 도달했을 때 최대 확률로 경로를 찾았는지 확인하는 데 중요합니다.

4. 알고리즘

   :
   시작 노드의 확률을 1로 초기화합니다(시작에 머무를 확률은 1이므로).
   우선순위 대기열을 사용하여 노드를 탐색하고 각 이웃에 도달할 최대 확률을 업데이트합니다.
   목적지 노드에 도달하면 확률을 반환합니다.
   경로가 없으면 0을 반환합니다.

산출:

제공된 예:

으아아아

출력은 0.25가 됩니다.

이 접근 방식은 확률 계산의 세부 사항을 처리하면서 Dijkstra 알고리즘을 사용하는 효율적인 솔루션을 보장합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서저장소

에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 당신의 지원은 나에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요:

• LinkedIn
• GitHub

위 내용은 최대 확률의 경로의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!