吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

时间:2022-08-30 17:11:15

    《设计和算法分析》课程,教学工作的厚礼,是《算法导论》(Sanjoy Dasgupta等待,清华大学出版社。2008年7第一个月1版本)。

    文章7周,主要教材 文章6章 动态规划 讨论。Dynamic Programming(简称DP)。是一个通用的问题求解方法,主要用于运筹学方面的最优化问题。因为其对思维能力的高要求。非常受各大公司笔试、面试欢迎。同学们在開始学习时。能够循序渐进,先理解教材中问题的精要并总结,然后去编程实现2-3个问题。最后去网上找3-10道笔试、面试题求解来开拓思路。

一:作业内容

    大家至少完毕下面作业中的一道题。以后从事IT业的同学,争取所有完毕。

(1) 背包问题。对上文中提到的背包问题提供的表1(数据文件下载 Knapsack.txt,第一行为背包总重量15,物品数量5;第2-6行。分别为第1-5件物品的重量与价值),W=15。编程计算终于背包所装物品的编号、总重量与总价值。要求可以把构造的二维表格输出到文件KnapsackResult.txt中。 博文标题:第7周作业1——背包问题

(2) 编辑距离

对数据文件edit.txt(下载请点击:edit.txt),当中第一行是须要计算的单词对,第2-4行。分别为两个词汇,请就算将第一个单词变换成第二个单词所须要的最少操作数(即:编辑距离)。请输出每组词汇的编辑距离。并尝试输出其对其方式(类似于教材P177最下行所看到的,- 号代表一个空隙)。

博文标题:第7周作业2——编辑距离

(3) 最长递增子序列。见博文  最长递增子序列具体解释(longest increasing subsequence)对此问题的解释,请先编程输出10个元素一组的随机整数数列,然后利用动态规划算法求其最长递增子序列的长度 及 具体的子序列。请多次測试与验证所编写的算法。 博文标题第7周作业3——最长递增子序列


二:作业要求

1. 请各班学委飞信通知同学完毕作业。

 
2. 作业计入平时成绩。计分根据为大家的完毕程度——态度(做 / 未做)。老师会根据大家作业的质量选择若干学生进行评论,以及提供个性化教学的根据。请大家根据自身能力,尽可能提供高水平的作业。为提高自身能力全力以赴。


3. 本次作业。老师主要检查本班学号位于11-20号的同学 和 申请免签到的同学,以及抽查部分其它同学,请大家相互转告。


三:提前预习

    预习 第7章 线性规划与归约(P205開始)。

理解线性规划问题的提出、网络流问题、二部图匹配。重点为单纯形算法(P232-241)。


四:推荐阅读

    成功不是偶然,对编程或其它方面的兴趣也是一个过程。仅仅有当我们了解一些基础后。才可能产生并激发兴趣。这里通过一篇博文,看一下大家的学长 郝中奎 的编程之路,以及软件专业大三学生骆宏的兴趣之路


五:讲授内容(整理)

(1)有向无环图的最短路径问题。Directed acyclic graph(简称:DAG)。这是我们第3次、第4次接触到有向无环图的应用了。首先大家回想一下,DAG有哪些特性?前面的章节中我们哪些问题有DAG有关?对DAG,我们又开展了哪些工作?温故而知新。

    DAG的一个重要性质是节点能够进行线性排列(拓扑排序),能够使用深度优先搜索(DFS)。并标记每个节点的第一次訪问(pre)和最后一次訪问时间(post),最后post的逆序就是DAG的拓扑排序,事实上也是节点在进行DFS搜索时。出栈的逆序就是拓扑排序。

    如何计算DAG的最短路径呢?第4章(P135-136)我们依照图中节点的拓扑排序的顺序依次计算节点的距离。其计算思路进一步能够表述例如以下所看到的的递推公式。

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

所以计算源点S到节点D的距离。能够通过先计算S到B、S到C的距离后,利用上述公式求解。以此类推,终于我们能够通过依次计算S到S、S到C、S到A……等把每一个节点的距离计算出来。

算法例如以下:

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

要点:不论什么一个动态规划问题,都能够等价为一个有向无环图DAG问题。

(2)动态规划的两个基本性质

(a)最优子结构性质:假设问题的最优解所包括的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。(b)重叠子问题性质:子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被反复计算多次。动态规划算法正是利用了这样的子问题的重叠性质。对每个子问题仅仅计算一次。然后将其计算结果保存在一个表格中,当再次须要计算已经计算过的子问题时,仅仅是在表格中简单地查看一下结果,从而获得较高的效率。

