当前位置：文档之家 › 算法设计与分析(第二版) 第7章

算法设计与分析(第二版) 第7章

  • 格式：ppt
  • 大小：1.70 MB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

《算法设计与分析》教案

《算法设计与分析》教案
for(int k=0;k<4;k++) cout<<m[k]<<" ";
cout<<endl;
}
}
}
}
}
2、数字全排列（使用STL）
#include<iostream>
#include<algorithm>
using namespace std;
const int n=4;
int main()
{
int a[4]={2,4,3,1};
if(l==r-1)
{ if(a[l]>a[r]) { max=a[l]; min=a[r]; }
else { max=a[r]; min=a[l]; }
return;
}
int m = (l+r)/2;
T max1,max2,min1,min2;
MaxMin(a, l, m, max1, min1);
例：在n个元素中找最大值和最小值（非递归程序）
template<class T>
void MaxMin(T a[], int n, T& max, T&min)
{
if(n==1) { max=min=a[0]; return; }
if(a[0]>a[1]) { max=a[0]; min=a[1]; }
{
if(k==m)
{#43;+) cout<<a[i]<<" ";
cout<<endl;
}
else
for(int i=k;i<=m;i++)

算法设计与分析课件

算法设计与分析课件
2
ACM国际大学生程序设计竞赛
ACM国际大学生程序设计竞赛（英文 全称：ACM International Collegiate Programming Contest（ACM-ICPC或 ICPC）是由美国计算机协会（ACM）主办 的，一项旨在展示大学生创新能力、团队 精神和在压力下编写程序、分析和解决问 题能力的年度竞赛。经过30多年的发展， ACM国际大学生程序设计竞赛已经发展成 为最具影响力的大学生计算机竞赛。赛事 目前由IBM公司赞助。
主要内容介绍（续）
• • • • 第 7章 第 8章 第 9章 第10章 概率算法 NP完全性理论 近似算法 算法优化策略
1
相关先导基础课程和算法概述
专业基础课程： 数据结构、计算机语言(C++)、操作系统 如何编写计算机程序： • 数据结构+算法 = 程序 • 算法：计算机软件的“灵魂” 算法是计算机科学和计算机应用的核心
1.2 算法复杂性分析
Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=Ω (g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ (g(N))当且仅当f(N)=O(g(N))且 f(N)= Ω (g(N))。此时称f(N)与g(N)同阶。 o的定义：对于任意给定的ε＞0，都存在正整数N0，使得 当NN0时有f(N)/Cg(N)ε,则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N))。 例如，4NlogN+7=o(3N2+4NlogN+7)。
调试：“调试只能指出有错误，而不能指出它们不存在 错误” 9 作时空分布图：验证分析结论，优化算法设计

算法的设计(第7章回溯和分支限界)

算法的设计(第7章回溯和分支限界)

未来发展趋势及挑战
算法优化与创新
随着问题规模的增大和复杂性的提高，对算法性能的要求也越来越高。未来，回溯和分支 限界算法的优化和创新将成为研究的重要方向，包括设计更高效的剪枝策略、改进限界函 数等。
人工智能与算法设计的融合
人工智能技术的快速发展为算法设计提供了新的思路和方法。未来，将人工智能技术应用 于回溯和分支限界算法的设计中，实现自动化或半自动化的算法设计和优化，将是一个具 有挑战性的研究方向。
旅行商问题（TSP）。该问题是一个典 型的分支限界法应用案例，通过估计 旅行路线的最小和最大长度，可以缩 小搜索范围，并提高求解效率。回溯 法也可以求解TSP问题，但通常需要结 合其他优化技术来提高效率。
案例三
图的着色问题。该问题既可以通过回 溯法求解，也可以通过分支限界法求 解。回溯法通过搜索所有可能的着色 方案，并判断每种方案是否满足条件 ；而分支限界法则可以通过估计着色 的最小和最大颜色数来缩小搜索范围 。在实际应用中，可以根据问题的具 体特点和要求选择合适的算法。
利用问题领域的启发式信息来指导搜索过程，通过评估当前状态的优劣来决定是否继续 搜索该分支。启发式剪枝能够显著减少搜索空间，提高算法效率。
04 分支限界法详解
队列式分支限界法原理及实现
• 原理：队列式分支限界法是一种广度优先搜索策略，通过维 护一个队列来存储待处理的节点。在搜索过程中，不断从队 列中取出节点进行处理，并将产生的子节点加入队列，直到 找到目标节点或队列为空。
特点
回溯算法通常采用深度优先搜索策略 ，在搜索过程中，当发现当前路径无 法满足问题要求时，会及时“回溯” 到上一步，尝试其他可能的路径。
适用场景及问题类型
适用场景
回溯算法适用于求解组合优化问题， 如排列组合、图的着色、旅行商问题 等。

算法设计与分析-王-第1章-算法设计基础

算法设计与分析-王-第1章-算法设计基础

2）有没有已经解决了的类似问题可供借鉴？
1.4 算法设计的一般过程
在模型建立好了以后，应该依据所选定的模型对问 题重新陈述,并考虑下列问题: (1)模型是否清楚地表达了与问题有关的所有重要
的信息?
(2)模型中是否存在与要求的结果相关的数学量? (3)模型是否正确反映了输入、输出的关系? (4)对这个模型处理起来困难吗？
程序设计研究的四个层次：
算法→方法学→语言→工具
理由2：提高分析问题的能力
算法的形式化→思维的逻辑性、条理性
1.2 算法及其重要特性
一、算法以及算法与程序的区别
例：欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数
m n
欧几里德算法
r
1.2 算法及其重要特性
欧几里德算法
① 输入m 和nห้องสมุดไป่ตู้如果m<n,则m、n互换；
对不合法的输入能作出相适应的反映并进行处理。 （2） 健壮性（robustness）: 算法对非法输入的抵抗能力， 即对于错误的输入，算法应能识别并做出处理，而不是 产生错误动作或陷入瘫痪。 （3）可读性：算法容易理解和实现，它有助于人们对算 法的理解、调试和修改。 （4） 时间效率高：运行时间短。 （5） 空间效率高：占用的存储空间尽量少。
算法设计与分析
Design and Analysis of Computer Algorithms
高曙
教材：

算法设计与分析（第二版），清华大学出版社，王红梅， 胡明 编著
参考书目：

Introduction to Algorithms, Third Edition， Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest，机械工 业出版社，2012

算法设计与分析第二版课后习题及解答（可编辑）

算法设计与分析第二版课后习题及解答（可编辑）

算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法,n是任意正整数。

除了赋值和比较运算,该算法只能用到基本的四则运算操作。

算法求 //输入:一个正整数n2//输出:。

step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。

b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。

a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。

6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。

数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。

故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.古老的七桥问题第2章习题2.17.对下列断言进行证明:如果是错误的,请举例a. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。

算法设计与分析王红梅第二版动态规划详解演示文稿

算法设计与分析王红梅第二版动态规划详解演示文稿

2022/3/2
Chapter 6 Dynamic Programming
26
第26页，共110页。
多段图的最短路径问题
多段图的决策过程：
多段图的边(u, v)，用cuv 表边的权值，从源点s到终点t的最短路 径记为d(s, t)，则从源点0到终点9的最短路径d(0, 9)由下式确定 ：
d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}
2022/3/2
Chapter 6 Dynamic Programming
10
第10页，共110页。
动态规划法的设计思想
动态规划法的求解过程 原问题
子问题1
子问题2 ……
子问题n
2022/3/2
填表 原问题的解
Chapter 6 Dynamic Programming
11
第11页，共110页。
动态规划法的设计思想
Page 15
第6章 动态规划法
2022/3/2
第15页，共110页。
数塔问题——想法
[想法]从顶层出 发下一层选择 取决于两个4层 数塔的最大数 值和。
8 12 15 3 96 8 10 5 12 16 4 18 10 9
Page 16
第6章 动态规划法
2022/3/2
第16页，共110页。
数塔问题——想法
求解初始子问题：底层的每个数字可看作1层数塔，则最大数值和就是其自身； 再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4 个2层数塔，对每个数塔进行求解； 再求解下一阶段的子问题：第3层的决策是在第4层决策的基础上进行求解，可以看作3个 2层的数塔，对每个数塔进行求解；

《算法设计与分析》第07讲精品PPT课件

《算法设计与分析》第07讲精品PPT课件
上海海洋大学信息学院2009-12-2
不同的活结点表形成不同的分枝限界法，分为： FIFO分枝限界法、LIFO分枝限界法和LC（least cost）分枝限界法。三种不同的活结点表，规定了 从活结点表中选取下一个E-结点的不同次序。
FIFO分枝限界法的活结点表是先进先出队列 LIFO分枝限界法的活结点表是堆栈； LC分枝限界法的活结点表是优先权队列，LC分 枝限界法将选取具有最高优先级的活结点出队列， 成为新的E-结点。
2
3 5 2 4
19 6
18
3
16 4 7 16
10 20 0 13 14 2 1 3 0 16 3 15 12 0 3 12
1 10
0
2
2 2
0
3
4
上海海洋大学信息学院2009-12-2
归约列
10 20 0 13 14 2 1 3 0 16 3 15 12 0 3 12
iJ,i 1..n iJ,im i m1,...,n
ĉ(X) c(X) u(X)
上海海洋大学信息学院2009-12-2
可变大小元组状态空间树
上海海洋大学信息学院2009-12-2
7. 3 货郎担问题的分支限界法
上海海洋大学信息学院2009-12-2
问题描述
旅行商问题（travelling salesperson）是一个看似 简单其实十分难解的著名难题之一，至今仍有许多 人在研究它。此问题描述为：一个旅行商准备到n 个村庄售货。他从A村出发经过其它n-1个村庄，又 回到出发地A村。现要求一条最短路径，使得每个 村庄都经过且仅经过一次。
收益之和，使得总收益最大的作业子集是问题的最
优解。如果希望以最小值为最优解，则可以适当改

算法设计与分析：第7章 分支限界算法

算法设计与分析：第7章 分支限界算法

7.3.1 0/1背包问题
问题描述
• ! "$ &# $%&"# &%& # %'
– $ – $ &
%$ &!
$ "# (
算法思想
• !!3 '$6;
• 2)&!";+0#
&&E) *
.2D,<
最小代价(LC)分支限界法
代价函数!(·)
• % "!(%) %
• % "! %( % )
– %
• !(%) = ∞#
– %
• ! % =
相对代价估计函数"!($)
• "!(')((')&! • & '
• '$% &' • "!(')" *
)' )#"!(*) ≤ "!(') (
代价估计函数"!($)
• "!(') "! ' = ) ' + ,+(')
//X进队列
if(x是一个答案结点&&cost(x)<U)
//X为答案结点时修正U
if(u(x)+e < cost(x)) U=u(x)+e ;
else{ U=cost(x); ans=x;} else if(u(x)+e < U) U=u(x)+e ; //X为非答案结点时修正U
}
E.@56
_ N8!O/4/\/2i"1#9)K<iK<'- 4i ?I 40iFMZ>I 40+(104)]6=76i"/2)%PT\/3i"1#19)K<i 6iK<'- ?IY 0iFMZ>I 10]6=60i"/3)%PT\

