著名算法matlab编程----贪心算法-背包问题----递归算法-Hanoi塔问题-----回溯算法-n皇后问题ppt课件.ppt

《著名算法matlab编程----贪心算法-背包问题----递归算法-Hanoi塔问题-----回溯算法-n皇后问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《著名算法matlab编程----贪心算法-背包问题----递归算法-Hanoi塔问题-----回溯算法-n皇后问题ppt课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/22 数学实验七贪心算法贪心算法背包问题背包问题递归算法递归算法Hanoi塔塔问题问题回溯算法回溯算法n皇后问题皇后问题2/221211221122(1,2,),10iiniinnnnnbiacinxxxixxc xc xc xa xa xa x 有旅行者要从 种物品中选取不超过 公斤的物品放入有旅行者要从 种物品中选取不超过 公斤的物品放入背包，要求总价值最大。设第 种物品的重量为 ，价背包，要求总价值最大。设第 种物品的重量为 ，价值为 ，。定义向量，当选第值为 ，。定义向量，当选第种物品往背包放时取，否则取。于是所有种物品往背包放时取，否则取。于是所有选取的物品的总价值为：，总的选取

2、的物品的总价值为：，总的重量为：。问题可描述为重量为：。问题可描述为11221122max 10 (1,2, ) nnnnizc xc xc xa xa xa xbxin约束条件为：约束条件为：或或3/22贪心算法意为见到好的就抓住不放，用贪心算法贪心算法意为见到好的就抓住不放，用贪心算法求解问题，一般可以获得比较好的求解速度。本求解问题，一般可以获得比较好的求解速度。本问题的具体做法为：先计算物品的价值密度，并问题的具体做法为：先计算物品的价值密度，并把物品按价值密度从大到小的顺序排列：把物品按价值密度从大到小的顺序排列：121,2, niikkkicpinpppa，1iikk 当选择第 件

