算法导论实战(六)(算法导论习题三十四、三十五章)

2024-06-09 23:28

本文主要是介绍算法导论实战(六)(算法导论习题三十四、三十五章),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

前言

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

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

目录

前言

第三十四章

34.1-4

34.5-1

34.5-5

第三十五章

35.1-4

35.2-3

总结


第三十四章

34.1-4

问题描述:

练习 16. 2-2 中曾要求读者给出的 0-1 背包问题的“动态规划算法“,它是一个多项式时间的算法吗?解释你的答案。

问题分析:

首先回忆:0-1背包问题的动态规划算法是什么?

0-1背包动态规划算法:

0-1bag(w,v,n,m) //n表示物品数量,m表示背包最大重量let d(i,j) be a Two-dimensional arraysfor i=0 to nd(i,0)=0for j=1 to md(0,j)=0for i =1 to nfor j=1 to mif(j>w(i))d(i,j)=max(d(i-1,j),d(i-1,j-w(i))+v(i))elsed(i,j)=d(i-1,j)

分析算法我们不难知道算法的时间复杂度为O(nm),其中n为物品最大数量,m为背包重量上限 


问题本质就是让我们思考O(nm)这个时间复杂度是不是多项式时间的

时间复杂度分为:编码时间复杂度、非编码时间复杂度

很多算法在非编码情况下时间复杂度为多项式时间的,但是在编码下就是非多项式时间 

编码时间复杂度更贴和计算机实际运行的情况 

问题求解:

这不是一个多项式时间的算法。考虑问题的编码。通过给出每个物品的索引、价值和重量的二进制表示,可以进行多项式编码,这些被表示为长度为a = Ω(n)的二进制字符串(每个物品独立需要一串编码,不能用两个位表示四个物品)。我们在多项式时间内对W进行编码,这将有长度为Θ(log W) 的编码(能用两位表示四个重量)。这个长度为a + b的问题的解的时间为Θ(nW) = Θ(a · 2^b)。因此,该算法实际上是指数级的。

注:本题实际上是问算法实际运行的时间复杂度

34.5-1

问题描述:

子图同构问题取两个无向图 G1、G2, 要回答 G1 是否与 G2 的一个子图同构这一问题。 证明:子图同构问题是 NP 完全的。(本题就是证明子图同构问题是NP完全问题

问题分析:

证明L问题是NP完全问题的步骤:

  1. 证明L∈NP
  2. 选取一个已知的NP完全问题L’
  3. 描述一个归约函数f(x)能够把L‘归约到L
  4. 证明归约函数f的归约是多项式时间的
  5. 当且仅当L‘有解时L有解

总的思路:假设L’有解将每个实例归约成L,此时L也有解;但是L‘是NPC问题,所以L也是NPC问题无解

问题求解:

1、假如我们得到了G1、G2以及其对应的解——G2的子图G2‘与G1同构。此时我们只需要遍历G2’中的点和每一个与点相连的边,同时检查G1中是够有对应的点即可验证。这个验证的时间复杂度是O(EV)(其中E为G2‘的边集,V为G1的点集),所以是多项式时间。但是假如不知道G2哪个子图与G1同构,要去寻找的话,由于G2的子图有2^n个,所以寻找的时间显然不是多项式时间

2、选择团问题作为已知的NPC问题,接下去思考如何把团问题归约到子图同构问题上

3、假如现在我们有一个有解团问题<G,k>,即G中存在一个k规模的团(即有k个点的完全子图),记这个完全子图为Gk。此时我们构造一个G2,令G2是和Gk一样规模的完全子图。那么我们将G和G2放到子图同构中不难证明,G一定有子图Gk与G2同构

4、假如G有子图Gk与G2同构,那么至少G中会存在规模为k的团,即L语言在NPC问题L’中一定有对应的解。同时团问题有解时由3可知子图同构问题也一定有解。所以当且仅当关系证明完毕!

5、由于归约算法中,我们仅仅构造一个规模为k的完全图G2,所以这个归约算法是多项式时间内可以完成的

34.5-5

问题描述:

给定一个整数集合S,求集合S的一个划分S1和S2(即:S=S1∪S2且S1∩S2=Φ),使得S1中的元素之和等于S2中的元素之和(本题就是证明集合划分问题是NPC问题)

问题分析:

证明L问题是NP完全问题的步骤:

  1. 证明L∈NP
  2. 选取一个已知的NP完全问题L’
  3. 描述一个归约函数f(x)能够把L‘归约到L
  4. 证明归约函数f的归约是多项式时间的
  5. 当且仅当L‘有解时L有解

总的思路:假设L’有解将每个实例归约成L,此时L也有解;但是L‘是NPC问题,所以L也是NPC问题无解

问题求解:

1、假如给定一个集合S的划分S1和S2,那么分别对S1和S2的元素求和并比较,因此可以在多项式时间验证这个集合划分的正确性。同时如果并没有给这个S的划分,那么S1和S2的划分个数都有2^n个,所以寻找S1、S2算法的时间复杂度肯定不是多项式时间的

2、选择子集和求和问题作为已知NPC问题

3、假如存在一个集合U,已知其中的元素xi、xj,....,等之和为t,t为提前已经设定好的量。那么我们取这个集合U,令U’=U 并 {U-2t},此时U‘中就存在几个可拆分的集合对象。这时,可以确定新集合U‘中的集合元素可以拆分为两个U-t。因为只要将集合{U-2t}中的t挪动到U中即可。而t已知为xi、xj,....,等元素的和,所以是可以挪动的。证毕!

4、归约算法仅仅涉及有限集合的并以及拆操作,所以整体的归约时间必然是多项式的

5、当新集合U'中元素可以拆分为两个相等的元素时,我们可以令这两个相等元素为U-t。那么重新拆分组合这两个元素,可以得到集合U,并且其中有元素求和为t。也就是说此时集合U的子集和问题必然存在解。

第三十五章

35.1-4

问题描述:

给出一个有效的贪心算法,使其能够在线性时间内找出一棵树的最优顶点覆盖。

问题分析:

已知顶点覆盖算法是NPC难度的,题目要我们找可行的线性时间算法,本质就是让我们去使用近似算法找最优顶点覆盖

 所谓贪心算法实现就是算法导论中的方法

问题求解:

APPROX-VERTEX-COVER(G)C=ØE'=G.Ewhile(E'!=Ø)let (u,v) be a arbitrary edge of E'C=C ∪ (u,v)remove from E' every edge incident on either u or vreturn C

 该算法是一个多项式时间的2近似算法

