著名算法matlab編程-貪心算法-背包問題-遞歸算法-Hanoi塔問題-回溯算法-n皇后問題課件

《數(shù)學(xué)實驗》七貪心算法—背包問題遞歸算法—Hanoi塔問題回溯算法—n皇后問題《數(shù)學(xué)實驗》七貪心算法—背包問題貪心算法背包問題貪心算法背包問題貪心算法意為見到好的就抓住不放，用貪心算法求解問題，一般可以獲得比較好的求解速度。本問題的具體做法為：先計算物品的價值密度，并把物品按價值密度從大到小的順序排列：貪心算法意為見到好的就抓住不放，用貪心算法求解問題，一般可以function[sch,tolval,tolwei]=backpack(maxwei,weight,value)n=size(weight,2);sch=zeros(1,n);p=value./weight;[a,b]=sort(p);%a從小到大排序后的向量,b是對應(yīng)元素原始下標(biāo)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=83function[sch,tolval,tolwei]=b遞歸算法Hanoi塔問題傳說在貝拿勒斯的圣廟里，有塊黃銅板，上面豎著3根寶石柱，這些寶石柱，徑不及小指，長僅半臂。大梵天王(印度教的一位主神)在創(chuàng)造世界的時候，在其中一根柱上放置了64片中心有插孔的金片。這些金片的大小不一樣，大的在下面，小的在上面，從下而上疊成塔形，這就是所謂的梵天寶塔。大梵天王立下法則：金片從一柱移到另一柱時，每次只能移動一片，且移動過程中，小金片永遠(yuǎn)在大金片上面，絕不允許顛倒。大梵天王預(yù)言：當(dāng)金片從它創(chuàng)造世界時的寶石柱移到另一寶石柱上時，世界末日就要來臨，一聲霹靂會將梵塔、廟宇和眾生都消滅干凈。遞歸算法Hanoi塔問題傳說在貝拿勒斯的圣廟里，12nABC12nABC問題分析：把柱C作為目標(biāo)柱子，設(shè)an為n塊金片從其中一柱移到另一柱的搬運次數(shù)，則把n塊金片從A移到C，可以先把前n-1片移到B，需搬an-1次；接著把第n片從A稱到C，再從B把剩下的n-1片搬到C，又需搬an-1次。所以從A到n塊金片稱到柱C，共需次數(shù)為：2an-1+1次。顯然，當(dāng)n=1時，a1=1，所以Hanoi塔的移動次數(shù)相當(dāng)于一個帶初值的遞歸關(guān)系：問題分析：把柱C作為目標(biāo)柱子，設(shè)an為n塊金片從其中一柱移到假如你手腳比較麻利，1秒鐘移動一片，那么：n=1時，1秒鐘可以完成任務(wù)n=2時，3秒鐘可以完成任務(wù)n=3時，7秒鐘可以完成任務(wù)…….n=8時，4.25分鐘可以完成任務(wù)…….n=64時，需時18,446,744,073,709,551,615秒，相當(dāng)于5846億年，比太陽的壽命都長(太陽的壽命不超過200億年)。假如你手腳比較麻利，1秒鐘移動一片，那么：首先構(gòu)造數(shù)據(jù)結(jié)構(gòu)。對金片，從上到下，分別有用整數(shù)1,2,3,……,n表示；三根寶石柱，從左到右分別用1,2,3表示。對于每一次移動，我們用一個行向量表示，例如把編號為4的金片從柱1移到柱3時，我們用向量[413]表示。本算法在hanoi.m文件中用兩個函數(shù)實現(xiàn)，其中一個是主函數(shù)，定義如下：function[tolnum,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)返回參數(shù)tolnum表示移到次數(shù)，scheme是移動方案矩陣，一行表示一次移動方式。輸入?yún)?shù)disknum表示本次移動的金片數(shù)(即最上面的disknum個金片)，beginpillar表示金片所在原始柱，endpillar表示目標(biāo)柱，midpillar表示中間柱(即輔助柱子)。首先構(gòu)造數(shù)據(jù)結(jié)構(gòu)。對金片，從上到下，分別有用整數(shù)1,2,3第二個是子函數(shù)，外部不能調(diào)用，只供主函數(shù)hanoi調(diào)用。該函數(shù)是實現(xiàn)遞歸生成的關(guān)鍵，而主函數(shù)hanoi實際上只起到了一個轉(zhuǎn)換參數(shù)的作用，其定義如下：functiontemphanoi(disknum,beginpillar,midpillar,endpillar)該子函數(shù)沒有返回參數(shù)，它使用了一個全局變量與主函數(shù)共享數(shù)據(jù)。輸入的四個參數(shù)與主函數(shù)的四個輸入?yún)?shù)含義相同。下面演示了三個金片從柱1移動到目標(biāo)柱3的過程：第二個是子函數(shù)，外部不能調(diào)用，只供主函數(shù)hanoi調(diào)用。該函在命令窗口輸入：>>[n,s]=hanoi(3,1,2,3)n=7s=113

