算法设计与分析5

算法设计与分析基础

IntroductiontotheDesignandAnalysisofAlgorithms

第五章减治法

DecreaseandConquer第

5

章减治法

算法策略

插入排序

深度优先搜索DFS

广度优先搜索BFS

拓扑排序生成组合对象减常因子法减可变规模法概念与算法策略算法策略减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现——自顶向下：规模减小（递归）

自底向上：规模增大（非递归）减常量法：常量通常为1（减1

法）减常因子法：常因子通常为2（减半法）减可变规模法：每次减去的规模不同原问题(规模n)子问题(规模n-1)子问题解原问题解减一技术子问题(规模n/2)子问题解原问题解原问题(规模n)减半技术×插入排序插入排序对n个元素A

[

0,...,n-1

]排序（非降序为例）减一策略——分析过程自顶向下（规模减小）减去一个元素A[n-1],对

A[

0,...,n-2

]排序（非降序）

原问题的解=减一规模的解+A[n-1]对数组递归减一，分解到仅一个元素为止；再合并得到原问题解。插入算法

——有三种方法插入一个元素，左右扫描称直接插入法

左扫描：从左向右扫描有序子数组，遇到第一个≥A[n-1]元素为止，在该元素前插入A[n-1].若未找到，则插在最后。

右扫描：从右向左扫描有序子数组，遇到第一个≤A[n-1]元素为止，在该元素后插入A[n-1].若未找到，则插在最前。常用：右扫描法。问：理由是什么？理由：子数组若有等值元素，右扫描插入时需移动的元素个数少。

——它插在等值元素后，前面等值元素都不用移动位置插入排序算法与算例折半插入法——

组合利用减一法和减半法子数组有序，用折半查找为插入元素在其中找到一个合适的位置。算法伪码基于递归思想设计，但非递归实现（从底向上）下划线为待插元素思考：为什么是右扫描插入V？插入排序效率分析插入排序效率分析输入规模：元素个数n基本操作：比较操作A[

j

]>V效率类别：输入A为升序，每次插入只需比较1次——最佳效率

输入A为降序——最差效率，其他——平均效率最佳效率：要插入n-1个元素，共需比较n-1次（线性效率）也可据伪码计算：最差效率对每个元素如第i个元素插入，从j=i-1比较到j=0，共i次比较，即插入元素A[

i

]要与前面的全部元素都比较一次。

平均效率：比最差效率快2倍。若遇到基本有序数组，比选择排序和冒泡排序的性能略优。图的遍历深度优先搜索DFS(Depth-FirstSearch)随后两节讨论图的一些常用算法，可看作是减一技术的应用。图是一种令人感兴趣的、有着广泛应用的数据结构。许多实际问题的计算模型——图结构

1.领土问题2.交通网络3.通信网络4.棋局、迷宫……图的遍历——从起点出发访问所有顶点。可能遇到的问题：1.非连通图：不能访问到某些顶点。

2.存在回路：要防止陷入死循环。

——为每个顶点设置访问标志(mark).开始时：所有顶点的访问标志置零遍历时：已访问顶点的标志被标记，以后不访问它，防止回路循环结束时：检查顶点标志。若有未标记顶点，则重选起点，继续遍历深度优先搜索DFS许多图的算法要求对图进行遍历或周游(graphtraversal).主要两种：

DFS(Depth-FirstSearch),BFS(Breadth-FirstSearch).DFS深度优先搜索过程简述从任一顶点（问题确定）出发，沿某一路径搜索该路径上所有未访问顶点，到达死端（所有相邻顶点都已访问过），沿原路后退一条边，从那里继续访问未访问过的顶点（回溯）；当回溯到开始顶点，并且它成为死端时，DFS过程结束。

顶点选择策略：搜索过程中，若某顶点有多个邻接顶点，可以按顶点编号（或其他策略如优先值大小选择顶点）进行访问，下页图示。DFS搜索的非递归实现——栈过程

1.当前顶点入栈2.将栈顶顶点的下一个未访问邻接顶点入栈若栈顶顶点无未访问邻接顶点，该顶点退栈（回溯）