《算法设计与分析》第07章

《算法设计与分析》第07章

南京邮电大学计算机学院 2008年3月
for (int r=2; r<=n;r++) for (int i=0;i<=n-r;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;k<j;k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]; if (t<m[i][j]) { m[i][j]=t;s[i][j]=k; } } } return m[0][n-1];
南京邮电大学计算机学院 2008年3月
for (int j=n-2;j>=0;j--){ float min=INFTY; for (ENode<T> *r=a[j];r;r=r->nextArc) { int v=r->adjVex; if (r->w+cost[v]<min) { min=r->w+cost[v];q=v; } } cost[j]=min;d[j]=q; } p[0]=0;p[k-1]=n-1; for(j=1;j<=k-2;j++) p[j]=d[p[j-1]]; delete []cost;delete []d; }
南京邮电大学计算机学院 2008年3月
7.3.3 矩阵连乘算法
【程序7－3】矩阵连乘算法 class MatrixChain { public: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback(); ……

算法设计与分析第7章作业.pdf

算法设计与分析第7章作业.pdf

「算法设计与分析」第7章作业2015.10学号: 15S103172 姓名: 谢浩哲1.在下图中考虑哈密顿环问题. 将问题的解空间表示成树, 并分别利用深度优先搜索和广度优先搜索判定该图中是否存在哈密顿环.问题解空间的树状结构:算法概述:从起始点出发, 搜索从这个点出发所有可到达的点(深度优先或广度优先策略均可). 对于每到达一个点, 判断: 是否已经回到起始点, 是否经过重复的点. 若经过了重复了点, 则不再搜索. 若到达了起始点, 并且恰好经过了所有的点, 则找到了最优解.算法实现:深度优先搜索:35}广度优先搜索:!isVisited(startPoint, i,372.考虑8-魔方问题. 分别用深度优先算法, 广度优先算法, 爬山法, 最佳优先方法判定上图所示的初始格局能够通过一系列操作转换成目标格局, 将搜索过程的主要步骤书写清楚.问题的部分解空间树状结构:深度优先搜索:搜索顺序为1 -> 2 -> 4 -> 10 -> …广度优先搜索:搜索顺序为1 -> 2 -> 3-> 4 -> 5 -> 6 -> …爬山法:基于深度优先搜索, 选取当前分支上最优解;搜索顺序为1 -> 2 -> 4 -> 11 -> …最佳优先方法:基于深度优先搜索, 选取所有分支上最优解;搜索顺序为1 -> 2 -> 4 -> 11 -> …3.分别使用深度优先法和分支限界法求解子集和问题的如下实例.输入: 集合S=7, 4, 6, 13, 20, 8和整数K=18.输出: S’使得S’中元素之和等于K.深度优先搜索:问题的部分解空间如下如所示:算法实现:分枝限界法可以在深度优先搜索时进行必要的剪枝, 例如对于分支7-4. 此时的分支上的和为11, 因此该分支上的数最大不可能超过18 - 11 = 7. 因此可见, 在深度优先搜索中搜索的13和8这两个分支其实可以进行剪枝. 其他分支亦然.算法实现:只需将以上代码的17行替换为:if ( !isSelected[i] &&4.将任意一整数n划分为若干整数之和的划分, 并按照降序的序列输出出来, 例如5的划分为: 5, 4+1,3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.问题解空间的树状图:算法实现(深度优先搜索):import java.util.ArrayList;public List<List<Integer>> getSplit(int n,1725 List<Integer> newSplit =new ArrayList<Integer>(currentSplit);5.在一个一维空间上有n个点1, 2, 3, 4, …, n, 有一个粒子它初始位置为1, 粒子从初始位置1开始做随机运动, 方向只有左右两个, 每次运动结束该粒子就会移动到相邻的位置上. 已知该粒子在i(1<i<n)点位置上向左运动的概率为p i, 该粒子在1点只能向右运动, 在n点只能向左运动, 那么请问该粒子在t次运动后它最有可能出现在哪个点上, 以及输出该粒子向右运行距离的期望值.对于n=5的问题解空间的树状图:算法实现(广度优先搜索):15public Queue<Point> getFinalPositions(25q.offer(new Point(cp.coordinate + 1,31 q.offer(new Point(cp.coordinate - 1,cp.probability * p[cp.coordinate]));。

算法设计与分析(第2版)-王红 梅-胡明-习题答案

算法设计与分析(第2版)-王红 梅-胡明-习题答案
}//while return r;
}
7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？ 任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为 这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自 然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界， 暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数
(1) Ω(n) 紧密？ (2) Ω(n*n) (3) Ω(logn+n)（先进行快排，然后进行比较查找） (4) Ω(2^n)
7．画出在三个数a, b, c中求中值问题的判定树。
a<b a<b<c
是
是 是 否 否 否 a<c b<c
b<a<c b<c
C<b<a b<c<a a<c C<a<b
a<c<b
return 0； }
double arctan(double x) { int i=0; double r=0,e,f,sqr;//定义四个变量初 sqr = x*x; e = x; while (e/i>1e-15)//定义精度范围 {
f = e/i;//f是每次r需要叠加的方程 r = (i%4==1)?r+f:r-f; e = e*sqr;//e每次乘于x的平方 i+=2;//i每次加2
cout<<"n至少为:"<<n<<endl; break; } }//for return 0; }
6. 计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求 的π值
#include <iostream> using namespace std;

算法设计与分析(第2版) 王红梅 胡明 习题参考答案

算法设计与分析(第2版) 王红梅 胡明 习题参考答案
#include<iostream>
usingnamespacestd;
intmain()
{
longdoubleresult=1;
doublej=1;
for(inti=1;i<=64;++i)
{
j=j*2;
result+=j;
j++;
}
cout<<result<<endl;
return0;
}
习题3
1．假设在文本"ababcabccabccacbab"中查找模式"abccac"，写出分别采用BF算法和KMP算法的串匹配过
else
value=a[i+2]-a[i+1];
}
cout<<value<<endl;
return0;
}
4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。
#include<iostream>
usingnamespacestd;
{
if(n==1)
return4;
elseif(n>1)
return3*T(n-1);
}
(2)
intT(intn)
{
if(n==1)
return1;
elseif(n>1)
return2*T(n/3)+n;
}
5.求下列问题的平凡下界，并指出其下界是否紧密。
（1）求数组中的最大元素；
（2）判断邻接矩阵表示的无向图是不是完全图；

