第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为其它点} 其中,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 为其它点 为出度为 的点，可能不唯一 Î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)
故,除G(1,{2,3,4,…,m)外,全部必须计算并存储的G值为∑(n-1)c=2个 由于每计算一个G(i,s)值,都要进行|s|-1次比较,故,算出最短路径 G(1,{2,3,4,…,n})所需总的比较次数为 n-1+∑(n-1)cb-2*(k-1)<m-1+(n-1)2∑cn2=(n-1)+(n-1)22 故,时间复杂度为:0((n-1)22m-2)=0((n22-2)次比较(或加法) 这比穷举法0(n!)好,但仍不可行。 由于是指数算法,故算法无意义,不介绍,只了解方法。由此知,TSP是难解问题。 7.资源分配问题(cp93) 第三节贪婪法(贪心法, Greedy method) 问题引入 到目前为止,我们已经学过了回溯法和动态规则法这两种设计算法的方法。今天我们 学习第三种方法——贪婪法(贪心法, Greedy method,板书题目) 贪婪法、动态规划法、穷举法都可以用于最优化问题的求解算法设计。但是,穷举 法只适于解决规模较小的问题,而且对某些连续的约束条件问题根本不可能穷举(比如我 们马上介绍的背包问题就是如此);而动态规划法的技巧性太强,不是所有优化问题都能 设计出巧妙的动态规划算法 那么,对于给定的优化问题,当其规模大,穷举法无能,动态规划算法一时很难设计出 来的时候,怎么办?请考虑使用贪婪法来设计算法。 虽然由贪婪法所得的解不一定是最优的,但总是接近最优的,而且设计算法容易,所得 算法复杂度低,运行速度快。 现实生活中的优化问题很多,大家在《数据结构》课程中熟知的有:哈夫曼树(最 有二叉树)问题、有向网络的关键路径(最长路经)问题,最短路径问题、无向网的最小 生成树问题等 由于本节将介绍的旅行商问题的贪婪法是受 kruskal算法的启发设计出来的,下面我 们先来回忆一下《数据结构》课程中的 kruskal算法求无向图最小生成树的动态过程(请 个同学到讲台上演示给大家看,无人自愿则点名) 6 演示求解过 6
*c 2 n-2 故，除 G(1,{2,3,4,…,n})外，全部必须计算并存储的 G 值为å - = - - n 2 k 0 k n 2 (n 1)c 个 由 于 每计算一个 G(i,s) 值 ， 都 要 进 行 |s|-1 次 比 较 ， 故 ， 算 出 最 短 路 径 G(1,{2,3,4,…,n})所需总的比较次数为： n-1+å - = - - n 2 k 0 k n 2 (n 1)c *(k-1)<n-1+(n-1) 2 å - = - 2 0 2 n k k n c =(n-1)+ ( n-1) 2 2 n-2 故，时间复杂度为：O(( n-1) 2 2 n-2 )=O(( n 2 2 n-2 )次比较（或加法） 这比穷举法 O(n!)好，但仍不可行。 由于是指数算法，故算法无意义，不介绍，只了解方法。由此知，TSP 是难解问题。 7.资源分配问题（cp93） 第三节 贪婪法（贪心法，Greedy method） 问题引入 到目前为止，我们已经学过了回溯法和动态规则法这两种设计算法的方法。今天我们 学习第三种方法——贪婪法（贪心法，Greedy method，板书题目） 贪婪法、动态规划法、穷举法都可以用于最优化问题的求解算法设计。但是，穷举 法只适于解决规模较小的问题，而且对某些连续的约束条件问题根本不可能穷举（比如我 们马上介绍的背包问题就是如此）；而动态规划法的技巧性太强，不是所有优化问题都能 设计出巧妙的动态规划算法。 那么，对于给定的优化问题，当其规模大，穷举法无能，动态规划算法一时很难设计出 来的时候，怎么办？请考虑使用贪婪法来设计算法。 虽然由贪婪法所得的解不一定是最优的，但总是接近最优的，而且设计算法容易，所得 算法复杂度低，运行速度快。 现实生活中的优化问题很多，大家在《数据结构》课程中熟知的有：哈夫曼树（最 有二叉树）问题、有向网络的关键路径（最长路经）问题，最短路径问题、无向网的最小 生成树问题等。 由于本节将介绍的旅行商问题的贪婪法是受 kruskal 算法的启发设计出来的，下面我 们先来回忆一下《数据结构》课程中的 kruskal 算法求无向图最小生成树的动态过程（请 一个同学到讲台上演示给大家看，无人自愿则点名）。 ① ① 6 5 ② 5 1 ④ 演示求解过程 ② 5 1 ④ 3 ③ 5 ③ 2 6 4 2 3 4 ⑤ ⑥ ⑤ ⑥ 6
从刚才的演示可知,最小生成树的求解过程是按边长递增的顺序进行的 其实,用 kruskal算法求给定网络最小生成树,使用的方法就是贪婪法,其求解过程是: 逐步给岀解的各部分,在每一点贪棽地选择最奷的部分解,但不顾及这样选择对整体的影响, 因此,一般得到的不是最好的解 不过,对最小生成树问题, kruskal贪心算法得到的碰巧是… 我们下面的任务就是通过对另外两个典型优化问题的求解来学习设计算法的贪婪法。 (背包问题,旅行商问题) 、背包问题( knapsack problem 1.问题描述 通俗:设某港口有n种不同的货物要求运往某地,每种货物的总重量为已知,各种不 同货物的运价也是确定的。 某支船队承运部分货物,其总吨位是确定的,每种货物允许分批发运。这支船队应装 运每种货物各多少,才能使它一次获得的运费最多? 形式:给定M(吨位,背包容量)>0,O2(各种货物重量>0,p(运完O能得到的利润 或运费)0,1≤i≤n。要求找出一个n元向量(x,x2,,xn),0≤x≤1,1≤i≤n,使得: ∑ox≤M且∑Px达到最大。 2.解背包问题的贪婪法 大家知道,满足0≤x≤1,的任何向量(x1x2,,xn)都是一个可能解,这样的解显然 有无穷多个,而最佳解必然使∑px达到最大。 对这种可能解空间是连续实数空间的优化问题,无法用穷举法求解,因此下面我们就 围绕主观上使∑Px达到最大这个目标,通过具体例子来讨论贪心求解法。 n3,M=40.(01,02,O3)=(2815,24,(P1,P2,P3)=(35,25,24) 贪心策略 (x1x2x3)∑O,x, pixi (1)按P的由大至小选O (1,4/5,0) 4055 (2)按O,的由小至大选O1(128,1,1)4049+35*128=5025 (3)按pO有大至小选O1(2528,1,0)4025/28*35+25=5625 可见,第三种方法所得解最优。 对于一般的背包问题,常用这个例子中第(3)种贪心策略进行求解,下面假定∑oM (因o,<M时,无需选择,全部装运即可),并对这三种贪心策略进行直观分析
从刚才的演示可知，最小生成树的求解过程是按边长递增的顺序进行的。 其实，用 kruskal 算法求给定网络最小生成树，使用的方法就是贪婪法，其求解过程是： 逐步给出解的各部分，在每一点贪婪地选择最好的部分解，但不顾及这样选择对整体的影响， 因此，一般得到的不是最好的解。 不过，对最小生成树问题，kruskal 贪心算法得到的碰巧是… 我们下面的任务就是通过对另外两个典型优化问题的求解来学习设计算法的贪婪法。 （背包问题，旅行商问题） 一、背包问题（knapsack problem） 1．问题描述 通俗：设某港口有 n 种不同的货物要求运往某地，每种货物的总重量为已知，各种不 同货物的运价也是确定的。 某支船队承运部分货物，其总吨位是确定的，每种货物允许分批发运。这支船队应装 运每种货物各多少，才能使它一次获得的运费最多? 形式：给定 M（吨位，背包容量）>0，wi (各种货物重量)>0, pi (运完wi 能得到的利润 或运费)>0，1 £ i£ n。要求找出一个 n 元向量（x1,x2,…,xn）, 0 £ xi £ 1, 1 £ i£ n，使得： å= £ n i i xi M 1 w 且å= n i i i p x 1 达到最大。 2．解背包问题的贪婪法 大家知道，满足 0£ xi £ 1，的任何向量（x1,x2,…,xn）都是一个可能解，这样的解显然 有无穷多个，而最佳解必然使å= n i i i p x 1 达到最大。 对这种可能解空间是连续实数空间的优化问题，无法用穷举法求解，因此下面我们就 围绕主观上使å= n i i i p x 1 达到最大这个目标，通过具体例子来讨论贪心求解法。 n=3,M=40,( 1 2 3 w ,w ,w )=(28,15,24),( 1 2 3 p , p , p )=(35,25,24) 贪心策略 （x1,x2,x 3 ） å= 3 i 1 i i w x å= 3 i 1 i i p x (1)按 pi 的由大至小选wi （1，4/5，0） 40 55 (2)按wi 的由小至大选wi （1/28，1，1） 40 49+35*1/28=50.25 (3)按 pi/wi 有大至小选wi （25/28，1，0） 40 25/28*35+25=56.25 可见，第三种方法所得解最优。 对于一般的背包问题，常用这个例子中第（3）种贪心策略进行求解，下面假定åwi >M （因åwi <=M 时，无需选择，全部装运即可），并对这三种贪心策略进行直观分析
(1)p大的物品先进包(x=1),直到某物品放不完时才取其一部分(x0。当(j)∈E时,定义Cn=∞
（1）pi 大的物品先进包（xi=1），直到某物品放不完时才取其一部分（xi0。当（i,j）ÏE 时，定义 Cij =¥
设№}=n1。所谓货郎担问题就是要在G中找出一条有最小消费的周游路线。 2.穷举法思路及改进方法,见教材p4-45,Om!)≈O(ne)) 3.由于求最佳解的穷举法复杂度太高,必须寻求近似解法以求较优解(近似解),或 称接近最优解。贪婪法就是其中之一。而贪婪法又有多种,这里先介绍最简单的一种 按教材p45介绍文字描述及 Pascal描述。 在黑板上画出图2.3进行求解过程演示,并说明所得解 ABCDEFA长70,不如 ABFEDCA 短,才 4.变形 kruskal法(另一种贪心法) (1)最小生成树求法(略) (2)画图演示变形算法思想p46,仍以图2.3为例演示求解过程 (3)计算机实现办法及类 pascal描述p47-49 (4)具体例子演示并改错P49 小结 另一个例子(略) 第四节分而治之法 1.引言(cp45) 2.合并(归并)排序(cp45)a.方法b.复杂度 3.快速排序(cp47)a.方法b.复杂度 4.赛程问题p50 5.整数乘法p54(自学为主) 6. strassen法(矩阵相乘)p56(自学为主) 三种语言同类型字节数对照 字节数 Integer %或 defiant 4 float single 或 defaNG 4 longint longinteger double double DedDbL 分而治之法(简称分治法) 引言或概述 要想直接解决一个较大的问题,有时是相当困难的。 1.分而治之( divide-and- conquer)的设计思想是:把一个难以下手的大问题分割成 些较小的子问题,再分别解决这些较小的子问题,然后由这些子问题的解构造出整个问题的 解。(思想) 2.如果能把一个规模为n的问题分割成若干个子问题,且这些子问题都可解,并且能 利用这些子问题的解求出原问题的解,那么这种分治方法便是可行的。(可行性) 因为子问题较小,一般比原问题容易处理 3.由分治法产生的子问题往往是原问题的较小模式,为使用递归技术提供了方便。在 多种情况下,反复应用分治手段,可以使子问题与原问题类型一致而规模却越来越小,最终 使子问题缩小到勿需再分且容易求解的地步。这样便自然导致递归过程的产生。分治和递归
设|V|=n>1。所谓货郎担问题就是要在 G 中找出一条有最小消费的周游路线。 2．穷举法思路及改进方法，见教材 p44~45，O(n!) » O((n/e)n ) 3．由于求最佳解的穷举法复杂度太高，必须寻求近似解法以求较优解（近似解），或 称接近最优解。贪婪法就是其中之一。而贪婪法又有多种，这里先介绍最简单的一种。 按教材 p45 介绍文字描述及 Pascal 描述。 在黑板上画出图 2.3 进行求解过程演示，并说明所得解 ABCDEFA 长 70，不如 ABFEDCA 短，才 65。 4．变形 kruskal 法（另一种贪心法） （1） 最小生成树求法（略） （2） 画图演示变形算法思想 p46，仍以图 2.3 为例演示求解过程 （3） 计算机实现办法及类 pascal 描述 p47-49 （4） 具体例子演示并改错 P49 5．小结 另一个例子（略） 第四节 分而治之法 1. 引言（cp45） 2. 合并（归并）排序（cp45） a.方法 b.复杂度 3. 快速排序（cp47） a.方法 b.复杂度 4. 赛程问题 p50 5. 整数乘法 p54（自学为主） 6. strassen 法（矩阵相乘）p56（自学为主） 三种语言同类型字节数对照 字节数 c pas bas 2 int integer %或 defint 4 float single ！或 defSNG 4 longint longinteger DefLong 8 double double DedDbL 分而治之法（简称分治法） 引言或概述 要想直接解决一个较大的问题，有时是相当困难的。 1．分而治之（divide-and-conquer）的设计思想是：把一个难以下手的大问题分割成一 些较小的子问题，再分别解决这些较小的子问题，然后由这些子问题的解构造出整个问题的 解。（思想） 2．如果能把一个规模为 n 的问题分割成若干个子问题，且这些子问题都可解，并且能 利用这些子问题的解求出原问题的解，那么这种分治方法便是可行的。（可行性） 因为子问题较小，一般比原问题容易处理。 3．由分治法产生的子问题往往是原问题的较小模式，为使用递归技术提供了方便。在 多种情况下，反复应用分治手段，可以使子问题与原问题类型一致而规模却越来越小，最终 使子问题缩小到勿需再分且容易求解的地步。这样便自然导致递归过程的产生。分治和递归
象一对孪生兄弟一样,经常同时应用在算法设计之中,并且产生许多高效算法。(与递归的 关系) 4.那么,根据分治法的分割原则,应把原问题分为多少个子问题才较适宜?每个子问 题是否大小一样及怎样才为适当?这些都很难肯定地予以回答。但人们从大量实践中发现 把一个问题分成大小相等的K个子问题的处理方法是行之有效的。许多问题可以取K等于 2。这种方法对不少问题具有典型意义。子问题大小相等的做法是出自一种平衡( balancing) 子问题的思想,它几乎总是比子问题大小不等的做法要好。(子问题个数) 5.究竟一些什么问题应该使用分治法,使用这一方法时应该怎样选择子问题的个数和 大小才能产生高效算法,目前很难给出科学的回答。我们还是致力于讨论一些具体问题,以 得到一些有益的启发。(适用场合) 现实生活中用分治法来处理的问题很多,如:用分而治之的方法,将国土分成几个部分 对每部分国土,委派一个诸侯去管理,国君自己就不直接过问这部分国土的事情了,他们的 工作就是分国土,派诸位,过问诸候工作的结果。 现今的国家和企事业单位管理机构也是借用的分而治之法:省、地、县、乡 处、科……;厅、处、科 在计算机算法设计领域,这种思想得到借鉴。例如,大家所熟知的河内塔问题算法、归 并排序算法、快速排序算法都是利用分治思想设计出来的 下面我们先来讨论一个大家不太熟悉但却很有用的问题的分治解法,然后再回头去总结 讨论归并、快速排序算法所采用的分治策略 、赛程问题 教材P50赛程问题:采用2等分的分治法。 教材写得不好,此处按补充材料介绍。(程国忠,赛程问题分治算法,西华师范大学学 报(自然科学版),2004.09) 实例演示:以堆栈为辅助工具,演示4阶和8阶例子的构造过程 时间复杂度分析 选赋值语句为基本运算,并设n=2时的4个赋值语句需时间为常数C1,三个二重For 循环中的每个赋值语句所需时间为常数C2(因为每个赋值语句右边表达式都要做两次除法 和两次加减法,运算次数相同),则由算法可得其时间复杂度的递归方程如下: n=2 7()+3()C2 可利用展开法解之
象一对孪生兄弟一样，经常同时应用在算法设计之中，并且产生许多高效算法。（与递归的 关系） 4．那么，根据分治法的分割原则，应把原问题分为多少个子问题才较适宜？每个子问 题是否大小一样及怎样才为适当？这些都很难肯定地予以回答。但人们从大量实践中发现： 把一个问题分成大小相等的 K 个子问题的处理方法是行之有效的。许多问题可以取 K 等于 2。这种方法对不少问题具有典型意义。子问题大小相等的做法是出自一种平衡（balancing） 子问题的思想，它几乎总是比子问题大小不等的做法要好。（子问题个数） 5．究竟一些什么问题应该使用分治法，使用这一方法时应该怎样选择子问题的个数和 大小才能产生高效算法，目前很难给出科学的回答。我们还是致力于讨论一些具体问题，以 得到一些有益的启发。（适用场合） 现实生活中用分治法来处理的问题很多，如：用分而治之的方法，将国土分成几个部分， 对每部分国土，委派一个诸侯去管理，国君自己就不直接过问这部分国土的事情了，他们的 工作就是分国土，派诸位，过问诸候工作的结果。 现今的国家和企事业单位管理机构也是借用的分而治之法：省、地、县、乡……；院、 处、科……；厅、处、科…… 在计算机算法设计领域，这种思想得到借鉴。例如，大家所熟知的河内塔问题算法、归 并排序算法、快速排序算法都是利用分治思想设计出来的。 下面我们先来讨论一个大家不太熟悉但却很有用的问题的分治解法，然后再回头去总结 讨论归并、快速排序算法所采用的分治策略。 一、赛程问题 教材 P50 赛程问题：采用 2 等分的分治法。 教材写得不好，此处按补充材料介绍。（程国忠，赛程问题分治算法，西华师范大学学 报（自然科学版），2004.09） 实例演示：以堆栈为辅助工具，演示 4 阶和 8 阶例子的构造过程。 时间复杂度分析： 选赋值语句为基本运算，并设 n=2 时的 4 个赋值语句需时间为常数 C1，三个二重 For 循环中的每个赋值语句所需时间为常数 C2（因为每个赋值语句右边表达式都要做两次除法 和两次加减法，运算次数相同），则由算法可得其时间复杂度的递归方程如下： ï î ï í ì + > = = ) 2 2 ) 3( 2 ( 2 ( ) 2 2 1 C n n n T C n T n 可利用展开法解之