3、物品时，先判断背包是否超载，如果当选择第 件物品时，先判断背包是否超载，如果不超载，则放入背包，否则考虑下一件。按照不超载，则放入背包，否则考虑下一件。按照这种方式考虑所有物品，即能得到背包问题的一个这种方式考虑所有物品，即能得到背包问题的一个近似最优解。近似最优解。4/22function sch,tolval,tolwei=backpack(maxwei,weight,value)n=size(weight,2);sch=zeros(1,n);p=value./weight;a,b=sort(p);%a从小到大排序后的向量从小到大排序后的向量,b是对应元素原始下标是对应元素原始下标b=b(

4、n:-1:1);tw=0;%已装入背包的物品重量已装入背包的物品重量for i=1:n if (tw+weight(b(i) s,v,t=backpack(110,1 10 20 40 45 22 30 55,10 20 30 50 55 32 40 60)s = 1 1 1 0 0 1 1 0v = 132 t = 835/22传说在贝拿勒斯的圣庙里，有块黄铜板，上面竖着传说在贝拿勒斯的圣庙里，有块黄铜板，上面竖着3根宝石根宝石柱，这些宝石柱，径不及小指，长仅半臂。大梵天王柱，这些宝石柱，径不及小指，长仅半臂。大梵天王(印度教印度教的一位主神的一位主神)在创造世界的时候，在其中一根柱上放置了

5、在创造世界的时候，在其中一根柱上放置了64片片中心有插孔的金片。这些金片的大小不一样，大的在下面，中心有插孔的金片。这些金片的大小不一样，大的在下面，小的在上面，从下而上叠成塔形，这就是所谓的梵天宝塔。小的在上面，从下而上叠成塔形，这就是所谓的梵天宝塔。大梵天王立下法则：金片从一柱移到另一柱时，每次只能移大梵天王立下法则：金片从一柱移到另一柱时，每次只能移动一片，且移动过程中，小金片永远在大金片上面，绝不允动一片，且移动过程中，小金片永远在大金片上面，绝不允许颠倒。许颠倒。大梵天王预言：当金片从它创造世界时的宝石柱移到另一宝大梵天王预言：当金片从它创造世界时的宝石柱移到另一宝石柱上时，世界末日

6、就要来临，一声霹雳会将梵塔、庙宇和石柱上时，世界末日就要来临，一声霹雳会将梵塔、庙宇和众生都消灭干净。众生都消灭干净。6/2212nABC7/22问题分析：问题分析：把柱把柱C作为目标柱子，设作为目标柱子，设an为为n块金片从其中一柱移块金片从其中一柱移到另一柱的搬运次数，则把到另一柱的搬运次数，则把n块金片从块金片从A移到移到C，可，可以先把前以先把前n-1片移到片移到B，需搬，需搬an-1次；接着把第次；接着把第n片从片从A称到称到C，再从，再从B把剩下的把剩下的n-1片搬到片搬到C，又需搬，又需搬an-1次。所以从次。所以从A到到n块金片称到柱块金片称到柱C，共需次数为：，共需次数为：2

7、an-1+1次。次。显然，当显然，当n=1时，时，a1=1，所以，所以Hanoi塔的移动次数相塔的移动次数相当于一个带初值的递归关系：当于一个带初值的递归关系：1121 (2)1nnaana 21nna 8/22假如你手脚比较麻利，假如你手脚比较麻利，1秒钟移动一片，秒钟移动一片， 那么：那么：n=1时，时，1秒钟可以完成任务秒钟可以完成任务n=2时，时，3秒钟可以完成任务秒钟可以完成任务n=3时，时，7秒钟可以完成任务秒钟可以完成任务.n=8时，时，4.25分钟可以完成任务分钟可以完成任务.n=64时，需时时，需时18,446,744,073,709,551,615秒，相当秒，相当于于584

8、6亿年，比太阳的寿命都长亿年，比太阳的寿命都长(太阳的寿命不超太阳的寿命不超过过200亿年亿年)。9/22首先构造数据结构。对金片，从上到下，分别有用首先构造数据结构。对金片，从上到下，分别有用整数整数 1,2,3,n表示；三根宝石柱，从左到右分别表示；三根宝石柱，从左到右分别用用1,2,3表示。对于每一次移动，我们用一个行向量表示。对于每一次移动，我们用一个行向量表示，例如把编号为表示，例如把编号为4的金片从柱的金片从柱1移到柱移到柱3时，我们时，我们用向量用向量4 1 3表示。表示。本算法在本算法在hanoi.m文件中用两个函数实现，其中一个文件中用两个函数实现，其中一个是主函数，定义如下

9、：是主函数，定义如下：function tolnum,scheme = hanoi(disknum,beginpillar,midpillar,endpillar)返回参数返回参数tolnum表示移到次数，表示移到次数，scheme是移动方案是移动方案矩阵，一行表示一次移动方式。输入参数矩阵，一行表示一次移动方式。输入参数disknum表示本次移动的金片数表示本次移动的金片数(即最上面的即最上面的disknum个金片个金片)，beginpillar表示金片所在原始柱，表示金片所在原始柱，endpillar表示目标表示目标柱，柱，midpillar表示中间柱表示中间柱(即辅助柱子即辅助柱子)。1

10、0/22第二个是子函数，外部不能调用，只供主函数第二个是子函数，外部不能调用，只供主函数hanoi调调用。该函数是实现递归生成的关键，而主函数用。该函数是实现递归生成的关键，而主函数hanoi实实际上只起到了一个转换参数的作用，其定义如下：际上只起到了一个转换参数的作用，其定义如下：function temphanoi (disknum,beginpillar,midpillar,endpillar)该子函数没有返回参数，它使用了一个全局变量与主该子函数没有返回参数，它使用了一个全局变量与主函数共享数据。输入的四个参数与主函数的四个输入函数共享数据。输入的四个参数与主函数的四个输入参数含义相同

11、。参数含义相同。下面演示了三个金片从柱下面演示了三个金片从柱1移动到目标柱移动到目标柱3的过程：的过程：11/22在命令窗口输入：在命令窗口输入： n,s=hanoi(3,1,2,3)n = 7s = 1 1 3 2 1 2 1 3 2 3 1 3 1 2 1 2 2 3 1 1 31 2 31232 3132131 21 2312312 31 2 312/22function tolnum,scheme = hanoi(disknum,beginpillar,midpillar,endpillar)global SCHEME_HANOI%全局变量全局变量,子函数可以直接访问子函数可以直接访问

12、SCHEME_HANOI=;%设置为空设置为空temphanoi(disknum,beginpillar,midpillar,endpillar);tolnum=size(SCHEME_HANOI,1);%取得行数取得行数,即移动次数即移动次数scheme=SCHEME_HANOI;%子函数子函数, 只能在本程序访问只能在本程序访问, 外部不可见外部不可见function temphanoi(disknum,beginpillar,midpillar,endpillar)%子函数子函数global SCHEME_HANOI%声明使用声明使用if disknum=1%添加一行移动方式添加一行移动

13、方式 SCHEME_HANOI=SCHEME_HANOI;1,beginpillar,endpillar;else%下面一句相当于把上面下面一句相当于把上面n-1片移到中间柱子片移到中间柱子 temphanoi(disknum-1,beginpillar,endpillar,midpillar); %然后把最后一片移到目标柱子上然后把最后一片移到目标柱子上 SCHEME_HANOI=SCHEME_HANOI;disknum,beginpillar,endpillar; %把中间当作第一根把中间当作第一根, 原来第一根当作中间柱子原来第一根当作中间柱子, 继续移动继续移动 temphanoi(d

14、isknum-1,midpillar,beginpillar,endpillar);end13/221212121122111,(),niiiiiiiiiixxxxSxxxxxxinxSxSxS 回溯法是重要的算法设计方法，回溯法的基本做法回溯法是重要的算法设计方法，回溯法的基本做法是搜索。假定一个问题的解能够表示成一个向量是搜索。假定一个问题的解能够表示成一个向量，且解及其子集 部分解 应满足，且解及其子集 部分解 应满足一定的约束条件。：若已有满足约一定的约束条件。：若已有满足约束条件的部分解，不妨设为：，则束条件的部分解，不妨设为：，则添加，检查是否满足约束条件，添加，检查是否满足约束条

15、件，满足就继续添加。若对均不满足就继续添加。若对均不回溯法的思想是回溯法的思想是满足满足约束条件约束条件121,iiiixxxxxS ，就去掉 ，回溯到，添加尚，就去掉 ，回溯到，添加尚未考察过的，看是否满足约束条件。如此反复未考察过的，看是否满足约束条件。如此反复进行，直到得到解或证明无解。进行，直到得到解或证明无解。14/22一种可能的回溯树结构一种可能的回溯树结构部分解部分解搜索路径搜索路径回溯路径回溯路径正确解正确解成成功功啦啦!15/22国际象棋规定：一个皇后可以攻击与之同处在同国际象棋规定：一个皇后可以攻击与之同处在同一行或同一列或同一斜线上的其它任何棋子。问一行或同一列或同一斜线

16、上的其它任何棋子。问怎样在一个怎样在一个nn的棋盘上放置的棋盘上放置n个皇后，使得它个皇后，使得它们彼此不受攻击？们彼此不受攻击？如右图，若一个皇后在第一如右图，若一个皇后在第一行的第三格，则第二行的第行的第三格，则第二行的第二、三、四都不能放，只能二、三、四都不能放，只能放在第一格。放在第一格。设棋盘上两个皇后的位置坐标分别为设棋盘上两个皇后的位置坐标分别为(m,n)和和(i,j)，按照攻击规则，若两皇后产生攻击，则必然有：按照攻击规则，若两皇后产生攻击，则必然有：i=m，或，或n=j，或，或|i-m|=|j-n|(可从两点连线斜率为可从两点连线斜率为1或或-1得到得到)。16/22现分析在

17、第现分析在第i行第行第j列放一个皇后时，可能会产生哪列放一个皇后时，可能会产生哪些动作：些动作：若该位置不符合攻击规则，放入皇后后，则若该位置不符合攻击规则，放入皇后后，则若若in，则令，则令i=i+1，重新进行判断，重新进行判断i=n，则找到一种方案，回到上一行，继续，则找到一种方案，回到上一行，继续搜索可行方案搜索可行方案该位置符合攻击规则，若该位置符合攻击规则，若j a,b=queen(4)a = 2b = 2 4 1 3 3 1 4 219/22在命令窗口输入：在命令窗口输入： a,b=queen(5)a = 10b = 1 3 5 2 4 1 4 2 5 3 2 4 1 3 5 2

18、5 3 1 4 3 1 4 2 5 3 5 2 4 1 4 1 3 5 2 4 2 5 3 1 5 2 4 1 3 5 3 1 4 220/22function num,scheme = Queen(n)global SCHEME_MATRIX N CURROWN=n;SCHEME_MATRIX=zeros(1,n);%一个空方案一个空方案CURROW=1;search;%搜索搜索scheme=SCHEME_MATRIX(1:(end-1),:);num=size(scheme,1);这是主函数，定义了三个全局变量，便于程序间传递这是主函数，定义了三个全局变量，便于程序间传递数据。其中数据。其

19、中CURROW保存当前正在搜索的行。保存当前正在搜索的行。search是自定义的子函数，是自定义的子函数，end用来指示当前维的最用来指示当前维的最后一个脚标。后一个脚标。21/22function search()function search()global SCHEME_MATRIX N CURROWglobal SCHEME_MATRIX N CURROWfor i=1:N%for i=1:N%在当前行逐列搜索在当前行逐列搜索 if checkchess(CURROW,iif checkchess(CURROW,i) %) %满足放置条件满足放置条件 SCHEME_MATRIX(end

20、,CURROWSCHEME_MATRIX(end,CURROW)=i;%)=i;%在当前行放入皇后在当前行放入皇后 if(CURROWif(CURROWN) CURROW=CURROW+1;search;%N) CURROW=CURROW+1;search;%进入下一行搜索进入下一行搜索 else %else %已在最后一行放入皇后，添加新的方案行已在最后一行放入皇后，添加新的方案行 SCHEME_MATRIX=SCHEME_MATRIX;SCHEME_MATRIX(endSCHEME_MATRIX=SCHEME_MATRIX;SCHEME_MATRIX(end,:);,:); break; break; end end end endendendCURROW=CURROW-1;%CURROW=CURROW-1;%回溯到上一行回溯到上一行, , 继续搜索继续搜索22/22