算法设计与分析 王红梅 第二版 第7章_贪心算法

算法设计与分析 王红梅 第二版 第7章_贪心算法

2015/11/4
Chapter 7 Greedy Method
3
第7章 贪心算法


贪心法把一个复杂问题的解分解为一系列较为简单 的局部最优选择，每一步选择都是对当前解的一个 扩展，直到获得问题的完整解。 贪心法的典型应用是求解最优化问题，而且对许多 问题都能得到整体最优解，即使不能得到整体最优 解，通常也是最优解的很好近似。
2015/11/4
Chapter 7 Greedy Method
22
7.2.1 TSP问题
设图G 有 n 个顶点， w[n][n] 存储边上的代价，集合 E‘存储是候选集合中未选取的边，集合 P 存储经过的边，最 短链接策略求解 TSP 问题的算法如下：
算法7.3——最短链接策略求解TSP问题 1．P={ }; 2．E'=E; //候选集合，初始时为图中所有边 3．循环直到集合P中包含n-1条边 3.1 在E'中选取最短边(u, v); 3.2 E'=E'-{(u, v)}; 3.3 如果 (顶点 u 和v 在 P 中不连通 and 不产生分枝) 则P=P+{(u, v)};
由于
A/B-1/E=((A*E)-B)/(B*E)
这个分数可能存在公因子，所以需要化简，可将分子和分母同 时除以最大公约数。
2015/11/4 Chapter 7 Greedy Method 11
7.1.2 一个简单的例子——埃及分数

