西华师范大学：《算法与程序设计》课程教学资源_第十章 算法设计

第10章算法设计 本章主要介绍下列内容(教材第二章) 1.回溯法 2.动态规划法 3.贪婪法 4.分而治之法 5.分支界限法 6.局部搜索法 课时分配:第1-5节每节讲授三个学时、上机三个学时,第6节根据时间多少而选讲 重点、难点:各节方法介绍、具体问题的算法设计思想 第一节回溯法 思路:见p4l 哪些问题可用回溯法解 迷宫问题详见《数据结构》C语言版p503.24或题集pl8 2.排列问题、组合问题、皇后问题、砝码问题。详见补充材料(师院学报理科版论文 几个典型问题的回溯算法)。 对于砝码问题,有简单的非回溯算法——一穷举砝码个数位二进制法,类似于最长有序 子序列的非动态规则法。 3.集和问题见cpl39 n个正数,找出满足条件的一切组合:每个组合中的数之和等于给定的某个正数M 算法类似于砝码问题。例子:M=30,W=(5,10,12,13,15,18) 解:51000150,50121300,00120018 4.性判定问题,cp141 5.哈密顿回路,cpl44 6.稳定婚姻问题,p32 7.马步问题,p41 、以排列组合或N后问题为例引入回溯思想 补充 马步问题 1.先演示41页5阶阵人工走法技巧 2.再演示下图(逆时针均匀转大圈法) 21491419 10152038 18|13 16

第 10 章 算法设计 本章主要介绍下列内容（教材第二章） 1. 回溯法 2. 动态规划法 3. 贪婪法 4. 分而治之法 5. 分支界限法 6. 局部搜索法 课时分配：第 1-5 节每节讲授三个学时、上机三个学时，第 6 节根据时间多少而选讲 重点、难点：各节方法介绍、具体问题的算法设计思想 第一节 回溯法 一、思路：见 p41 二、哪些问题可用回溯法解 1．迷宫问题 详见《数据结构》C 语言版 p50 3.2.4 或题集 p183 2．排列问题、组合问题、皇后问题、砝码问题。详见补充材料（师院学报理科版论文： 几个典型问题的回溯算法）。 对于砝码问题，有简单的非回溯算法——穷举砝码个数位二进制法，类似于最长有序 子序列的非动态规则法。 3．集和问题 见 cp139 n 个正数，找出满足条件的一切组合：每个组合中的数之和等于给定的某个正数 M。 算法类似于砝码问题。例子：M=30,W=(5,10,12,13,15,18) 解：5 10 0 0 15 0，5 0 12 13 0 0 ，0 0 12 0 0 18 4． 性判定问题，cp141 5．哈密顿回路，cp144 6．稳定婚姻问题，p32 7．马步问题，p41 …… 三、以排列组合或 N 后问题为例引入回溯思想。 补充： （一）马步问题 1．先演示 41 页 5 阶阵人工走法技巧 2．再演示下图（逆时针均匀转大圈法） 21 4 9 14 19 10 15 20 3 8 5 22 1 18 13 16 11 24 7 2 23 6 17 12 25