(3)最长递增子序列。输入类似下图中的一个数字序列,从中按顺序挑选一个子集。使得该子序列中数字满足严格单调递增关系。如以下,数列中的2、3、6、9 与 2、3、6、7等数列就是该数列的最长递增子序列。

如何计算呢?利用动态规划方法的性质,我们须要思考得到一个重叠子问题的结构。思考:假设2、3、6、9是一个最长递增子序列。那么去掉最后数字9与7之后,2、3、6也是数列5、2、8、6、3、6的最长递增子序列(最优子结构性质)。所以计算包含某一个数字(如9)并到该数字结束的的最长递增子序列。能够考虑该数字之前的子序列(5、2、8、6、3、6)中与9满足严格递增关系的数字(如 5、2、8、6、3、6)。假设计算得到了5、2、8、6、3、6等数字的最长递增子序列,选择当中最长的一条,则能够得到包含9在内的最长递增子序列。运算关系见下下图。

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

    未完待续……

(4)编辑距离

查找两个单词的相似度,在拼写检查等非常多场合中都有应用。前面我们补充过 利用余弦定理与TF-IDF来计算文档相似性(TF-IDF与余弦相似性的应用(一):自己主动提取关键词TF-IDF与余弦相似性的应用(二):找出相似文章),今天我们学习还有一种距离定义方式。

    编辑距离:将一个字符串变换为还有一个字符串所需最小编辑操作——包含插入、删除、字符替换的次数(教材P178)。

例如以下图中两个单词SNOWY和SUNNY。第一种方式次数为3,另外一种方式次数为5,但因为编辑距离指的是最小编辑操作,所以这两个单词的编辑距离为3。

把上面这个单词变换为以下单词,仅仅须要在S后插入U。把O替换为N,删除W,一共三个操作(当然还有其它方式)。

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

    如何把编辑距离的问题用动态规划方法求解,首先须要定义最优子结构。把单词 x[1···m] and y[1···n] 分成两部分:前缀部分和剩余部分。如前缀(Prefix)部分x[1···i] 和 y[1···j]。定义编辑距离的子问题E(i,j),则原问题即为计算E(m,n)。如 x[1···i]  和 y[1···j]。其对齐方式有三种(例如以下图,教材P179)。

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

如两个单词 EXPONENTIAL与POLYNOMIAL,其E(7,5)例如以下图所看到的。如今我们就能够写出递归形式了。 E(i,j)=min{1+E(i −1,j), 1+E(i,j −1), diff(i,j)+E(i −1,j −1)} ,寻找三种对齐方式下的最小编辑距离,而且成功的把E(i,j)问题转化为求解 E(i −1,j)。E(i,j −1)。E(i −1,j −1)等小一点的问题。


吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

明确了这一点,我们就能够依照算法伪代码,编出详细程序代码了。请思考图6-4(教材P180)。在计算得到编辑距离E(m,n)后。我们如何得到两个字符串的对齐方式呢?如何添加最少的代码实现呢?

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

(5)背包问题

网上有经典的 背包问题九讲,以及在此基础上的进一步学习(背包问题九讲笔记_01背包)。研究与总结的人非常多,如背包问题 笔试题,大家须要掌握单副本下的背包问题(教材P185)。

    单副本的背包问题(Knapsack without repetition):N件物品,分别重w1,...,wn,价值为v1,...,vn,现有一个背包最大容量为W,如何的组合才可以使背包中装下的物品价值最高?

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

摘自:    knapsack-problem(http://www.answers.com/topic/knapsack-problem)

如果我们对物品进行编号。则问题转化为 W=15,且物品编号、重量与价值例如以下表所看到的。为此,定义子问题,使包括关于哪件物品已经被使用过的信息。引入两个參数w、j,定义例如以下

K(w,j) = 基于背包容量w和物品1,…。j所能得到的最高价值。当中0≤j ≤n


表1:背包问题物品价值
物品 重量 价值
1 4 10
2 12 4
3 1 2
4 2 2
5 1 1

我们的目标是计算K(W,n)。怎样把K(w,j) 用更小的子问题来表示呢?非常easy:要么须要选择物品j以获得最高价值,要么不须要:
吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)
第一种情况仅当wj ≤w时成立,换句话说。K(w,j)  能够用子问题 K(·,j −1)来表示。于是。算法须要填写一个二维的表格。共同拥有W+1行 n+1列,算法复杂度为O(nW),算法伪代码例如以下。实现之。

吉克1111-1114第七周讲座班、家庭作业(动态规划,期限:2014年4月25日本23点-周五晚上,科委飞信通知学生)

(6) 矩阵连乘。大家依据教材P186-188,自己进行理解就可以。书仅仅有多读、多思考、多实践。才会有更深的体会。



版权声明:本文博客原创文章,博客,未经同意,不得转载。