[算法]伪代码描述如下： 算法7.1：埃及分数EgyptFraction 输入：真分数的分子A和分母B 输出：最少的埃及分数之和 1. E＝B/A+1; //E＝C+1 2. 输出1/E; 3. A=A*E-B; B=B*E; 4. 求A和B的最大公约数R，如果R不为1，将A和B同时除以R 5. 如果A等于1，则输出1/B，算法结束；否则转步骤1

算法设计与分析习题解答(第2版)

算法设计与分析习题解答(第2版)

第1章算法引论11.1 算法与程序11.2 表达算法的抽象机制11.3 描述算法31.4 算法复杂性分析13小结16习题17第2章递归与分治策略192.1 递归的概念192.2 分治法的基本思想262.3 二分搜索技术272.4 大整数的乘法282.5 Strassen矩阵乘法302.6 棋盘覆盖322.7 合并排序342.8 快速排序372.9 线性时间选择392.10 最接近点对问题432.11 循环赛日程表53小结54习题54第3章动态规划613.1 矩阵连乘问题62目录算法设计与分析(第2版)3.2 动态规划算法的基本要素67 3.3 最长公共子序列713.4 凸多边形最优三角剖分753.5 多边形游戏793.6 图像压缩823.7 电路布线853.8 流水作业调度883.9 0-1背包问题923.10 最优二叉搜索树98小结101习题102第4章贪心算法1074.1 活动安排问题1074.2 贪心算法的基本要素1104.2.1 贪心选择性质1114.2.2 最优子结构性质1114.2.3 贪心算法与动态规划算法的差异1114.3 最优装载1144.4 哈夫曼编码1164.4.1 前缀码1174.4.2 构造哈夫曼编码1174.4.3 哈夫曼算法的正确性1194.5 单源最短路径1214.5.1 算法基本思想1214.5.2 算法的正确性和计算复杂性123 4.6 最小生成树1254.6.1 最小生成树性质1254.6.2 Prim算法1264.6.3 Kruskal算法1284.7 多机调度问题1304.8 贪心算法的理论基础1334.8.1 拟阵1334.8.2 带权拟阵的贪心算法1344.8.3 任务时间表问题137小结141习题141第5章回溯法1465.1 回溯法的算法框架1465.1.1 问题的解空间1465.1.2 回溯法的基本思想1475.1.3 递归回溯1495.1.4 迭代回溯1505.1.5 子集树与排列树1515.2 装载问题1525.3 批处理作业调度1605.4 符号三角形问题1625.5 n后问题1655.6 0\|1背包问题1685.7 最大团问题1715.8 图的m着色问题1745.9 旅行售货员问题1775.10 圆排列问题1795.11 电路板排列问题1815.12 连续邮资问题1855.13 回溯法的效率分析187小结190习题191第6章分支限界法1956.1 分支限界法的基本思想1956.2 单源最短路径问题1986.3 装载问题2026.4 布线问题2116.5 0\|1背包问题2166.6 最大团问题2226.7 旅行售货员问题2256.8 电路板排列问题2296.9 批处理作业调度232小结237习题238第7章概率算法2407.1 随机数2417.2 数值概率算法2447.2.1 用随机投点法计算π值2447.2.2 计算定积分2457.2.3 解非线性方程组2477.3 舍伍德算法2507.3.1 线性时间选择算法2507.3.2 跳跃表2527.4 拉斯维加斯算法2597.4.1 n 后问题2607.4.2 整数因子分解2647.5 蒙特卡罗算法2667.5.1 蒙特卡罗算法的基本思想2667.5.2 主元素问题2687.5.3 素数测试270小结273习题273第8章 NP完全性理论2788.1 计算模型2798.1.1 随机存取机RAM2798.1.2 随机存取存储程序机RASP2878.1.3 RAM模型的变形与简化2918.1.4 图灵机2958.1.5 图灵机模型与RAM模型的关系297 8.1.6 问题变换与计算复杂性归约299 8.2 P类与NP类问题3018.2.1 非确定性图灵机3018.2.2 P类与NP类语言3028.2.3 多项式时间验证3048.3 NP完全问题3058.3.1 多项式时间变换3058.3.2 Cook定理3078.4 一些典型的NP完全问题3108.4.1 合取范式的可满足性问题3118.4.2 3元合取范式的可满足性问题312 8.4.3 团问题3138.4.4 顶点覆盖问题3148.4.5 子集和问题3158.4.6 哈密顿回路问题3178.4.7 旅行售货员问题322小结323习题323第9章近似算法3269.1 近似算法的性能3279.2 顶点覆盖问题的近似算法3289.3 旅行售货员问题近似算法3299.3.1 具有三角不等式性质的旅行售货员问题330 9.3.2 一般的旅行售货员问题3319.4 集合覆盖问题的近似算法3339.5 子集和问题的近似算法3369.5.1 子集和问题的指数时间算法3369.5.2 子集和问题的完全多项式时间近似格式337 小结340习题340第10章算法优化策略34510.1 算法设计策略的比较与选择34510.1.1 最大子段和问题的简单算法34510.1.2 最大子段和问题的分治算法34610.1.3 最大子段和问题的动态规划算法34810.1.4 最大子段和问题与动态规划算法的推广349 10.2 动态规划加速原理35210.2.1 货物储运问题35210.2.2 算法及其优化35310.3 问题的算法特征35710.3.1 贪心策略35710.3.2 对贪心策略的改进35710.3.3 算法三部曲35910.3.4 算法实现36010.3.5 算法复杂性36610.4 优化数据结构36610.4.1 带权区间最短路问题36610.4.2 算法设计思想36710.4.3 算法实现方案36910.4.4 并查集37310.4.5 可并优先队列37610.5 优化搜索策略380小结388习题388第11章在线算法设计39111.1 在线算法设计的基本概念39111.2 页调度问题39311.3 势函数分析39511.4 k 服务问题39711.4.1 竞争比的下界39711.4.2 平衡算法39911.4.3 对称移动算法39911.5 Steiner树问题40311.6 在线任务调度40511.7 负载平衡406小结407习题407词汇索引409参考文献415习题1-1 实参交换1习题1-2 方法头签名1习题1-3 数组排序判定1习题1-4 函数的渐近表达式2习题1-5 O(1) 和 O(2) 的区别2习题1-7 按渐近阶排列表达式2习题1-8 算法效率2习题1-9 硬件效率3习题1-10 函数渐近阶3习题1-11 n !的阶4习题1-12 平均情况下的计算时间复杂性4算法实现题1-1 统计数字问题4算法实现题1-2 字典序问题5算法实现题1-3 最多约数问题6算法实现题1-4 金币阵列问题8算法实现题1-5 最大间隙问题11第2章递归与分治策略14 习题2-1 Hanoi 塔问题的非递归算法14习题2-2 7个二分搜索算法15习题2-3 改写二分搜索算法18习题2-4 大整数乘法的 O(nm log(3/2))算法19习题2-5 5次 n /3位整数的乘法19习题2-6 矩阵乘法21习题2-7 多项式乘积21习题2-8 不动点问题的 O( log n) 时间算法22习题2-9 主元素问题的线性时间算法22习题2-10 无序集主元素问题的线性时间算法22习题2-11 O (1)空间子数组换位算法23习题2-12 O (1)空间合并算法25习题2-13 n 段合并排序算法32习题2-14 自然合并排序算法32习题2-15 最大值和最小值问题的最优算法35习题2-16 最大值和次大值问题的最优算法35习题2-17 整数集合排序35习题2-18 第 k 小元素问题的计算时间下界36习题2-19 非增序快速排序算法37习题2-20 随机化算法37习题2-21 随机化快速排序算法38习题2-22 随机排列算法38习题2-23 算法qSort中的尾递归38习题2-24 用栈模拟递归38习题2-25 算法select中的元素划分39习题2-26 O(n log n) 时间快速排序算法40习题2-27 最接近中位数的 k 个数40习题2-28 X和Y 的中位数40习题2-29 网络开关设计41习题2-32 带权中位数问题42习题2-34 构造Gray码的分治算法43习题2-35 网球循环赛日程表44目录算法设计与分析习题解答（第2版）算法实现题2-1 输油管道问题（习题2-30) 49算法实现题2-2 众数问题（习题2-31) 50算法实现题2-3 邮局选址问题（习题2-32) 51算法实现题2-4 马的Hamilton周游路线问题（习题2-33) 51算法实现题2-5 半数集问题60算法实现题2-6 半数单集问题62算法实现题2-7 士兵站队问题63算法实现题2-8 有重复元素的排列问题63算法实现题2-9 排列的字典序问题65算法实现题2-10 集合划分问题（一）67算法实现题2-11 集合划分问题（二）68算法实现题2-12 双色Hanoi塔问题69算法实现题2-13 标准二维表问题71算法实现题2-14 整数因子分解问题72算法实现题2-15 有向直线2中值问题72第3章动态规划76习题3-1 最长单调递增子序列76习题3-2 最长单调递增子序列的 O(n log n) 算法77习题3-7 漂亮打印78习题3-11 整数线性规划问题79习题3-12 二维背包问题80习题3-14 Ackermann函数81习题3-17 最短行驶路线83习题3-19 最优旅行路线83算法实现题3-1 独立任务最优调度问题（习题3-3) 83算法实现题3-2 最少硬币问题（习题3-4) 85算法实现题3-3 序关系计数问题（习题3-5) 86算法实现题3-4 多重幂计数问题（习题3-6) 87算法实现题3-5 编辑距离问题（习题3-8) 87算法实现题3-6 石子合并问题（习题3-9) 89算法实现题3-7 数字三角形问题（习题3-10) 91算法实现题3-8 乘法表问题（习题3-13) 92算法实现题3-9 租用游艇问题（习题3-15) 93算法实现题3-10 汽车加油行驶问题（习题3-16) 95算法实现题3-11 圈乘运算问题（习题3-18) 96算法实现题3-12 最少费用购物（习题3-20) 102算法实现题3-13 最大长方体问题（习题3-21) 104算法实现题3-14 正则表达式匹配问题（习题3-22) 105算法实现题3-15 双调旅行售货员问题（习题3-23) 110算法实现题3-16 最大 k 乘积问题（习题5-24) 111算法实现题3-17 最小 m 段和问题113算法实现题3-18 红黑树的红色内结点问题115第4章贪心算法123 习题4-2 活动安排问题的贪心选择123习题4-3 背包问题的贪心选择性质123习题4-4 特殊的0-1背包问题124习题4-10 程序最优存储问题124习题4-13 最优装载问题的贪心算法125习题4-18 Fibonacci序列的Huffman编码125习题4-19 最优前缀码的编码序列125习题4-21 任务集独立性问题126习题4-22 矩阵拟阵126习题4-23 最小权最大独立子集拟阵126习题4-27 整数边权Prim算法126习题4-28 最大权最小生成树127习题4-29 最短路径的负边权127习题4-30 整数边权Dijkstra算法127算法实现题4-1 会场安排问题（习题4-1) 128算法实现题4-2 最优合并问题（习题4-5) 129算法实现题4-3 磁带最优存储问题（习题4-6) 130算法实现题4-4 磁盘文件最优存储问题（习题4-7) 131算法实现题4-5 程序存储问题（习题4-8) 132算法实现题4-6 最优服务次序问题（习题4-11) 133算法实现题4-7 多处最优服务次序问题（习题4-12) 134算法实现题4-8 d 森林问题（习题4-14) 135算法实现题4-9 汽车加油问题（习题4-16) 137算法实现题4-10 区间覆盖问题（习题4-17) 138算法实现题4-11 硬币找钱问题（习题4-24) 138算法实现题4-12 删数问题（习题4-25) 139算法实现题4-13 数列极差问题（习题4-26) 140算法实现题4-14 嵌套箱问题（习题4-31) 140算法实现题4-15 套汇问题（习题4-32) 142算法实现题4-16 信号增强装置问题（习题5-17) 143算法实现题4-17 磁带最大利用率问题（习题4-9) 144算法实现题4-18 非单位时间任务安排问题（习题4-15) 145算法实现题4-19 多元Huffman编码问题（习题4-20) 147算法实现题4-20 多元Huffman编码变形149算法实现题4-21 区间相交问题151算法实现题4-22 任务时间表问题151第5章回溯法153习题5\|1 装载问题改进回溯法（一）153习题5\|2 装载问题改进回溯法（二）154习题5\|4 0-1背包问题的最优解155习题5\|5 最大团问题的迭代回溯法156习题5\|7 旅行售货员问题的费用上界157习题5\|8 旅行售货员问题的上界函数158算法实现题5-1 子集和问题（习题5-3) 159算法实现题5-2 最小长度电路板排列问题（习题5-9) 160算法实现题5-3 最小重量机器设计问题（习题5-10) 163算法实现题5-4 运动员最佳匹配问题（习题5-11) 164算法实现题5-5 无分隔符字典问题（习题5-12) 165算法实现题5-6 无和集问题（习题5-13) 167算法实现题5-7 n 色方柱问题（习题5-14) 168算法实现题5-8 整数变换问题（习题5-15) 173算法实现题5-9 拉丁矩阵问题（习题5-16) 175算法实现题5-10 排列宝石问题（习题5-16) 176算法实现题5-11 重复拉丁矩阵问题（习题5-16) 179算法实现题5-12 罗密欧与朱丽叶的迷宫问题181算法实现题5-13 工作分配问题（习题5-18) 183算法实现题5-14 独立钻石跳棋问题（习题5-19) 184算法实现题5-15 智力拼图问题（习题5-20) 191算法实现题5-16 布线问题（习题5-21) 198算法实现题5-17 最佳调度问题（习题5-22) 200算法实现题5-18 无优先级运算问题（习题5-23) 201算法实现题5-19 世界名画陈列馆问题（习题5-25) 203算法实现题5-20 世界名画陈列馆问题（不重复监视）（习题5-26) 207 算法实现题5-21 部落卫队问题（习题5-6) 209算法实现题5-22 虫蚀算式问题211算法实现题5-23 完备环序列问题214算法实现题5-24 离散01串问题217算法实现题5-25 喷漆机器人问题218算法实现题5-26 n 2-1谜问题221第6章分支限界法229习题6-1 0-1背包问题的栈式分支限界法229习题6-2 用最大堆存储活结点的优先队列式分支限界法231习题6-3 团顶点数的上界234习题6-4 团顶点数改进的上界235习题6-5 修改解旅行售货员问题的分支限界法235习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树237 习题6-7 电路板排列问题的队列式分支限界法239算法实现题6-1 最小长度电路板排列问题一（习题6-8) 241算法实现题6-2 最小长度电路板排列问题二（习题6-9) 244算法实现题6-3 最小权顶点覆盖问题（习题6-10) 247算法实现题6-4 无向图的最大割问题（习题6-11) 250算法实现题6-5 最小重量机器设计问题（习题6-12) 253算法实现题6-6 运动员最佳匹配问题（习题6-13) 256算法实现题6-7 n 后问题（习题6-15) 259算法实现题6-8 圆排列问题（习题6-16) 260算法实现题6-9 布线问题（习题6-17) 263算法实现题6-10 最佳调度问题（习题6-18) 265算法实现题6-11 无优先级运算问题（习题6-19) 268算法实现题6-12 世界名画陈列馆问题（习题6-21) 271算法实现题6-13 骑士征途问题274算法实现题6-14 推箱子问题275算法实现题6-15 图形变换问题281算法实现题6-16 行列变换问题284算法实现题6-17 重排 n 2宫问题285算法实现题6-18 最长距离问题290第7章概率算法296习题7-1 模拟正态分布随机变量296习题7-2 随机抽样算法297习题7-3 随机产生 m 个整数297习题7-4 集合大小的概率算法298习题7-5 生日问题299习题7-6 易验证问题的拉斯维加斯算法300习题7-7 用数组模拟有序链表300习题7-8 O(n 3/2)舍伍德型排序算法300习题7-9 n 后问题解的存在性301习题7-11 整数因子分解算法302习题7-12 非蒙特卡罗算法的例子302习题7-13 重复3次的蒙特卡罗算法303习题7-14 集合随机元素算法304习题7-15 由蒙特卡罗算法构造拉斯维加斯算法305习题7-16 产生素数算法306习题7-18 矩阵方程问题306算法实现题7-1 模平方根问题（习题7-10) 307算法实现题7-2 集合相等问题（习题7-17) 309算法实现题7-3 逆矩阵问题（习题7-19) 309算法实现题7-4 多项式乘积问题（习题7-20) 310算法实现题7-5 皇后控制问题311算法实现题7-6 3-SAT问题314算法实现题7-7 战车问题315算法实现题7-8 圆排列问题317算法实现题7-9 骑士控制问题319算法实现题7-10 骑士对攻问题320第8章NP完全性理论322 习题8-1 RAM和RASP程序322习题8-2 RAM和RASP程序的复杂性322习题8-3 计算 n n 的RAM程序322习题8-4 没有MULT和DIV指令的RAM程序324习题8-5 MULT和DIV指令的计算能力324习题8-6 RAM和RASP的空间复杂性325习题8-7 行列式的直线式程序325习题8-8 求和的3带图灵机325习题8-9 模拟RAM指令325习题8-10 计算2 2 n 的RAM程序325习题8-11 计算 g(m,n)的程序 326习题8-12 图灵机模拟RAM的时间上界326习题8-13 图的同构问题326习题8-14 哈密顿回路327习题8-15 P类语言的封闭性327习题8-16 NP类语言的封闭性328习题8-17 语言的2 O (n k) 时间判定算法328习题8-18 P CO -NP329习题8-19 NP≠CO -NP329习题8-20 重言布尔表达式329习题8-21 关系∝ p的传递性329习题8-22 L ∝ p 330习题8-23 语言的完全性330习题8-24 的CO-NP完全性330习题8-25 判定重言式的CO-NP完全性331习题8-26 析取范式的可满足性331习题8-27 2-SAT问题的线性时间算法331习题8-28 整数规划问题332习题8-29 划分问题333习题8-30 最长简单回路问题334第9章近似算法336习题9-1 平面图着色问题的绝对近似算法336习题9-2 最优程序存储问题336习题9-4 树的最优顶点覆盖337习题9-5 顶点覆盖算法的性能比339习题9-6 团的常数性能比近似算法339习题9-9 售货员问题的常数性能比近似算法340习题9-10 瓶颈旅行售货员问题340习题9-11 最优旅行售货员回路不自相交342习题9-14 集合覆盖问题的实例342习题9-16 多机调度问题的近似算法343习题9-17 LPT算法的最坏情况实例345习题9-18 多机调度问题的多项式时间近似算法345算法实现题9-1 旅行售货员问题的近似算法（习题9-9) 346 算法实现题9-2 可满足问题的近似算法（习题9-20) 348算法实现题9-3 最大可满足问题的近似算法（习题9-21) 349 算法实现题9-4 子集和问题的近似算法（习题9-15) 351算法实现题9-5 子集和问题的完全多项式时间近似算法352算法实现题9-6 实现算法greedySetCover（习题9-13) 352算法实现题9-7 装箱问题的近似算法First Fit（习题9-19) 356算法实现题9-8 装箱问题的近似算法Best Fit（习题9-19) 358算法实现题9-9 装箱问题的近似算法First Fit Decreasing（习题9-19) 360算法实现题9-10 装箱问题的近似算法Best Fit Decreasing（习题9-19) 361算法实现题9-11 装箱问题的近似算法Next Fit361第10章算法优化策略365 习题10-1 算法obst的正确性365习题10-2 矩阵连乘问题的 O(n 2) 时间算法365习题10-6 货物储运问题的费用371习题10-7 Garsia算法371算法实现题10-1 货物储运问题（习题10-3) 374算法实现题10-2 石子合并问题（习题10-4) 374算法实现题10-3 最大运输费用货物储运问题（习题10-5) 375算法实现题10-4 五边形问题377算法实现题10-5 区间图最短路问题（习题10-8) 381算法实现题10-6 圆弧区间最短路问题（习题10-9) 381算法实现题10-7 双机调度问题（习题10-10) 382算法实现题10-8 离线最小值问题（习题10-11) 390算法实现题10-9 最近公共祖先问题（习题10-12) 393算法实现题10-10 达尔文芯片问题395算法实现题10-11 多柱Hanoi塔问题397算法实现题10-12 线性时间Huffman算法400算法实现题10-13 单机调度问题402算法实现题10-14 最大费用单机调度问题405算法实现题10-15 飞机加油问题408第11章在线算法设计410习题11-1 在线算法LFU的竞争性410习题11-4 多读写头磁盘问题的在线算法410习题11-6 带权页调度问题410算法实现题11-1 最优页调度问题（习题11-2) 411算法实现题11-2 在线LRU页调度（习题11-3) 414算法实现题11-3 k 服务问题（习题11-5) 416参考文献422。