3.重复2，直到栈空为止，DFS过程结束DFS算法构造出一棵DFS树（或森林）DFS算法过程图示DFS算法过程图示（以树为例）12345678910111213141516171819202122根据访问顺序，用连续整数标记各个顶点，如图。红色箭头表示回溯过程。DFS算法的栈过程图示DFS栈过程图示AEBCDF从顶点A开始DFSACABCAFBCADFBCAEFBCAFBCABCACAAFBCA顶点选择策略——未访问邻接顶点有多个，按顶点编号的字母序访问。栈空时，DFS遍历结束。DFS可产生进栈、退栈两种顶点线性序列，可按实际情况的需要选用。顶点进栈的线性序列：ACBFDE顶点退栈的线性序列：DEFBCADFS树与森林DFS树与森林DFS可构造出一棵深度优先搜索树（可转换为有根树）或森林树边：图中当前顶点到未访问儿子顶点的边，如CB,FE回边：图中当前顶点到已访问祖父顶点的边，如EA,DCDFS树：不含回边的树（无环图）（只有树边）DFS森林：包含回边的图（有环图）（含有回边）右图实际上不是森林（不连通的多棵树），而是一种类森林的表示。若将其转换为DFS树，不同的顶点选择策略如选择C顶点的下一个邻接顶点为D或者B，可以得到不同的DFS树，这些树组成森林。AEBCDFDFS树AEBCDFDFS森林DFS递归算法DFS递归版DFS非递归算法DFS非递归版vtopSPush(v)DFS的时间效率DFS时间效率分析输入规模：顶点数

n基本操作：顶点访问判断Mark[w]=0，简称：访问顶点效率类别：对于给定图，无最佳、最差、平均效率增长函数——基本操作数与顶点数n的关系：T(n)=?它与给定图的表示法（邻接矩阵、邻接链表）有关

一、图的邻接矩阵表示访问下一个邻接顶点，要检查余下所有顶点，判断是不是邻接顶点。起点开始，从余下n-1个顶点选择一个；再访问下一顶点，从n-2个顶点中选一个；如此继续，每次余下的顶点数序列：n-1,n-2,...,1

访问的顶点总数（基本操作数）：

T(n)=(n-1)+(n-2)+...+1=n(n-1)/2∈Θ(n2)

思考：这与给定图G=<V,E>是稠密图或稀疏图有关吗？无关：当前顶点并不知道下一个相邻顶点，需要在剩余顶点中寻找，与连接形式无关。图的邻接链表表示DFS的时间效率：邻接链表表示图二、图的邻接链表表示：下一个邻接顶点在链表中是确定的acbdef访问顶点数与n的关系：1.每个表头顶点需要访问，以找到该顶点开始的邻接顶点链2.每个链表的剩余顶点需要访问剩余顶点数等于该链表的边数访问顶点总数等于上述两项之和：

T(n)

∈Θ(|V|+|E|)|V|=n,|E|∈[0,n(n-1)

/

2]

|E|min=0：一个顶点|E|max=n(n-1)

/

2：完全图结论：稠密图——邻接矩阵表示较好无链表的额外开销稀疏图——邻接链表表示较好DFS简单应用DFS简单应用DFS检查图的连通性从任意顶点开始DFS遍历，当遍历算法停止以后，检查是否全部顶点都已访问过。若都访问过，此图是连通的。否则，此图不连通。因为遍历算法不能到达的顶点，说明它与图的其他顶点没有路径可通。DFS检查图的无环性如果从某个顶点到它的祖先顶点之间有一条回边，则该图存在回路，以此检查给定图的环。若不存在这样的回边，则为无环。DFS其他应用例如：求图的关节点（从图中移走某个顶点及其与它相连的边以后，图被分为若干个不相交的部分，该顶点称为关节点）等更复杂应用。BFS算法过程图示（以树为例）BFS算法过程图示（以树为例）12581216212213179143671015181920114根据访问顺序，用连续整数标记各个顶点，如图。BFS搜索的队列过程图示BFS队列过程图示AEBCDF从顶点A开始BFSA头A入队，开始BFSCEA出队，A的邻接顶点C,E入队FD出队，D无未访问邻接顶点入队DFB出队，B无未访问的邻接顶点入队EBDFC出队，C的邻接顶点B,D,F入队BDFE出队，E无未访问的邻接顶点入队F出队，F无未访问的邻接顶点入队此时队列空，BFS过程结束顶点出、入队线性序列

