算法设计与分析归纳.doc

动态规划法的适用条件
动态规划法解所能解决的问题一般具有以下两个基本因素：
一、最优子结构性质
当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。
二、重叠子问题性质
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
最短路径问题
设G是有向图，若G中从顶点i到顶点j有路径存在，找出最短的一条。
下面证明最短路径问题具有最优子结构性质：
证明：
设i,i1,i2,…,ik,j是从i到j的一条最短路径。从初始顶点i开始，设从i到下一顶点i1的判定已经做出。接下去，问题就转化为用i1替代i，重复原来的问题，找出一条从i1到j的路径。显然， i1,i2,…,ik,j一定构成了从从i1到j的最短路径（与原问题相同的最优子序列）
若不然，设i1, r1,r2,…,rp,j是一条从i1 到j的最短路径，则i,i1, r1,r2,…,rp,j将是一条从i到j的路径且比路径i,i1,i2,…,ik,j要短，得出矛盾。
所以，最短路径问题具有最优子结构性质。

0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

贪心算法采用逐步构造最优解的方法。它所作出的每一步决策都是当前状态下的局部最优选择。
1 贪心选择性质
即证明活动安排问题总存在一个最优解从贪心选择开始。

1 贪心选择性质
设A⊆E是所给活动安排问题的一个最优解，且A中的活动也按结束时间非递减排序，A中的第一个活动是k。
若k＝1,则A就是以贪心选择开始的最优解。
若k>1,设B=A-{k}∪{1}。因为f1<=fk且A中的活动是相容的。古B中的活动也是相容的。又由于B中的活动个数与A中的活动个数相同，故A是最优的，B也是最优的。即B是以选择活动1开始的最优活动安排。
由此可见，总存在以贪心选择开始的最优活动安排方案。

2 最优子结构性质
在作出了贪心选择，即选择了活动1后，原问题简化为对E中所有与活动1相容的活动进行活动安排的子问题。即若A是原问题的最优解，则A’=A-{1}是活动安排问题的E’={i∈E:Si≥f1}的最优解。
反证法：若E’中存在另一个解B’，比A’有更多的活动，则将1加入B’中产生另一个解B，比A有更多的活动。与A的最优性矛盾。
因此，每一步所作出的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。对贪心选择次数用归纳法可知，贪心算法greedySelector产生问题的最优解。
单源最短路径
其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。

P类和NP类语言的定义：
P={L|L是一个能在多项式时间内被一台DTM所接受的语言}
NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}
P Í NP

没办法：这两门课又可以放一下了，周五来解决。实在不行，就背一些概念题吧。

到目前为止可以看一些期末试卷了（晚上其他复习好之后）。