首页  >  文章  >  后端开发  >  具有最大概率的路径

具有最大概率的路径

WBOY
WBOY原创
2024-08-28 06:40:37660浏览

1514。具有最大概率的路径

难度:中等

主题:数组、图、堆(优先级队列)、最短路径

给你一个由 n 个节点(0 索引)组成的无向加权图,由边列表表示,其中edges[i] = [a, b] 是连接节点 a 和 b 的无向边,有成功的概率遍历该边 succProb[i].

给定两个节点的起点和终点,找到从起点到终点成功概率最大的路径,并返回其成功概率

如果没有从起点到终点的路径,返回0。如果您的答案与正确答案相差最多 1e-5.

,我们将接受您的答案。

示例1:

Path with Maximum Probability

  • 输入: n = 3,edges = [[0,1],[1,2],[0,2]],succProb = [0.5,0.5,0.2],start = 0,end = 2
  • 输出: 0.25000
  • 说明:从开始到结束有两条路径,一条成功概率 = 0.2,另一条成功概率 0.5 * 0.5 = 0.25。

示例2:

Path with Maximum Probability

  • 输入: n = 3,edges = [[0,1],[1,2],[0,2]],succProb = [0.5,0.5,0.3],start = 0,end = 2
  • 输出: 0.30000

示例 3:

Path with Maximum Probability

  • 输入: n = 3,edges = [[0,1]],succProb = [0.5],start = 0,end = 2
  • 输出: 0.00000
  • 解释: 0 和 2 之间没有路径。

约束:

  • 2
  • 0
  • 开始!=结束
  • 0
  • a != b
  • 0
  • 0
  • 每两个节点之间最多有一条边

提示:

  1. 概率相乘会导致精度误差。
  2. 采用对数概率对数字进行求和而不是相乘。
  3. 使用 Dijkstra 算法求否定所有成本后两个节点之间的最小路径。

解决方案:

我们可以使用 Dijkstra 算法的修改版本。您将最大化成功的可能性,而不是寻找最短路径。

让我们用 PHP 实现这个解决方案:1514。概率最大的路径

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param Float[] $succProb
 * @param Integer $start_node
 * @param Integer $end_node
 * @return Float
 */
function maxProbability($n, $edges, $succProb, $start_node, $end_node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$n1 = 3;
$edges1 = [[0,1],[1,2],[0,2]];
$succProb1 = [0.5,0.5,0.2];
$start_node1 = 0;
$end_node1 = 2;

echo maxProbability($n1, $edges1, $succProb1, $start_node1, $end_node1);//Output: 0.25000


$n2 = 3;
$edges2 = [[0,1],[1,2],[0,2]];
$succProb2 = [0.5,0.5,0.3];
$start_node2 = 0;
$end_node2 = 2;

echo maxProbability($n2, $edges2, $succProb2, $start_node2, $end_node2);//Output: 0.30000


$n3 = 3;
$edges3 = [[0,1]];
$succProb3 = [0.5;
$start_node3 = 0;
$end_node3 = 2;

echo maxProbability($n3, $edges3, $succProb3, $start_node3, $end_node3); //Output: 0.00000
?>

解释:

  1. 图表示:图表示为邻接列表,其中每个节点都指向其邻居以及连接它们的边的成功概率。

  2. 最大概率数组:数组maxProb用于存储从起始节点到达每个节点的最大概率。

  3. 优先级队列:最大堆(SplPriorityQueue)用于首先探索概率最高的路径。这对于确保当我们到达目标节点时,找到概率最大的路径至关重要。

  4. 算法:

    • 将起始节点的概率初始化为1(因为停留在起始点的概率为1)。
    • 使用优先级队列来探索节点,更新到达每个邻居的最大概率。
    • 如果到达目的节点,则返回概率。
    • 如果不存在路径,则返回0。

输出:

对于提供的示例:

$n = 3;
$edges = [[0,1],[1,2],[0,2]];
$succProb = [0.5,0.5,0.2];
$start_node = 0;
$end_node = 2;

输出将为 0.25。

这种方法确保了使用 Dijkstra 算法的有效解决方案,同时处理概率计算的细节。

联系链接

如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!

如果您想要更多类似的有用内容,请随时关注我:

  • 领英
  • GitHub

以上是具有最大概率的路径的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn