算法导论实战(三)(算法导论习题第二十四章)

🌈 个人主页:十二月的猫-CSDN博客
🔥 系列专栏: 🏀算法启示录

💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 

目录

前言

第二十四章 

24.1-3

24.1-4

24.2-4

24.3-2 

24.3-3

24.3-6

24.3-8

24.3-10 

总结


前言

算法导论的知识点学习将持续性更新在算法启示录_十二月的猫的博客-CSDN博客,欢迎大家订阅呀(反正是免费的哦~~)

实战篇也将在专栏上持续更新,主要目的是强化对理论的学习(题目来源:山东大学孔凡玉老师推荐)

第二十四章 

24.1-3

问题描述

假设给定G=(V,E)是一带权重且没有权重为负值的环路的有向图,对于所有的结点𝑣∈𝑉,从源结点s到结点v之间的最短路径中,包含边的条数的最大值为m。请对算法BELLMAN-FORD进行简单修改,可以让其在m+1遍松弛操作之后终止,即使m不是事先知道的一个数值。

问题分析:

如果一个图所有节点到源点s的距离包含的边的条数的最大值为m,那么意味算法在进行m轮松弛后,整个图的所有节点都已经得到最短路径。此时不再需要继续执行m+1轮松弛

问题求解
在BELLMAN-FORD算法的2-4行的执行记录下松弛前各点的最短路径长度,如果某一次松弛循环结束时所有v.d的值跟本次循环开始时v.d的值相比不发生改变时,此次循环即为第m+1次。 

INITALIZE-SINGLE-SOURCE(G,s)
for i=1 to |G.V|-1for each v in G.Vsave v.d to Tfor each edge(u,v) in G.ERELAX(u,v,w)for each v in G.Vif v.d != T[v].dcontinue //没有点的值被更新,说明所有点都取到最短路径,则停止for each edge(u,v) in G.Eif v.d>u.d+w(u,v)return FALSEreturn TRUE

24.1-4

问题描述:
修改Bellman-Ford算法,使其对于所有结点v来说,如果从源结点s都结点v的一条路径上存在权重为负值的环路,则将v.d的值设置为−∞。

问题分析:

贝尔曼福德算法不能够处理存在权重为负值的环路,因为一旦存在则会一直在环路上循环,因为这样的最短路径值会不停缩短。该情况显然是我们不希望发生的,所以我们增加这一个功能来应对存在负值环路的特殊情况。

问题求解:

如果存在负权环路,那么w(u,v)就是无穷小,并且w(s,v)(就是v.d)也是无穷小,于是这个if语句返回值是FLASE。所以只要在if内增加对v.d的修正即可

INITALIZE-SINGLE-SOURCE(G,s)
for i=1 to |G.V|-1for each v in G.Vsave v.d to Tfor each edge(u,v) in G.ERELAX(u,v,w)for each v in G.Vif v.d != T[v].dcontinue //没有点的值被更新,说明所有点都取到最短路径,则停止for each edge(u,v) in G.Eif v.d>u.d+w(u,v)v.d=-∞return FALSEreturn TRUE

24.2-4

问题描述:

给出一个有效的算法来计算一个有向无环图中的点的路径总数。分析你自己的算法。

问题分析:

目前我们手头关于图的知识点只有图的基本算法+最短路径算法+最小生成树,利用这些知识点来思考如何找路径总数。考虑到本题不用考虑有权图,所以我们把眼光转向BFS和DFS两个算法。进一步思考,我们能知道BFS常常用在求解最短路径算法中(BFS特点在于得到的是一棵树,同时每个点都是最短路径的),在这里我们需要求解的是到一个点的所有路径。

假如我们有如下一个图,现在要我们来求解顶点6的路径数

朴素想法:我们最朴素的想法就是从顶点1、2、3、5、4、....、这样的顺序去求解路径数。于是我们可以得到p(1)=1; p(2)+=p(1); p(3)+=p(1); p(5)+=p(2); p(4)+=p(2); 等等。

总的来说,就是从上层到下层计算,下层的路径数:下层路径数+=上层路径数

那什么是下层?什么又是上层呢?

