故,除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 时，无需选择，全部装运即可），并对这三种贪心策略进行直观分析