著名算法matlab编程----贪心算法-背包问题----递归算法-Hanoi塔问题-----回溯算

1/22《数学实验》七贪心算法—背包问题递归算法—Hanoi塔问题回溯算法—n皇后问题2/22贪心算法背包问题1211221122(1,2,)[,,,]10iiniinnnnnbiacinxxxixxcxcxcxaxaxax有旅行者要从种物品中选取不超过公斤的物品放入背包，要求总价值最大。设第种物品的重量为，价值为，。定义向量，当选第种物品往背包放时取，否则取。于是所有选取的物品的总价值为：，总的重量为：。问题可描述为11221122max10(1,2,,)nnnnizcxcxcxaxaxaxbxin约束条件为：或3/22贪心算法意为见到好的就抓住不放，用贪心算法求解问题，一般可以获得比较好的求解速度。本问题的具体做法为：先计算物品的价值密度，并把物品按价值密度从大到小的顺序排列：121,2,,niikkkicpinpppa，1iikk当选择第件物品时，先判断背包是否超载，如果不超载，则放入背包，否则考虑下一件。按照这种方式考虑所有物品，即能得到背包问题的一个近似最优解。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(n:-1:1);tw=0;%已装入背包的物品重量fori=1:nif(tw+weight(b(i)))=maxweitw=tw+weight(b(i));sch(b(i))=1;endendtolwei=tw;tolval=sum(value(find(sch)));[s,v,t]=backpack(110,[110204045223055],[1020305055324060])s=11100110v=132t=835/22递归算法Hanoi塔问题传说在贝拿勒斯的圣庙里，有块黄铜板，上面竖着3根宝石柱，这些宝石柱，径不及小指，长仅半臂。大梵天王(印度教的一位主神)在创造世界的时候，在其中一根柱上放置了64片中心有插孔的金片。这些金片的大小不一样，大的在下面，小的在上面，从下而上叠成塔形，这就是所谓的梵天宝塔。大梵天王立下法则：金片从一柱移到另一柱时，每次只能移动一片，且移动过程中，小金片永远在大金片上面，绝不允许颠倒。大梵天王预言：当金片从它创造世界时的宝石柱移到另一宝石柱上时，世界末日就要来临，一声霹雳会将梵塔、庙宇和众生都消灭干净。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，共需次数为：2an-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秒，相当于5846亿年，比太阳的寿命都长(太阳的寿命不超过200亿年)。9/22首先构造数据结构。对金片，从上到下，分别有用整数1,2,3,……,n表示；三根宝石柱，从左到右分别用1,2,3表示。对于每一次移动，我们用一个行向量表示，例如把编号为4的金片从柱1移到柱3时，我们用向量[413]表示。本算法在hanoi.m文件中用两个函数实现，其中一个是主函数，定义如下：function[tolnum,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)返回参数tolnum表示移到次数，scheme是移动方案矩阵，一行表示一次移动方式。输入参数disknum表示本次移动的金片数(即最上面的disknum个金片)，beginpillar表示金片所在原始柱，endpillar表示目标柱，midpillar表示中间柱(即辅助柱子)。10/22第二个是子函数，外部不能调用，只供主函数hanoi调用。该函数是实现递归生成的关键，而主函数hanoi实际上只起到了一个转换参数的作用，其定义如下：functiontemphanoi(disknum,beginpillar,midpillar,endpillar)该子函数没有返回参数，它使用了一个全局变量与主函数共享数据。输入的四个参数与主函数的四个输入参数含义相同。下面演示了三个金片从柱1移动到目标柱3的过程：11/22在命令窗口输入：[n,s]=hanoi(3,1,2,3)n=7s=11321213231312122311312312323132131212312312312312/22function[tolnum,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)globalSCHEME_HANOI%全局变量,子函数可以直接访问SCHEME_HANOI=[];%设置为空temphanoi(disknum,beginpillar,midpillar,endpillar);tolnum=size(SCHEME_HANOI,1);%取得行数,即移动次数scheme=SCHEME_HANOI;%子函数,只能在本程序访问,外部不可见functiontemphanoi(disknum,beginpillar,midpillar,endpillar)%子函数globalSCHEME_HANOI%声明使用ifdisknum==1%添加一行移动方式SCHEME_HANOI=[SCHEME_HANOI;1,beginpillar,endpillar];else%下面一句相当于把上面n-1片移到中间柱子temphanoi(disknum-1,beginpillar,endpillar,midpillar);%然后把最后一片移到目标柱子上SCHEME_HANOI=[SCHEME_HANOI;disknum,beginpillar,endpillar];%把中间当作第一根,原来第一根当作中间柱子,继续移动temphanoi(disknum-1,midpillar,beginpillar,endpillar);end13/22回溯算法1212121122111[,,]()[,,][,,]niiiiiiiiiixxxxSxxxxxxinxSxSxS回溯法是重要的算法设计方法，回溯法的基本做法是搜索。假定一个问题的解能够表示成一个向量，，且解及其子集部分解应满足一定的约束条件。：若已有满足约束条件的部分解，不妨设为：，，则添加，检查是否满足约束条件，满足就继续添加。若对均不回溯法的思想是满足约束条件121[,,]iiiixxxxxS，就去掉，回溯到，添加尚未考察过的，看是否满足约束条件。如此反复进行，直到得到解或证明无解。14/22一种可能的回溯树结构部分解搜索路径回溯路径正确解成功啦!15/22n皇后问题国际象棋规定：一个皇后可以攻击与之同处在同一行或同一列或同一斜线上的其它任何棋子。问怎样在一个n×n的棋盘上放置n个皇后，使得它们彼此不受攻击？如右图，若一个皇后在第一行的第三格，则第二行的第二、三、四都不能放，只能放在第一格。设棋盘上两个皇后的位置坐标分别为(m,n)和(i,j)，按照攻击规则，若两皇后产生攻击，则必然有：i=m，或n=j，或|i-m|=|j-n|(可从两点连线斜率为1或-1得到)。16/22现分析在第i行第j列放一个皇后时，可能会产生哪些动作：若该位置不符合攻击规则，放入皇后后，则若in，则令i=i+1，重新进行判断i=n，则找到一种方案，回到上一行，继续搜索可行方案该位置符合攻击规则，若jn，则令j=j+1，继续搜索17/22本例使用了三个函数，主函数为：function[num,scheme]=Queen(n)返回参数num表示n×n棋盘放置n个皇后总的可行方案数，scheme是方案矩阵，一行是一个可行方案，例如[2,4,1,3]表示4×4棋盘中第1个皇后放在第一行第2列，第2个皇后放在第2行第4列……。第二和第三个是子函数，定义为：functionsearch()functionresult=checkchess(row,col)search实现回溯搜索，checkchess检查当前row-1行皇后放好后，在第row行第col列是否可以放皇后。18/22在命令窗口输入：[a,b]=queen(4)a=2b=2413314219/22在命令窗口输入：[a,b]=queen(5)a=10b=1352414253241352531431425352414135242531524135314220/22function[num,scheme]=Queen(n)globalSCHEME_MATRIXNCURROWN=n;SCHEME_MATRIX=zeros(1,n);%一个空方案CURROW=1;search;%搜索scheme=SCHEME_MATRIX(1:(end-1),:);num=size(scheme,1);这是主函数，定义了三个全局变量，便于程序间传递数据。其中CURROW保存当前正在搜索的行。search是自定义的子函数，end用来指示当前维的最后一个脚标。21/22functionsearch()globalSCHEME_MATRIXNCURROWfori=1:N%在当前行逐列搜索ifcheckchess(CURROW,i)%满足放置条件SCHEME_MATRIX(end,CURROW)=i;%在当前行放入皇后if(CURROWN)CURROW=CURROW+1;search;%进入下一行搜索else%已在最后一行放入皇后，添加新的方案行SCHEME_MATRIX=[SCHEME_MATRIX;SCHEME_MATRIX(end,:)];break;endendendCURROW=CURROW-1;%回溯到上一行,继续搜索22/22functionresult=checkchess(row,col)globalSCHEME_MATRIXfori=1:(row-1);%逐行比较ifSCHEME_MATRIX(end,i)==col||abs(i-row)==abs(SCHEME_MATRIX(end,i)-col)result=0;return;endendresult=1;%没有出现会攻击的情况,返回真