边上最困难,走法最少,先解决。绕中心转 计算机程序实现比较困难,且有偶然性。 3.再演示下图(随机转小圈) 8 15 492 5 4.回溯法介绍(程序实现方便) (二)图的可着色性(cpl142) 1.算法 const maxn=100 var g arrayal .: arrayll.. maxn]of integer; m, n integer; procedure coloring (k: integer Lable next Ifor j =I To k-l do if gLi, k=l and xll=i then goto mexti x[ k]: =1; if k=n then print(x)else coloring(k+1) next 输入mng, coloring(1) End。 2.例子 all 13 c13112 着色方案:1212 3121 23 22222 33333 212 21 231 13 333 232 三、哈密顿回路(cp145) 算法 const maxn=100 var g array[l..maxn, 1.. maxn]of integer; a: arrayll.. maxnof integer; m,n: integer procedure H(k integer ); Lable mexti I TO [for j:=l To k-1 do if all=i then goto mexti if g[a(k-1], i]l then goto mexti;

边上最困难，走法最少，先解决。绕中心转。 计算机程序实现比较困难，且有偶然性。 3．再演示下图（随机转小圈） ×18 ×13 ×12 7 10 3 ×14 ×17 4 1 6 9 ×11 8 ×15 2 ×16 5 4．回溯法介绍（程序实现方便） （二）图的可着色性（cp142） 1．算法 const maxn=100; var g:array[1…maxn,1…maxn]of integer; x:array[1…maxn]of integer; m，n:integer; procedure mcoloring（k:integer）; Lable mexti; Begin for i：=1 To n do [for j:=1 To k-1 do if g[j,k]=1 and x[j]=i then goto mexti; x[k]:=i; if k=n then print(x) else mcoloring(k+1) mexti:] end; Begin 输入 m,n,g; mcoloring(1) End。 2．例子 a b a b c d m=3 n=4 着色方案： 1 2 1 2 2 1 2 1 3 1 2 1 c d 1 2 1 3 2 1 2 3 3 1 3 1 1 2 3 2 2 1 3 1 3 1 3 2 1 3 1 2 2 3 1 3 3 2 1 2 1 3 1 3 2 3 2 1 3 2 3 1 1 3 2 3 2 3 2 3 3 2 3 2 三、哈密顿回路（cp145） 1. 算法 const maxn=100; var g:array[1…maxn,1…maxn]of integer; a:array[1…maxn]of integer; m，n:integer; procedure H(k:integer); Lable mexti; Begin for i：=1 To n do [for j:=1 To k-1 do if a[j]=i then goto mexti; if g[a[k-1],i]<>1 then goto mexti;

ak]=; ifk= n then [if g{a[1]a[n= I then打印a else H(k+1) Begin( main: 输入ng,form=1 To n do[a[=mH[2] END 2.例子 结果:128765431 结果:无 第二节动态规则法 为求优化问题最优解的“顾全大局、全面考虑”的一种算法设计方法 1.矩阵乘法问题—一按乘法结合律安排连乘积顺序P23 2.特殊有向图的最短路径问题p29 类似于《数据结构》中求关键路径,区别是这里求min,那里求max. 特殊的含义是:具有层次性的有向无环图。 多级图的单源最短路径问题,请同学们按《数据结构》理解。 根据学生接受力和课时多少适当补充以下内容 3.求给定有限序列中最长有序子序列及其长度——有向图、动态规划。 问题:任给一个序列a,a,…,a,请提出方法,计算其最长有序子序列的长度(元素 个数)。注:子序列中元素可以从原序列中跳跃取出,不要求连续。例如,9,2,7,3,4, 10,则2,3,4,10是最长的有序子序列,其长度为4。 方法1穷举法 从1循环至2-1(即n位二进制,见下 图),对其中的每一个整数i,化成n位二进 长度 123 10路径 制,判别其为1的位置上原序列中的相应数是 否构成有序子序列,是则统计出1的个数c 所有c1的最大者即为题目所求。 方法2动态规划法 第一步:根据原序列的大小关系建立一个类似于AOE的网(见右上图) 令每个结点的长度初值为1,边权为1,路径序列初值开始时是本身,以后按类似 于最短路径的求法进行逐步替换

a[k]:=i; if k=n then [if g[a[1],a[n]]=1 then 打印 a] else H(k+1)； mexti:] end; Begin{main} 输入 n,g; for m:=1 To n do [a[1]:=m;H[2];] END 2. 例子： 1 2 3 4 5 结果：128765431 8 7 6 1 2 3 结果：无 5 4 第二节 动态规则法 ——为求优化问题最优解的“顾全大局、全面考虑”的一种算法设计方法 1. 矩阵乘法问题——按乘法结合律安排连乘积顺序 P23 2. 特殊有向图的最短路径问题 p29 类似于《数据结构》中求关键路径，区别是这里求 min，那里求 max. 特殊的含义是：具有层次性的有向无环图。 多级图的单源最短路径问题，请同学们按《数据结构》理解。 根据学生接受力和课时多少适当补充以下内容。 3. 求给定有限序列中最长有序子序列及其长度——有向图、动态规划。 问题：任给一个序列 a1,a2,…,an，请提出方法，计算其最长有序子序列的长度（元素 个数）。注：子序列中元素可以从原序列中跳跃取出，不要求连续。例如，9，2，7，3，4， 10，则 2，3，4，10 是最长的有序子序列，其长度为 4。 方法 1 穷举法 从 1 循环至 2 n -1( 即 n 位二进制，见下 图)，对其中的每一个整数 i, 化成 n 位二进 0 1 1 … 0 1 2 3 n 制，判别其为 1 的位置上原序列中的相应数是 否构成有序子序列，是则统计出 1 的个数 ci. 所有 ci的最大者即为题目所求。 方法 2 动态规划法 第一步：根据原序列的大小关系建立一个类似于 AOE 的网（见右上图）： 令每个结点的长度初值为 1，边权为 1，路径序列初值开始时是本身，以后按类似 于最短路径的求法进行逐步替换。 1 10 长度 路径 1 1 1 1 1 1 1 1 1 2 10 7 4 3 9

第二步:按逆拓扑顺序求从每个顶点出发可能构成的最长有序子序列及其长度(按如 下公式) VI(n)=l {n为出度为0点,可能不唯一} V()=max{V(j)+dut(<i,j>}{i为其它点} 其中,s是所有以i为尾的弧的集合。 该步的算法实现可仿《数据结构》算法7.13,7.14 第三步:max{Vl(i)}为所求解。 l≤i≤n 如果还需求出对应的最长子序列元素,则可仿最短路径一节。 教材p29图2.1对应的有向无环图: 3 3℃5 20244VD)38 (1,O) D28M)5 11 4B3不 X13,Q) (6,E) Y(10,M 要求同学以动态规划观点复习《数据结构》的关键路径一节。 4.最佳旅行路线(详见《 pcworld China1997.4》)pl59,奥赛精解) 5.一个M位(1≤m≤200)数字串及N个(0≤N≤20)加号,如何添加才能使总和最 小。作为同学思考题,课外完成。 货郎担问题(参考CP101) (1)问题描述 货郎担问题、旅行商问题、巡回推销员问题、 Travelling Salesman Problem-TSP (2)穷举法 任取一出发点V,则剩下的n-1个点任何一个排列均可能与V构成一条回路(因可 能是有向完全图),对每条回路计算一次长度,在这些长度中选取最小者,其对应的路径即 为所求。显然,计算量为0((n-1)!)。 (3)动态规划法 a.函数g(i,s)的定义—从顶点i出发,经过s中除去顶点i之外的其它顶点各一 次并回到顶点1的一条最短路径的长(s中可能包含1,也可能不包含),则g(1,V-{1})就 是一条最佳路线的长。 b.按最佳原理有:g(1,V-{1)=mnck+g(k,V-{1,k) 般地有:g(i,s)=min{cn+g(,s-{})}这里igs c.按b中所给式子,对图5.9(cp102)利用树形结构直观给出解法(值和路径获取)

第二步：按逆拓扑顺序求从每个顶点出发可能构成的最长有序子序列及其长度（按如 下公式）： ïî ï í ì = + < > = Vl(i) max{Vl(j) dut( i, j } {i } Vl(n) 1 {n 0 } j 为其它点 为出度为 的点，可能不唯一 <i,j>Îs, 1 £ i £ n-1 其中，s 是所有以 i 为尾的弧的集合。 该步的算法实现可仿《数据结构》算法 7.13，7.14。 第三步： 1£i£n max {Vl(i)}为所求解。 如果还需求出对应的最长子序列元素，则可仿最短路径一节。 教材 p29 图 2.1 对应的有向无环图： 要求同学以动态规划观点复习《数据结构》的关键路径一节。 4．最佳旅行路线（详见《pcworld China 1997.4》）p159，奥赛精解） 5．一个 M 位（1£ m£ 200）数字串及 N 个（0£ N £ 20）加号，如何添加才能使总和最 小。作为同学思考题，课外完成。 6．货郎担问题（参考 CP101） （1）问题描述 货郎担问题、旅行商问题、巡回推销员问题、Travelling Salesman Problem—TSP （2）穷举法 任取一出发点 V0，则剩下的 n-1 个点任何一个排列均可能与 V0构成一条回路（因可 能是有向完全图），对每条回路计算一次长度，在这些长度中选取最小者，其对应的路径即 为所求。显然，计算量为 O（（n-1）！）。 （3）动态规划法 a. 函数 g(i,s)的定义——从顶点 i 出发，经过 s 中除去顶点 i 之外的其它顶点各一 次并回到顶点 1 的一条最短路径的长（s 中可能包含 1，也可能不包含），则 g(1,V-{1})就 是一条最佳路线的长。 b. 按最佳原理有：g(1,V-{1})= 2£k£n min {c1k + g(k,V-{1，k})} 一般地有：g(i,s)= min{c g( j,s { j})} ij j s + - Î 这里 iÏs c．按 b 中所给式子，对图 5.9（cp102）利用树形结构直观给出解法（值和路径获取） F C K A G P O D L S B H Q E M J R T U N 2 1 3 2 3 4 3 3 2 1 3 2 2 3 2 2 1 4 2 2 3 1 1 2 1 4 3 2 2 5 4 (2,O) (1,O) (4,B) (6,E) (9,J) (10,M) (13,Q) (11,S) (6,H) (8,M) (9,P) (8,L) (6,H) (5,D) (3,B) (7,D) (5,A) (8,G) (7,C)

910 (1,{2,3,4}) mIn C12+g(2,{3,4}) C13+g(3,{2,4})c14+g(4,{2,3}) c23+g(3,{4)cx+g(4,(3)cx2+g(2,4)ca+(42)c4+g(2,3)c43+g(,2) Cy+g(4φ)c4+g(3,φ)c24+g(4,φ)ca+g(2,φ)c23+g(3,中)c2+g(2φ) (计算过程为向上,推导理解过程向下) d.复杂度(对一般情形n个点) 下面部分讲课时省去!只进行简单说明(与穷举法对比) 用5个点的情形,在黑板上演示以推导复杂度:需要实际计算g(i,s)的次数(己有的 不再计算,直接取,因而只需第一次计算的次数,比如计算g(3,{2,5})和g(4,{2,5}), 即 min{(32+g(2,{5}),(35+g(5,{2})}和min{(42+g(2,{5}),45+g(5,{2})} 都要g(2,{5})和g(5,{2}),亦即公用{2,5}。 故,一般情况下,整个过程必须要计算和存储的内容为: g(2,φ)+g(3,φ)+g(4,φ)+…+g(m,φ),此即n-1个ca值,i=1,2,…n,共 (n-1)c2个 [g(2,{3}),g(2,{4}),…g(2,{n}),g(3,{2}),g(3,{4}),…,g(3,{n}),…,g(n,{2}), g(n,{3}),…,g(n,{n-1})],共有(n-1)*c [g(2,{3,4}),g(2,{3,5}) (2,{3,n}) 2,{4,5}),g(2,{4,6}),…, g(2,{n-1,n}),g(3,{2,4}),g(3,{2,5}),…,g(3,{2,n}),g(3,{4,5}),g(3,{4,6}),…, g(3,{n-1,n}),g(n,{2,3}),g(n,{2,4}),…,g(n,{2,n}),g(n,{4,5}),g(n,{4,6}),…, g(n,n-2,n-1})],共n-1)*c2 [g(2,{3,4,5,…,n}),g(3,{2,4,5,…,n}),…,g(n,{2,3,4,5,…,n-1}),共(n-1)

c= ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ ¥ ¥ ¥ ¥ 8 8 9 6 13 12 5 9 10 10 15 20 g(1,{2,3,4}) min c12 +g(2,{3,4}) c13 + g(3,{2,4}) c14 +g(4,{2,3}) min min min c23 + g(3,{4}) c24 + g(4,{3}) c32 + g(2,{4}) c34 + g(4,{2}) c42 + g(2,{3}) c43 + g(3,{2}) c34 +g(4,f ) c 43 + g(3,f ) c 24 + g(4,f ) c 42 + g(2,f ) c 23 + g(3,f ) c 32 + g(2,f ) c 41 c 31 c 41 c 21 c 31 c 21 (计算过程为向上，推导理解过程向下) d.复杂度（对一般情形 n 个点） 下面部分讲课时省去！只进行简单说明（与穷举法对比） 用 5 个点的情形，在黑板上演示以推导复杂度：需要实际计算 g(i,s)的次数（已有的 不再计算，直接取，因而只需第一次计算的次数，比如计算 g(3,{2，5})和 g(4,{2，5})）， 即 min{(32+g(2,{5}),(35+g(5,{2})}和 min{(42+g(2,{5}),45+g(5,{2})} 都要 g(2,{5})和 g(5,{2}),亦即公用{2,5}。 故，一般情况下，整个过程必须要计算和存储的内容为： g(2, f )+ g(3, f )+ g(4, f )+…+ g(n, f ),此即 n-1 个 c i1 值，i=1,2,…,n, 共 (n-1)c 0 n-2 个 [g(2,{3})，g(2,{4})，…g(2,{n})，g(3,{2})，g(3,{4})，…, g(3,{n})，…, g(n,{2}), g(n,{3}),…, g(n,{n-1})],共有(n-1) *c1 n-2 [g(2,{3,4}), g(2,{3,5}),…, g(2,{3,n}), g(2,{4,5}), g(2,{4,6}),…, g(2,{n-1,n}), g(3,{2,4}), g(3,{2,5}),…, g(3,{2,n}), g(3,{4,5}), g(3,{4,6}),…, g(3,{n-1,n}), g(n,{2,3}), g(n,{2,4}),…, g(n,{2,n}), g(n,{4,5}), g(n,{4,6}),…, g(n,{n-2,n-1})]，共(n-1) *c 2 n-2 … [g(2,{3,4,5,…,n}), g(3,{2,4,5,…,n}),…, g(n,{2,3,4,5,…,n-1}), 共 (n-1)