下层:在上层结点撤去后不存在入度结点的点;上层:存在出度给其他顶点

如果可以从上层到下层计算呢?我们就需要对图进行拓扑排序


拓扑排序:是一种对有向图进行排序的算法,其主要目的是确定图中节点的线性顺序,使得在排序后,所有的边都从左到右指向更大的节点。换句话说,拓扑排序可以将图中的节点按照其依赖关系进行排序,使得所有的依赖关系都被满足。

 实现拓扑排序的方法有两个:一、计算结点入度+队列方法(通用方法)二、深度搜索(用于无环路的有向图

本题是有向无环图可以用方法二


问题求解:

一、利用DFS搜索树,将图进行拓扑排序,得到拓扑排序后的图

二、在新的图中,按照拓扑排序的顺序,对每个点u,找其所指向的点v,执行v.paths+=u.paths

PATHS(G)topologically sort the vertices of Gfor each vertex u, taken in topologically sorted orderfor each v ∈ G.Adj[u]v.paths = u.paths + v.pathsreturn the sum of all paths attributes

24.3-2 

问题描述:

请举出一个包含负权重的有向图,使得 Dijkstra 算法在其上运行时将产生不正确的结果。为什么在有负权重的情况下,定理 24.6 的证明不能成立呢?

问题分析:

看到对本题的其中一个解答: 

大致意思是说:如果存在负权重回路,那么这个RELAX操作是没有意义的,因为RELEX是有限次的,但是通过负权重回路,我们到任何通过这个回路的点的距离都是−∞。于是在RELAX后,u.d并不是(s,u)的最小值,因此不成立

显然上面的证明是没有问题的,但是本题问的是为什么不能有负权重边,而不是负权重回路。所以仅仅有上面的证明是不充分的

问题求解:

Dijkstra算法是贪心贪心算法,也就是说每次都选择贪心策略下的局部最优解,这个解在后续中也不会再修正。那么对于如下的带有负权重的有向图:

假如源点是A,那么首先选择C此时C值为1;后选择B此时B的值为2,然后又会选择C此时C的值应该要修正为0.但是C的值不会被修正,因此Dijkstra每个点只访问一次(贪心策略)。所以最终C.d=1,但是实际上C到A的最小值为0。因此定理 24.6是不成立的,算法结束后,存在点的d的值不是最短路径值

24.3-3

问题描述:

假定将 Dijkstra 算法的第 行改为:

4 :white(lQl)>1

这种改变将让呻证循环的执行次数从 IVI 次降低到 IVI -1次。这样修改后的算法正确吗?

问题分析:

迪杰斯特拉算法最后得到的结果有两个:一、访问序列s,用来记录对点的访问次序;二、每个点的v.d记录每个点到源点的距离。

所以正确性的证明也将从这两个角度展开:

问题求解:

正确的!

一、假如我们已经得到前面V-1个点的访问序列,那么最后一个点不需要放入,我们也可以只知道最终的访问序列

二、迪杰斯特拉对每个结点只访问一次,且每次都能确定一个点的最短路径,此时程序运行了V-1个循环,访问并确定了V-1个点的最短路径。所以最后一个点进行松弛操作时,它并不能缩短其他点到原点的距离,所以最后一个点的RELAX操作也是无意义的。因此算法是正确的

24.3-6

问题描述:

问题分析: 

本题和最短路径问题存在几点不一样:

一、它需要找的是最可靠,也就是值最大的路径,可以认为是最长路径

二、最短路径算法相连路径段之间的关系是求和,但是通信链路相连路径段求可靠性时之间的关系是求积

问题求解:

一、最长路径。那就把贪婪准则改为选择d最大的点

二、总路径和子路径的关系变为乘。那就修改RELAX准则,从+变为*

三、初始化。源点可靠性为1;其他未搜索到的点初始化为0

INITIALIZE(G,s)for each vertex v ∈ G.Vv.d=0v.π=NULLs.d=1
DIJKSTRA(G,w,s) //s用来记录访问的顺序,是需要返回的值;w边的权重集合S=空集合Q=G.Vwhile(Q <> 空集合)u=EXTRACT-MAX(Q)S=S U {u}for each vertex v∈G.adj[u]RELEX(u,v,w) 
RELAX(u,v,w)if v.d<u.d*w(u,v)v.d=u.d*w(u,v)v.π=u

24.3-8

问题描述:

问题分析:

我第一次看这道题的时候,说实话,连题目都没看懂【emmmmm】。具体原因就在权重函数w:E->{0,1,...,W}这里没看明白。

这个权重函数就表示:边E的权重只能取{1,2,....,W}中的数

再来看看这个WV时间复杂度是哪里来的?要解决这个问题

先让友友们先思考另一个问题:WV含义是什么?

WV含义:图中任意点到源点的距离上限(图中任意点到源点的距离不超过WV)


再来思考一个这个E的时间复杂度含义又是什么?

E是指边,也就是说我需要对边进行E次操作,这不禁让我们想到了松弛操作。

E的复杂度就代表我们要对所有边进行一轮的松弛,每次松弛边本质是更新点的V.d,所以本质就是对点进行了E次的操作

问题求解:

从优化“贪心寻找dist最小点”的操作入手。由于边权≤W≤𝑊,那么一个点的dist值不会超过VW。基于这个条件,我们可以抽象出一个长度为VW的队列数组。每个数组的队列存储着“dist值为该数组序号”的点。然后抽象出一个指针,这个指针指向的队列,是我们贪心取点的队列。由于一个点被取出后,被他更新的点只会被push进该队列或者该队列之后的队列,所以指针只会从左到右扫描一遍数组。

最多扫描一遍数组,复杂度为O(VW)。此外,最多会有E次入队、出队操作,复杂度为O(E)。总时间复杂度为O(VW+E)。

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = ..., M = ..., W = ...;
queue<int> qs[N*W];
int head[N], ver[M], edge[M], Next[M], tot = 0;//采用数组模拟邻接链表的方式
void add(int x,int y,int z){ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
int d[N], v[N];
int n, m, w;
void dijkstra(int s){memset(d,0x3f,sizeof(d));//初始化为正无穷memset(v,0,sizeof(v));d[s] = 0; qs[0].push(s);for(int k = 0; k<=n*w; k++){while(!qs[k].empty()){int x = qs[k].front(); qs[k].pop();if(v[x]) continue;v[x] = 1;for(int i = head[x]; i; i = Next[i]){int y = ver[i], z = edge[i];if(d[y] > d[x] + z){d[y] = d[x] + z;qs[d[y]].push(y);}}}}
}

24.3-10 

问题描述:

假设给定带权重的有向图 G=(V, E), 从源结点s发出的边的权重可以为负值,而其他所有边的权重全部是非负值,同时,图中不包含权重为负值的环路。证明: Dijkstra 算法可以正确计算出从源结点到所有其他结点之间的最短路径。 

问题分析:

证明Dijkstra 算法是可行的==证明一个贪心策略是有效的。考虑到Dijkstra 算法本身的贪心策略已经证明结束,所以我们只需要针对其中变化的部分进行特别论证即可

特别部分:从源结点s发出的边的权重可以为负值

利用 Dijkstra 算法取出S,并更新与S相邻的点,将得到多个值不为0的点

于是,该问题可以等效为:多源点且初始值不为0的最短路径问题,并且每个源点都可以适用Dijkstra 算法

因此,整个问题同样可以利用 Dijkstra 算法来求解

问题求解:

首先,Dijkstra的算法思路是:对于任意一个从队列取出来的点x,如果它没有被标记过,那么d[x]一定是源结点s到x的最短路径,然后我们不断地进行贪心扩展,最终可以得到源结点s到每个结点的最短路径。它的本质是一个贪心+BFS算法。
现在,题目中给出的限制是:“只有从源结点s出发的边权重可以为负,且图中无负环”。
源结点s一定是在一开始被取出,更新完之后被丢弃。因为只有源结点s出发的边权重可以为负,所以我们在后面更新由“s以外的其他点”更新“s以外的其他点”时,仍旧是在一个无负边权的图中的更新,所以Dijkstra仍正确。而对于这些点,当他们尝试更新s的时候,因为图中无负环,所以无法更新s。此外,由于无负环,s也不会出现有一个权值为负的子环无限更新自身的情况。综上,Dijkstra基于贪心的性质没有发生改变,每次从队列中取出的一个点更新完其他点被丢弃后,这个点在后面一定不会被更新。所以Dijkstra仍旧可以正确运行。

总结

本文到这里就结束啦~~

本篇文章的撰写花了本喵四个多小时

如果仍有不够,希望大家多多包涵~~

如果觉得对你有帮助,辛苦友友点个赞哦~

知识来源:《算法导论》课后习题、山东大学孔凡玉老师ppt。不要用于商业用途转发~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/343658.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DVWA-XSS(Reflected)

反射型XSS可以用来窃取cookie Low 输入1111进行测试&#xff0c;发现1111被打印 输入<script>alert(document.cookie)</script>&#xff0c;出现弹窗&#xff0c;获得cookie Medium 查看后端代码&#xff0c;发现对<script>进行了转义&#xff0c;但是…

【UML用户指南】-10-对高级结构建模-高级类

目录 1、类目 2、高级类 3、可见性 4、实例范围和静态范围 5、抽象元素、叶子元素和多态性元素 6、多重性 7、属性 8、操作 9、模板类 10、标准元素 1、类目 类目 &#xff08;classifier&#xff09;是描述结构特征和行为特征的机制。类目包括类、关联、接口、数据类…

nvm安装使用

什么是 node.js&#xff1f;&#xff1a; Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行时&#xff0c;可以在服务器端运行 JavaScript。由于其非阻塞 I/O 模型和事件驱动架构&#xff0c;Node.js 非常适合构建高并发、低延迟的应用程序。随着 Node.js 的不断发展&…

STM32作业实现(四)光敏传感器

目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…

SSM框架整合,内嵌Tomcat。基于注解的方式集成

介绍&#xff1a; SSM相信大家都不陌生&#xff0c;在spring boot出现之前&#xff0c;SSM一直是Java在web开发中的老大哥。现在虽说有了spring boot能自动整合第三方框架了&#xff0c;但是现在市面上任然有很多老项目是基于SSM技术的。因此&#xff0c;能熟练掌握SSM进行开发…

BL104网关钡铼技术多协议设备互操作简单一键接入

在工业环境中&#xff0c;设备之间的通信和互操作性是实现智能化生产的关键。为了满足这一需求&#xff0c;钡铼技术推出了PLC物联网关BL104&#xff0c;一款专为工业环境设计的多协议设备&#xff0c;简化了设备互操作的复杂性&#xff0c;实现了一键接入的便捷性。 PLC物联网…

30、matlab现代滤波:维纳滤波/LMS算法滤波/小波变换滤波

1、信号1和信号2的维纳滤波 实现代码 N 2000; %采样点数 Fs 2000; %采样频率 t 0:1 / Fs:1 - 1 / Fs; %时间序列 Signal1 sin(2*pi*20* t) sin(2*pi*40* t) sin(2*pi*60* t); Signal2[2*ones(1,50),zeros(1,50),-1*ones(1,100),zeros(1,50),-2*ones(1,50),zeros(1,50),1…

国产主流软硬件厂商生态分析

国产领域主流厂商汇总 信创&#xff0c;即信息技术应用创新&#xff0c;由“信息技术应用创新工作委员会”于2016年3月4日发起&#xff0c;是专注于软硬件关键技术研发、应用与服务的非营利性组织。作为科技自强的关键力量&#xff0c;信创在我国信息化建设中占据核心地位&…

GWT 与 Python App Engine 集成

将 Google Web Toolkit (GWT) 与 Python App Engine 集成可以实现强大的 Web 应用程序开发。这种集成允许你使用 GWT 的 Java 客户端技术构建丰富的用户界面&#xff0c;并将其与 Python 后端结合在一起&#xff0c;后端可以运行在 Google App Engine 上。 1、问题背景 在 Pyt…

通过Excel,生成sql,将A表数据插入B表

文章目录 投机取巧的方式,进行表数据初始化通过navicat搜索A表数据,然后复制进excel中通过excel的函数方式,将该批量数据自动生成插入B表的sql语句然后一次性拷贝生成的sql语句,放进navicat中一次执行,直接完成数据初始化

fps游戏如何快速定位矩阵

fps游戏如何快速定位矩阵 矩阵特点: 1、第一行第一列值的范围在**-1 ---- 1**之间&#xff0c;如果开镜之后值会变大。 2、第一行第三列的值始终为 0。 3、第一行第四列 的值比较大 &#xff0c; >300或者**<-300**。 根据这三个特点&#xff0c;定位矩阵已经足够了…

如何安装 CleanMyMac X 4.15.3破解版

CleanMyMac X 4.15.3破解版是一款专业的Mac系统清理软件&#xff0c;可一键智能扫描清理mac系统日志缓存磁盘垃圾和多余语言安装包&#xff0c;快速释放电脑内存&#xff0c;轻松管理和升级Mac上的应用。同时CleanMyMac X 破解版可以强力卸载恶意软件&#xff0c;修复系统漏洞&…

WPF中读取Excel文件的内容

演示效果 实现方案 1.首先导入需要的Dll(这部分可能需要你自己搜一下) Epplus.dll Excel.dll ICSharpCode.SharpZipLib.dll 2.在你的解决方案的的依赖项->添加引用->浏览->选择1中的这几个Dll点击确定。(添加依赖) 3.然后看代码内容 附上源码 using Excel; usi…

变压器绕线完成之后要做的事

1 调整感量&#xff1a;测主绕组电感量&#xff0c;通过磨气隙或垫气隙&#xff0c;测得感量没错以后&#xff0c;用胶带封装磁芯 2 测验同名端是否正确&#xff1a;两绕组首尾相连&#xff0c;测试连接后的总感量&#xff0c;是否比感量大的那个绕组还大。如果是&#xff0c;…

EasyExcel导出多个sheet封装

导出多个sheet 在需求中&#xff0c;会有需要导出多种sheet的情况&#xff0c;那么这里使用easyexcel进行整合 步骤 1、导入依赖 <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId></dependency><d…

ssti模板注入

一、Flask应用 1、介绍 定义 Flask&#xff1a;是一个使用Python编写的轻量级web应用框架。Flask基于Werkzeug WSGI工具包和Jinja2模板引擎。 特点 良好的文档、丰富的插件、包含开发服务器和调试器、集成支持单元测试、RESTful请求调度、支持安全cookies、基于Unicode。 …

霸气的短视频:成都科成博通文化传媒公司

霸气的短视频&#xff1a;瞬间的力量与魅力 在数字化浪潮中&#xff0c;短视频以其独特的魅力迅速崛起&#xff0c;成为社交媒体的新宠。而在众多短视频中&#xff0c;那些充满霸气、让人热血沸腾的作品&#xff0c;总能引起广泛的关注和讨论。成都科成博通文化传媒公司将从内…

在线OJ项目测试(selenium+Junit5)

目录 在线OJ项目测试的思维导图 在线OJ的UI自动化测试 测试一&#xff1a;检查未登录时的页面访问以及一些未登录时的非法操作 测试二&#xff1a;测试注册界面 测试三&#xff1a;测试登录界面 测试四&#xff1a;测试题目列表界面 测试五&#xff1a;测试题目详情界面…

优化财务管理制度提升企业经营效益—以审计代理记账为例

随着社会经济的快速发展&#xff0c;企业经营规模不断扩大&#xff0c;面临的财务管理问题也日益复杂&#xff0c;而作为其中的重要一环&#xff0c;审计代理记账已经成为了企业的必要组成部分&#xff0c;本文将重点探讨审计代理记账对于优化企业财务管理&#xff0c;提高经营…

Vue 学习笔记 总结

Vue.js 教程 | 菜鸟教程 (runoob.com) 放一下课上的内容 Vue练习 1、练习要求和实验2的用户注册一样&#xff0c;当用户输入后&#xff0c;能在下方显示用户输入的各项内容&#xff08;不需要实现【重置】按钮&#xff09; 2、实验报告中的实验小结部分来谈谈用JS、jQuery和…