问题深究: 

下面给出证明,说明为什么这个算法是多项式时间的2近似算法

 证:

定义C:为算法实际找出的顶点覆盖;C*:为图G最优顶点覆盖;A为算法找出的边的集合

由于每找到一个边(u,v)则把与u或v连接的边删除,所以A集合中没有两个边存在共同的顶点,即所有边都是不相连的。因此,想要覆盖这些边至少需要边个数的顶点,即有:

\left | C^* \right |>=\left | A \right |

由由于A的边并不相交,所以并不存在一个点连接两个边的情况,每个边的两个端点都是不相同的。因此有:

\left | C \right |=2\left | A \right | 

结合上面两个式子,我们可以得到:

 \left | C \right |=2\left | A \right |<=2\left | C^* \right |

即该算法是多项式时间上的2近似算法 

35.2-3

问题描述:

考虑下述用于构造近似旅行商旅行路线(代价函数满足三角不等式)的最近点启发式:从只包含任意选择的某一顶点的平凡回路开始,在每一步中,找出一个顶点 u, 它不在回路中,但到回路上任何顶点之间的距离最短。假设回路上距离u最近的顶点为 v, 则将u插入到v之后,从而对回路加以扩展。重复这一过程,直到所有顶点都在回路上为止。 证明:这一启发式方法返回的旅行路线总代价不超过最优旅行路线代价的2倍。

 问题分析:

 证明近似算法与最优算法代价的近似比:

1、确定近似算法产生的结果;

2、确定最优算法产生的结果;

3、找到两者中间的联系桥点

4、通过桥点来判断近似算法和最优算法的近似比

问题求解: 

按照这个思路来求解近似算法的近似比 :

1、确定近似算法产生的结果:每次选择一个点,将点插入到原本的回路中间,从而完成回路的拓展

2、最优算法产生回路的方式:回忆通过最小生成树来确定旅行路线的方法,可以知道生成最优旅行路线我们是每次选择一个点然后将该点加入已知回路(注意是加入不是插入

3、 顶点覆盖近似算法每次找的是边,所以中点桥点就是|A|;旅行商问题的最小生成树近似算法依靠生成树来解决问题,所以中间桥点就是c(T),即生成树的权值和。本题不需要一个特定的桥点,因为近似结果和最优结果内部就存在桥点可以利用

4、假设回路中已经存在vi,vi+1,现在想要插入ui。利用近似算法每次插入一个点,新增的值:

c(u_i,v_i)+c(u_i,v_{i+1})-c(v_i,v_{i+1})

根据三角形理论可以知道下面不等式:

 c(u_i,v_{i+1})<=c(u_i,v_{i})+c(v_i,v_{i+1})

将第二个不等式代入第一个式子中有:

 c(u_i,v_i)+c(u_i,v_{i+1})-c(v_i,v_{i+1})<=2c(u_i,v_{i})

 而最优结果每次加入点新增的值为(因为已知ui到vi的距离是最短的):

c(u_i,v_i)

 因此可以证明,每次新增的值近似算法是最优算法新增值的两倍,所以从总的代价上看,近似算法最终耗费也是最优算法最终耗费的两倍。证毕!

总结

本文到这里就结束啦~~

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

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

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

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

这篇关于算法导论实战(六)(算法导论习题三十四、三十五章)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1046600

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Pandas使用SQLite3实战

《Pandas使用SQLite3实战》本文主要介绍了Pandas使用SQLite3实战,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录1 环境准备2 从 SQLite3VlfrWQzgt 读取数据到 DataFrame基础用法:读

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python实战之屏幕录制功能的实现

《Python实战之屏幕录制功能的实现》屏幕录制,即屏幕捕获,是指将计算机屏幕上的活动记录下来,生成视频文件,本文主要为大家介绍了如何使用Python实现这一功能,希望对大家有所帮助... 目录屏幕录制原理图像捕获音频捕获编码压缩输出保存完整的屏幕录制工具高级功能实时预览增加水印多平台支持屏幕录制原理屏幕

最新Spring Security实战教程之Spring Security安全框架指南

《最新SpringSecurity实战教程之SpringSecurity安全框架指南》SpringSecurity是Spring生态系统中的核心组件,提供认证、授权和防护机制,以保护应用免受各种安... 目录前言什么是Spring Security?同类框架对比Spring Security典型应用场景传统

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.