ACEBDFBFS树或森林森林解释见DFSAEBCDF交叉边BFS非递归算法BFS非递归算法BFS相关讨论BFS相关讨论时间效率：同DFS效率一样。前面讨论DFS的效率时，仅与图的存储

结构（邻接矩阵、邻接链表）有关，与DFS或BFS无关应用1：检查图的连通性和无环性，本质上与DFS一样应用2：求给定两个顶点的最短路径（边数最少，非带权图）从两个给定的顶点之一开始BFS，当访问到另一个顶点，BFS结束从BFS算法过程看，其正确性不言而喻，但数学上的证明并不简单

说明：这样的最短路径可能不只一条（考虑去掉BG边的图）

BFS树的一部分，确定了从A到G的最短路径（边数最少）AEBCDFGHAEBCFG拓扑排序拓扑排序(TopologicalSort)概述问题提出假设要安排一系列任务，如教学计划中的安排各门课程的学习顺序，项目中各子课题的研究顺序，建筑项目，……等等。每个任务只有当前提条件具备时，才能去完成这个任务。举例如下：

——只有当学完某课程的全部前修课程后，才能安排该课程的教学拓扑排序

找到在满足前提条件情况下，各个任务如何安排的一个线性序列计算模型——图（顶点：一个任务，边：该任务的前提条件）

1.有向图：任务之间有先后关系——边有方向

2.无环图：若有环，回路中就会存在彼此矛盾的条件。（想一想）不可能在不违反前提条件情况下，为这些任务安排一个合理的顺序，问题无解（存在矛盾条件）

综合1、2，若拓扑排序问题有解，必须是有向无环图拓扑排序：有向无环图有向无环图

无向图：仅有2种类型的边——树边、回边

有向图：可有4种类型的边1.树边：ABBCDE2.回边：BA（无回边:无环图）3.前向边（祖孙边）当前顶点到孙子顶点的边AC4.交叉边（横跨边）上述3种类型以外的边DCAEBCD有向有环图AEBCDA为起点的DFS森林ACBED有向无环图去掉BA边则为有向无环图拓扑排序算法：DFS法例1拓扑排序算法拓扑排序DFS算法

【例1】5门课程的安排，问题模型如图ACBEDC有两门前修课AB，E有两门前修课CD,必须先安排前修课程。因此，正确次序是：先安排AB，然后安排C；接下来安排D，最后安排E.即正确的线性序列序列为：

ABCDE

或BACDE（非唯一解）任选一个源顶点开始DFS过程：源顶点：没有入边，即无前提条件的边

——我们选A开始DFSA到E搜索完后，尚有未访问顶点B，将B入栈，从B重新开始DFS.进栈序列：ACDEB进栈逆序：BEDCA出栈序列：EDCAB出栈逆序：BACDE问题模型图BCAEDDFS森林拓扑排序算法：DFS例2DFS解拓扑排序【例2】7个任务的安排2163754问题模型图2163754DFS树仅有树边退栈线性序列：7546231（或7543621）退栈线性逆序：1326457（或1263457）解不是唯一的，与顶点选择策略即路径选择有关拓扑排序的源删除算法拓扑排序的源删除算法（减一法）

每次减去一个源顶点若算法结束（无源顶点），尚有未访问顶点时，问题无解！

——存在矛盾条件

顶点的删除顺序即拓扑排序的一个解（不唯一），本例ABCDE源删除算法与数据结构

1.找出全部源顶点并入队。若无源顶点，算法停止。有未访问顶点？

Yes——无解；No——输出解（记录的顶点序列）2.队头顶点出队并记录，删除与该顶点连接的所有边，返回1问题模型图ACBEDCBEDCEDEDE生成组合对象算法：生成排列生成组合对象组合对象：满足一定约束条件的集合组合数学：指出组合对象有多少个——组合数（通常呈指数级增长）如何生成：本节内容生成排列（前面讲过蛮力法）生成集合元素的全排列，可解释为：

——生成集合元素下标

{1,2,...,n}的全排列，排列数=n

!个减一策略：设规模减一{1,2,...,n-1}的全排列已解决，有

(n-1)

!个把n插入到这(n-1)

!个排列中去，就解决了规模n的问题，即得

{1,...,n}全排列。在每个{

1,...,n-1

}排列中，插入n的位置有(n-1)

+

1=n个，排列数=(n-1)

!×n=n

!

问：这样得到的排列是唯一的吗？

答：是。(n-1)