212132

313121

223113123123231321312123123123123在命令窗口輸入：>>[n,s]=hanoi(3,1,2,3function[tolnum,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)globalSCHEME_HANOI%全局變量,子函數(shù)可以直接訪問SCHEME_HANOI=[];%設(shè)置為空temphanoi(disknum,beginpillar,midpillar,endpillar);tolnum=size(SCHEME_HANOI,1);%取得行數(shù),即移動次數(shù)scheme=SCHEME_HANOI;%子函數(shù),只能在本程序訪問,外部不可見functiontemphanoi(disknum,beginpillar,midpillar,endpillar)%子函數(shù)globalSCHEME_HANOI%聲明使用ifdisknum==1%添加一行移動方式SCHEME_HANOI=[SCHEME_HANOI;1,beginpillar,endpillar];else%下面一句相當(dāng)于把上面n-1片移到中間柱子temphanoi(disknum-1,beginpillar,endpillar,midpillar);%然后把最后一片移到目標(biāo)柱子上SCHEME_HANOI=[SCHEME_HANOI;disknum,beginpillar,endpillar];%把中間當(dāng)作第一根,原來第一根當(dāng)作中間柱子,繼續(xù)移動temphanoi(disknum-1,midpillar,beginpillar,endpillar);endfunction[tolnum,scheme]=han回溯算法回溯算法一種可能的回溯樹結(jié)構(gòu)部分解搜索路徑回溯路徑正確解成功啦!一種可能的回溯樹結(jié)構(gòu)部分解搜索路徑回溯路徑正確解成功啦!n皇后問題國際象棋規(guī)定：一個皇后可以攻擊與之同處在同一行或同一列或同一斜線上的其它任何棋子。問怎樣在一個n×n的棋盤上放置n個皇后，使得它們彼此不受攻擊？如右圖，若一個皇后在第一行的第三格，則第二行的第二、三、四都不能放，只能放在第一格。設(shè)棋盤上兩個皇后的位置坐標(biāo)分別為(m,n)和(i,j)，按照攻擊規(guī)則，若兩皇后產(chǎn)生攻擊，則必然有：i=m，或n=j，或|i-m|=|j-n|(可從兩點連線斜率為1或-1得到)。n皇后問題國際象棋規(guī)定：一個皇后可以攻擊與之同處在同一行或同現(xiàn)分析在第i行第j列放一個皇后時，可能會產(chǎn)生哪些動作：若該位置不符合攻擊規(guī)則，放入皇后后，則若i<n，則令i=i+1，重新進(jìn)行判斷i=n，則找到一種方案，回到上一行，繼續(xù)搜索可行方案該位置符合攻擊規(guī)則，若j<n，則令j=j+1，繼續(xù)搜索現(xiàn)分析在第i行第j列放一個皇后時，可能會產(chǎn)生哪些動作：若該位本例使用了三個函數(shù)，主函數(shù)為：

function[num,scheme]=Queen(n)返回參數(shù)num表示n×n棋盤放置n個皇后總的可行方案數(shù)，scheme是方案矩陣，一行是一個可行方案，例如[2,4,1,3]表示4×4棋盤中第1個皇后放在第一行第2列，第2個皇后放在第2行第4列……。第二和第三個是子函數(shù)，定義為：functionsearch()functionresult=checkchess(row,col)search實現(xiàn)回溯搜索，checkchess檢查當(dāng)前row-1行皇后放好后，在第row行第col列是否可以放皇后。本例使用了三個函數(shù)，主函數(shù)為：在命令窗口輸入：>>[a,b]=queen(4)a=2b=24133142在命令窗口輸入：>>[a,b]=queen(4)在命令窗口輸入：>>[a,b]=queen(5)a=10b=13524142532413525314314253524141352425315241353142在命令窗口輸入：>>[a,b]=queen(5)function[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);這是主函數(shù)，定義了三個全局變量，便于程序間傳遞數(shù)據(jù)。其中CURROW保存當(dāng)前正在搜索的行。search是自定義的子函數(shù)，end用來指示當(dāng)前維的最后一個腳標(biāo)。function[num,scheme]=Queen(functionsearch()globalSCHEME_MATRIXNCURROWfori=1:N%在當(dāng)前行逐列搜索ifcheckchess(CURROW,i)%滿足放置條件SCHEME_MATRIX(end,CURROW)=i;%在當(dāng)前行放入皇后if(CURROW<N)CURROW=CURROW+1;search;%進(jìn)入下一行搜索else%已在最后一行放入皇后，添加新的方案行SCHEME_MATRIX=[SCHEME_MATRIX;SCHEME_MATRIX(end,:)];break;endendendCURROW=CURROW-1;%回溯到上一行,繼續(xù)搜索functionsearch()functionresu