Eea_7_算法设计与分析

Eea_7_算法设计与分析
不同点：
1、求解方式不同： 动态规划法：自底向上； 贪心法：自顶向下；
2、对子问题的依赖不同： 动态规划法：依赖于各子问题的解，所以应使各子问题最 优，才能保证整体最优； 贪心法：依赖于过去所作过的选择，但决不依赖于将来的 选择，也不依赖于子问题的解。
具有最优子结构性质的问题有些只能用动态规划法，13 有些可用贪心法。
达汇点t的最短路径的长度。cost(i,j)则是这些路径中的最短路
径长度。
16
9
7 源点s 0 3
2
14 2
1 2
7
3 11
6
5
2
5
4
63 5
11
7 6
48
8 4 2
9 5
10
11 t汇点
阶段 v1
v2
v3
v4
v5
使用式（7-1）向前递推式，由后向前计算最优解值—cost(1,0)
cost(5,11)=0,
矛盾。
多段图的最优子结构性质得证！
15
多段图问题的递推式（向前递推）
由多段图问题的最优子结构性质，容易得到多段图问题的递推 式，从而由子问题的最优解来计算原问题的最优解：
多段图问题的向前递推式：（式7-1）
cos t(k,t) 0
cos t(i, j)
min
c( j, p) cos t(i 1, p)
19
(0, d(1,0)=2, d(2,2)=5, d(3,5)=9, d(4,9)=11)
程序7-1：多段图的向前递推动态规划算法
FMultiGraph(int k,int*p) //共k个阶段
{//带权有向图G （多段图）采用邻接表存储（见程序6-8）

第7章 贪心法-算法设计与分析(第2版)-李春葆-清华大学出版社

第7章 贪心法-算法设计与分析(第2版)-李春葆-清华大学出版社

{ SolutionType x={}；
//初始时，解向量不包含任何分量
for (int i=0;i<n;i++)
//执行n步操作
{ SType xi=Select(a);
//从输入a中选择一个当前最好的分量
if (Feasiable(xi))
//判断xi是否包含在当前解中
solution=Union(x,xi); //将xi分量合并形成x
} } }
//求解最大兼容活动子集 //初始化为false //A[1..n]按活动结束时间递增排序 //前一个兼容活动的结束时间 //扫描所有活动 //找到一个兼容活动 //选择A[i]活动 //更新preend值
【算法分析】算法的主要时间花费在排序上，排序时间为
O(nlog2n)，所以整个算法的时间复杂度为O(nlog2n)。
问题的最优子结构性质是该问题可用动态规划算法或贪心法求解 的关键特征。
7.1.3 贪心法的一般求解过程
贪心法求解问题的算法框架如下：
SolutionType Greedy(SType a[],int n)
//假设解向量(x0,x1,…,xn-1)类型为SolutionType，其分量为SType类型
//标记选择的活动 //选取的兼容活动个数
void solve() { memset(flag,0,sizeof(flag));
sort(A+1,A+n+1); int preend=0; for (int i=1;i<=n;i++) { if (A[i].b>=preend)
{ flag[i]=true; preend=A[i].e;

算法分析与设计 第二版 英文版 (潘彦 著) 清华大学出版社 课后答案--solu7

算法分析与设计 第二版 英文版 (潘彦 著) 清华大学出版社 课后答案--solu7
This file contains the exercises, hints, and solutions for Chapter 7 of the book ”Introduction to the Design and Analysis of Algorithms,” 2nd edition, by A. Levitin. The problems that might be challenging for at least some students are marked by ; those that might be difficult for a majority of students are marked by .
1
8. a. Write a program for multiplying two sparse matrices, a p-by-q matrix A and a q-by-r matrix B.
b. Write a program for multiplying two sparse polynomials p(x) and q(x) of degrees m and n, respectively.
tree’s vertices in constant time.
7. The following technique, known as virtual initialization, provides a
网 time-efficient way to initialize just some elements of a given array A[0..n −Fra 网 案 答 后 课2
Hints to Exercises 7.1
1. Yes, it is possible. How? 2. Check the algorithm’s pseudocode to see what it does upon encountering
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

图7-1 有向图示例
广度优先搜索直接实现了我们上述的过程。初始时，队 列Q中只含顶点s，即距离为0的顶点。对于后续距离d = 1， 2，3，…，在某时刻，队列Q中只包含距离为d的所有顶点。 随着这些顶点被处理(执行出队操作)，其尚未被访问的近邻 被插入到队尾。图7-2给出了访问图7-1中顶点时的当前队列， 其中a为起始点，顶点按照字母顺序排列。队列Q中字母上 方的数字表示起始点到该顶点的距离。而且图7-2右边的广 度优先搜索树包含了每个顶点最先被访问时所通过的那些边。 由此可得，从a开始的每条路径都是最短路径。因此，这棵 树称为最短路径树(shortest path tree)。
对于图7-1，以结点a作为源点s，将该图划分为若干层： s自身，与s距离为1的那些顶点作为一层，与s距离为2的那 些结点作为另一层，以此类推。一种简便的计算从s到其他 顶点的距离的方法是逐层进行计算。一旦计算出距离为0，1， 2，…，d的那些顶点，就很容易确定出距离为d+1的顶点。 这些顶点就是那些与距离为d的那层顶点相邻的尚未被访问 的顶点。这就给出一个在任一给定时刻只有两层是活跃的迭 代算法：在某层d，其中的顶点完全被访问过；在d+1层， 要通过扫描第d层顶点的近邻，来找出该层的顶点。
表7-1 应用领域与图模型
7.1 图 的 表 示
可以使用邻接矩阵来表示一个图。对于有n(= |V|)个顶点 的图，其邻接矩阵的第(i，j)个元素为
ai, j
1， vi到v j存在一条边 0， vi、v j 间无边
其中，vi(i = 1, …, n)为图中顶点。对于一个无向图，因为其 中的每条边{u，v}可从两个方向看待，因而该邻接矩阵是对 称的。这种表示的好处是可在常量时间内检查图中是否存在 某条边，只需要访问一次内存。而矩阵需要O(n2)的空间。 如果图中的边数不是很多，这种表示方式浪费空间。
第7章 图算法
7.1 图的表示 7.2 广度优先搜索 7.3 Dijkstra算法 7.4 Bellman-Ford算法 7.5 Floyd-Warshall算法 习题
许多应用问题可以归结为图模型上的问题。因而，我们 可以用图作为表示和求解问题的工具。例如，在航线图中， 图中的顶点可以表示机场，边可以表示飞行航线，边上的权 值则可能表示距离或费用。在电路图中，图中的顶点表示逻 辑门、寄存器、引脚或处理器，边表示接线，边上的权值可 能表示接线长度或传输延迟。在作业调度问题中，图中的顶 点表示作业，边表示优先关系，边上的权值可能表示优先级。 在金融问题中，图中的顶点表示股票或流通货币，边表示交 易或事务处理，边上的权值可能表示费用。表7-1列举了不 同应用领域在图模型中的意义。
BFS算法的执行过程如图7-3所示。
图7-3 BFS算法的执行过程
7.3 Dijkstra算法
给定加权有向图G = (V，E)，定义权函数w为边到其上 实值的映射w：E→R。路径p =〈v0，v1，…，vk〉上的权定 义为这条路径边上的权值之和，即
使用哪一种表示法，取决于顶点集|V|中顶点之间的关系、 图中的顶点数以及边数|E|。|E|的规模可与|V|相当或与|V|2相 当(所有边可能相连)。如果是前者，则称该图是稀疏的，否 则称该图是稠密的。我们将在后续的章节中看到，|E|与|V|之 间的这个关系将会成为我们选择合适图算法的主要因素。
7.2 广度优先搜索
图7-2 图7-1的广度优先队列Q及其广度优先搜索树
广度优先搜索算法如下所示。
前驱
BFS(G, s)
1
for each vertex v V[G] //初始化到顶点v的最短路径及
2 3 4 5 6 7 8 9 长度
do d[v]
[v] NIL
d[s] 0 Q
//初始化队列Q
ENQUEUE(Q, s)
图的另一种表示方法是邻接表表示法。这种方法只需要 与边数成正比的空间，由|V|个链表组成，每个顶点都有一个 链表。顶点u的链表存放由u出发所指向的顶点，也就是说， 存放(u，v)∈E的那些顶点v。因此，如果图为有向图，则每 条边只在一个链表中出现； 如果图为无向图，则每条边在 两个链表中出现。无论是哪种情况，数据结构的总规模为 O(|E|)。在这种情况下，检查某条边(u，v)不再为常量时间， 因为这个过程需要查找u的邻接表。但通过一个顶点的所有 近邻还是可以比较容易地完成这个过程。我们很快就可知， 这个过程证明是图算法中的一个很有用的操作。对于无向图， 这种表示是对称的，当且仅当u在v队列中存在顶点
do u DEQUEUE(Q) //摘取队列中最小元素
for each vertex v Adj[u] //更新顶点v的最短路径
10
do if d[v] =
11
then d[v] d[u] + 1
12
ENQUEUE(Q, v)
以下分析算法的运行时间。初始化后，第10行的测试保 证每个顶点至多入队一次，且至多出队一次。入队和出队操 作所需时间为常量时间O(1) O(V)。由于仅在顶点出队时才扫描该顶点的邻接表，因此， 每个邻接表至多被扫描一次。由于所有邻接表的长度之和为 Θ(E)，因此扫描邻接表所花费的总时间为O(E)。初始化的开 销为O(V)。因此，BFS的总运行时间为O(V+E)。由此可得， 广度优先搜索算法的运行时间为G的邻接表表示规模的线性 时间。
广度优先搜索(Breadth First Search，BFS)是图搜索中最 简单的算法之一，也是很多重要图算法的基础算法。 Dijkstra单源点最短路径算法就使用了与BFS类似的思想。 给定一个图G = (V，E)以及一个称为源点的特殊顶点s，BFS 系统地探索图G中的边，找出由s可达的那些顶点。BFS计算 出从s到每个可达顶点的距离(最少边数)。同时，还形成一 棵根为s的广度优先树，这棵树中包括了由s可达的所有顶点。 对于由s可达的任一顶点v，在这棵广度优先树中从s到v的路 径对应于图G中从s到v的一条最短路径，也就是说，包含了 边数最少的一条路径。BFS算法对于有向图和无向图均适用。