!个排列是唯一的，在其不同位置插入一个新元素n，结果当然唯一生成组合对象算法：生成排列（2）减一算法（实现——从底向上，规模增加）在{

1,...,n-1

}排列中，可以从左向右或从右向左插入n较好的插入法：（有什么好处？）1.开始时，从右向左插入n到{

1,...,n-1

}子排列的n个位置上2.每次插入完一个子排列，换方向插入n到下一个子排列，如下：开始

1插入212

21(←)插入3123132312(←3)321

231213

(→3)插入4……(4

!=24个)最小变化：仅交换排列的相邻两个元素，可得直接后继排列。例如：交换3

1

2

的12两元素可得直接后继排列321.即相邻两个排列，交换一次元素的位置可以变成另一个。非最小变化情况，下例：123和312：元素交换一次不能变成另一个，当然它们不是相邻的好处：满足最小变化

——提高算法效率，便于相关应用选用提高效率：可只插入一个元素，然后交换元素位置可得后续排列生成幂集生成幂集幂集n元集合A={a1,a2,...,an}的全部子集组成的集合子集个数：2n

（数学）应用举例——0-1背包问题找出n个物品中的最有价值子集，装入一个承重有限的背包中。解背包问题的蛮力法要求：生成n个物品的全部组合减一策略（用元素的下标表示）设{

1,2,...,n-1

}问题已解决（规模-1），把n插入到每一个子集，即得规模n的全部子集。与前述排列问题的减一策略的不同处：

排列问题在每个{1,...,n-1}子集中插入元素n的位置有n个，组合问题仅1个插入位置。（为什么？）

解释：排列问题与元素在排列中的顺序有关，组合问题与顺序无关，全部元素相同的集合就是同一个集合。生成幂集：减一算法减一算法（实现——自底向上，规模加一）从空集开始，每次向已生成的每个子集中加入一个元素，如此继续，直到所有n个元素都加入为止。

例：生成A={a1,a2,a3}全部子集n子集（元素下标表示）子集数开始{}20=11→{}{1}21=22→{}{1}{2}{1,2}22=43→{}{1}{2}{1,2}{3}{1,3}{2,3}{1,2,3}23=8生成幂集：小规模算法子集的比特串表示每个比特（二进制位）表示有、无两种状态：1－有，0－无例如：集合A={a1,a2,a3}，3个比特表示23=8个子集

比特串

000001010011100101110111

子集

{}{a3}{a2}{a2,a3}{a1}{a1,a3}{a1,a2}{a1,a2,a3}十进制数

01234567生成幂集的简洁算法一个n元集合，产生

0,1,...,2n-1的十进制数序列，其二进制序列即该n元集合的全部子集。最小变化比特串

——与前述最小变化定义不同生成的相邻两个比特串仅一个比特不同。例如：

001与010不是最小变化比特串，二位不同。注：不是一次交换格雷码：最小变化比特串，生成算法见相关文献（ACM考题）000001011010110111101100减常因子算法减常因子法减治法的第2种变化。折半查找——常因子=2，注意与分治法区别这类算法效率常常是对数型，速度非常快，不要指望有很多此类算法，常因子≠2的情况更是少之又少。常因子=3，每次规模减2

/

3.假币问题有n枚外观相同的硬币，其中有一枚假币。设假币较轻，用一架天平将这枚假币检测出来减常因子策略（多种方法，这里仅用减治策略）把n枚硬币等分为两堆——n为奇数：留下一枚硬币，把两堆放天平上。若两堆硬币重量相同，

留下这枚即为假币n为偶数：较轻的一堆含假币，继续分解它，丢弃较重的那一堆——常因子=2，减半法假币问题（续）时间效率分析输入规模：硬币数n基本操作：称重（比较操作）效率类别：有最佳、最差、平均效率情况增长函数：称重次数与硬币数n的函数关系T(n)=?1.最佳效率T(n)=1(n为奇数)2.最差效率

解此递推式，得本算法并非最高效的算法！更高效的策略是：每次把n个硬币分为3堆，常因子=3，每次减去问题规模的2/3.称重次数约为log3n,比log2n更小。需要作1次称重将问题规模减半减常因子法——俄式乘法减常因子法算例——俄式乘法（俄国农夫法）问题：两个正整数相乘。十九世纪，俄国农民广泛采用该算法