具有最大概率的路径

梦晨姑娘_5542

梦晨姑娘_5542

2024-08-28

815人浏览

转载

1514。具有最大概率的路径

难度:中等

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

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

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

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

,我们将接受您的答案

示例1:

具有最大概率的路径

  • 输入: 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:

具有最大概率的路径

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

示例3:

具有最大概率的路径

  • 输入: 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 算法求否定所有成本后两个节点之间的最小路径。

解决方案:

GitHub Actions 工作流调试器
GitHub Actions 工作流调试器

使用 GitHub REST API v3 /actions/runs 和 /actions/jobs 端点诊断失败的 GitHub Actions 工作流程。解析步骤日志,识别 YAML 语法错误,并为运行器环境问题提供修复建议。

下载

我们可以使用 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速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

git 社交网络

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

相关专题

更多
堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7347

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2988

6

length函数用法
length函数用法

length函数用于返回指定字符串的字符数或字节数。可以用于计算字符串的长度,以便在查询和处理字符串数据时进行操作和判断。 需要注意的是length函数计算的是字符串的字符数,而不是字节数。对于多字节字符集,一个字符可能由多个字节组成。因此,length函数在计算字符串长度时会将多字节字符作为一个字符来计算。更多关于length函数的用法,大家可以阅读本专题下面的文章。

2023.09.19

2047

6

github中文官网入口 github中文版官网网页进入
github中文官网入口 github中文版官网网页进入

github中文官网入口https://docs.github.com/zh/get-started,GitHub 是一种基于云的平台,可在其中存储、共享并与他人一起编写代码。 通过将代码存储在GitHub 上的“存储库”中,你可以: “展示或共享”你的工作。 持续“跟踪和管理”对代码的更改。

2026.01.21

9045

27

GitHub官网入口版本汇总
GitHub官网入口版本汇总

本专题整合了GitHub入口版本地址汇总,阅读专题下面的文章了解更多详细内容。

2026.04.02

1078

19

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7456

4

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Postman Native Git工作流指南
Postman Native Git工作流指南

共0课时 | 0人学习

vscode手册
vscode手册

共0课时 | 0人学习

Git 教程
Git 教程

共21课时 | 8.2万人学习