【正文】 (4,2) (5,2) (1,5) (2,5) (1,4) 圖 基于堆棧的回溯算法與克里特算法相比 （ 1）往棧中壓入一個(gè)節(jié)點(diǎn)，就說明該節(jié)點(diǎn)可達(dá)，相當(dāng)于鋪了第 1條線。 （ 2）將棧頂節(jié)點(diǎn)彈出，說明該節(jié)點(diǎn)是死節(jié)點(diǎn)，相當(dāng)于鋪了第 2條線。 2. 定義數(shù)據(jù)結(jié)構(gòu) 基于棧的迷宮探索，需要建立兩種基本的數(shù)據(jù)結(jié)構(gòu)： 這里首先考慮如何建立基于數(shù)組的堆棧。 int Si=1,Sj=1,Ei=5,Ej=5。 /* 節(jié)點(diǎn)位置 */ int nodeState。 typedef struct ExploreStack { MAZE_NODE explStack[N]。 3. 算法設(shè)計(jì)初步 （ 1）擴(kuò)展棧頂節(jié)點(diǎn)的算法 void mazeExpand(EXP_STACK *s ) { 獲取棧頂節(jié)點(diǎn)在迷宮中的坐標(biāo) x,y。 } else if(棧頂節(jié)點(diǎn)位于出口 ) { printf(“探察結(jié)束，探察過程如下：“ )； return。 將此節(jié)點(diǎn)周圍值為 0（不是墻以及未壓過棧）的節(jié)點(diǎn)壓棧，同時(shí)將它們的置1； } 重新獲取棧頂節(jié)點(diǎn)進(jìn)行拓展； } 程序框架 （ 2）程序框架 定義迷宮矩陣為靜態(tài)數(shù)組 定義入口、出口坐標(biāo) 定義探索棧 定義棧的壓入函數(shù) 定義棧的彈出函數(shù) 定義棧頂節(jié)點(diǎn)擴(kuò)展函數(shù) 定義迷宮矩陣打印函數(shù) void main() { 從入口節(jié)點(diǎn)開始調(diào)用棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)； 調(diào)用迷宮矩陣打印函數(shù)； } 4. 程序設(shè)計(jì) （ 1） push操作和 pop操作 /*在 */ int top=1。 MAZE_NODE *pop(EXP_STACK *s) /*pop操作 */ { MAZE_NODE *npop。 exit(1)。 top = top 1。 } } （ 1） push操作和 pop操作（續(xù)） /*在 */ int top=1。 MAZE_NODE *pop(EXP_STACK *s) /*pop操作 */ { MAZE_NODE *npop。 exit(1)。 top = top 1。 } } （ 2）棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)設(shè)計(jì) /*在 */ int Ei=5,Ej=5。 /* 引用性聲明 */ MAZE_NODE *new1。 MAZE_NODE end。 /* 出口的設(shè)置 */ =Ej。 if(top ==1) /* 探索?？?*/ { printf(\n此迷宮找不到出口，探索過程如下： \n)。 } （ 2）棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)設(shè)計(jì)（續(xù)） else { if((*old).x==amp。(*old).y==) /* 判斷是否為出口 */ { printf(\n探察結(jié)束，探察過程如下： \n)。 } else { i=(*old).x。 if(maze[i1][j]==2 amp。 maze[i][j+1]==2 amp。 maze[i+1][j]==2) { /* 本節(jié)點(diǎn)為死點(diǎn)：狀態(tài)置為 2，并擴(kuò)展新棧頂節(jié)點(diǎn) */ (*old).nodeState=2。mazeExpand(pop(s))。 } （ 2）棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)設(shè)計(jì)（續(xù)） else if(maze[i][j+1]==2 amp。 maze[i+1][j]==2 amp。 maze[i][j1]==2) { (*old).nodeState=2。 mazeExpand(pop(s))。 } else if(maze[i+1][j]==2 amp。 maze[i][j1]==2 amp。 maze[i1][j]==2) { (*old).nodeState=2。 mazeExpand(pop(s))。 } else if(maze[i][j1]==2 amp。 maze[i1][j]==2 amp。 maze[i][j+1]==2) { (*old).nodeState=2。 mazeExpand(pop(s))。 } （ 2）棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)設(shè)計(jì)（續(xù)） else { maze[i][j]=1。 /* 不是死點(diǎn) ,則壓入棧 */ /*針對(duì)不同情況，分別進(jìn)行處理壓棧 */ if(maze[i1][j]==0) { (*new1).x=i1。 (*new1).nodeState=1。 push(new1)。 (*new1).y=j+1。 maze[i][j+1]=1。 } （ 2）棧頂節(jié)點(diǎn)擴(kuò)展函數(shù)設(shè)計(jì)（續(xù)） if(maze[i+1][j]==0) { (*new1).x=i+1。 (*new1).nodeState=1。 push(new1)。 (*new1).y=j1。 maze[i][j1]=1。 } } }/*else*/ } mazeExpand(pop(s))。 printf(\n)。i=6。j=6。 printf(\n)。 /* 初始化迷宮矩陣 */ int Si=1,Sj=1。 main() { (*start).x=Si。 /* 入口的初始化 */ (*start).nodeState=1。 push(start)。 /* 從入口節(jié)點(diǎn)開始調(diào)用棧頂節(jié)點(diǎn)擴(kuò)展函數(shù) */ prnt()。在穿梭過河的過程中，若留在岸上的猴子數(shù)多于人數(shù)，猴子就會(huì)逃跑。 2. 自然數(shù)的拆分：任何一個(gè)大于 1的自然數(shù) N，總可以拆分為若干個(gè)自然數(shù)之和，并且有多種拆分方法。 五、編程練習(xí)（續(xù)） 3. 機(jī)器設(shè)計(jì)問題：某機(jī)器由 n 個(gè)部件組成，每一個(gè)部件可從 3個(gè)投資者那里獲得。編寫一個(gè)回溯算法，找出耗費(fèi)不超過 c的機(jī)器構(gòu)成方案，使其重量最少。若每個(gè)信封上至多只允許貼 m枚郵票。如，對(duì)于 n=4， m=5，有面值 (1， 4， 12， 21)四種郵票。 5. 控制方格棋盤游戲：如 圖 5 5的方格棋盤，若在某一方格內(nèi)放入一個(gè)黑子，則與該方格相鄰的上、下、左、右 4各方格中都不可再放黑子。請(qǐng)?jiān)O(shè)計(jì)在棋盤上放 7個(gè)黑子就可以控制整個(gè)棋盤的所有方案。它由 8塊同樣大小的方塊組成，這 8個(gè)方塊分別涂以不同的顏色或編號(hào)。應(yīng)用三種基本操作，可以由一種狀態(tài)到達(dá)另一種狀態(tài)。 五、編程練習(xí)（續(xù)） 7. 四色問題：在彩色地圖中，相鄰區(qū)塊要用不同的顏色表示。為了證實(shí)這一猜想，許多科學(xué)家付出了艱巨的勞動(dòng)，但一直沒有成功。 請(qǐng)按四色定理為 圖 。也就是說，貪心策略總是不斷地將原問題變成一個(gè)相似、而規(guī)模更小的問題，然后做出當(dāng)前看似最好的 ——局部意義上的最優(yōu)選擇 。但是許多情況下，用貪心策略可以得到最優(yōu)解的接近結(jié)果。 旅行費(fèi)用問題 一、問題描述 一個(gè)游客要到如 圖 （ a） 所示的 A、 B、 C、 D、 E五個(gè)景點(diǎn)旅行。試問，該游客從 A出發(fā)，如何以最小費(fèi)用走過每一個(gè)景點(diǎn)最后返回 A？ A E D C B 50 30 80 30 20 12 43 10 36 21 圖 （ a）旅行費(fèi)用拓?fù)? 二、解題策略 按照貪心策略，在局部尋優(yōu)的過程可以用 圖 （ b） 表示，得到的路徑為 ABECDA，總費(fèi)用為 10+30+20+12+80=152。因?yàn)?，最?yōu)路徑為 ABEDCA，總費(fèi)用為 10+30+30+12+21=103。 （ 2）定義枚舉變量 enum scenes{a,b,c,d,e}。 i= n1。 enum scenes{a,b,c,d,e} 。 enum scenes start,j。 int flag[N]={0,0,0,0,0}。 v=a。 三、程序的實(shí)現(xiàn)（續(xù)） for(i=1。i++) { min=65535。j=N1。amp。 s=j。 flag[v]=1。 /* 新的起點(diǎn) */ } sum=sum+expense[v][start]。 } 四、程序測(cè)試 （ 1）測(cè)試 1 當(dāng) v=a時(shí)， sum=152 （ 2）測(cè)試 2 當(dāng) v=b時(shí)， sum=103 （ 3）測(cè)試 3 當(dāng) v=c時(shí)， sum=103 五、編程練習(xí) 用貪心法求解下列問題，并分析這些問題用貪心法能否得到整體最優(yōu)解。強(qiáng)盜只有一個(gè)最多只能裝 W斤的背包。該商店中有 N件物品，每件物品的重量和價(jià)值都是不一樣的：第 i件物品值 vi元，重 wi斤（ 1≤i≤N）。 子問題 1：當(dāng)每一件物品都不可分割時(shí)，強(qiáng)盜只能對(duì)某件物品選擇帶走，還是不帶走。 子問題 2：當(dāng)每一件物品都可分割時(shí)，強(qiáng)盜只能對(duì)某件物品選擇帶走，還是不帶走。 要求分別考慮下列策略： （ 1）每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？ （ 2）每次挑選所占空間最輕的物品裝入，是否能得到最優(yōu)解？ （ 3）每次選取單位容量?jī)r(jià)值最大的物品，成為解本題的策略。若要找給顧客的錢為 x，如何找，拿出的硬幣個(gè)數(shù)最少？ 例如： n=4， c1=2 c2= c3= c4= x=67. 3. 古代埃及人有一個(gè)非常奇怪的習(xí)慣，他們喜歡把一個(gè)分?jǐn)?shù)表示為若干個(gè)分子為 1的分?jǐn)?shù)之和的形式，如： 7/8=1/2+1/3+1/24。試給出把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的算法。 刪數(shù)問題 一、問題描述 由鍵盤輸入一個(gè)長(zhǎng)整數(shù) N（不超過 240位），去掉其中的任意 S個(gè)數(shù)字，剩下的數(shù)字按原來的左右順序組成一個(gè)新的整數(shù)。要求輸出無空格的數(shù)字串。但是， C語言中長(zhǎng)整數(shù)（ long int）的十進(jìn)制最大長(zhǎng)度是 19位（ 32位系統(tǒng)）。每一個(gè)數(shù)組元素中包含一個(gè) 4位十進(jìn)制數(shù)。 2. 選擇貪心策略 （ 1）從數(shù)字串中的最左端的一個(gè)遞減區(qū)間，刪去該區(qū)間的首字符。 2 7 6 8 5 9 2 3 2 6 8 5 9 2 3 2 6 5 9 2 3 2 5 9 2 3 2 5 2 3 2 2 3 （ 2）無遞減空間，則刪除最后一個(gè)數(shù)字。 char * strTemp。j0。istrlen(digitStr)2。 /* 刪除第 i個(gè)數(shù)字 */ flag =1。 } } if(flag= =0) /* 無遞減空間 */ *（ digitStr+(strlen(digitStr)1)） =’\0’。\039。 } 四、說明 一般來說，適合貪心策略的問題大多數(shù)具有兩個(gè)特征： （ 1）貪心選擇性質(zhì) 貪心選擇性質(zhì)就是可以通過局部最優(yōu)選擇達(dá)到全局最優(yōu)。例如本題中，當(dāng)前要?jiǎng)h除的數(shù)不依賴于將來要?jiǎng)h除的數(shù)，只考慮當(dāng)前最優(yōu)。例如本題中的數(shù) 27685923，要?jiǎng)h去 4個(gè)數(shù)字，肯定要?jiǎng)h去‘ 768’和‘ 9’。即問題的最優(yōu)解包含了 4個(gè)子問題的解。 void getMinInteger(char * digitStr,int n)。 char * strTemp。j0。 for(i=0。i++) /* 搜索遞減空間 */ { if(*(digitStr+i)*(digitStr+i+1)) /* 存在遞減空間 */ { striDel(digitStr,i)。 break。\039。\039。 } main( ) { char *digitStr。 printf(請(qǐng)輸入一個(gè)數(shù)字串： )。 printf(請(qǐng)輸入需刪除數(shù)字個(gè)數(shù)： )。n)。 printf(%s,digitStr)。 2. 汽車加油問題：某汽車加滿一次油后可以行駛 n公里路程。 要求：沿途加油次數(shù)最少。 輸出：汽車加油的加油站序列號(hào)。任務(wù)可以在機(jī)器上處理。 在可行分配中每臺(tái)機(jī)器在任何時(shí)刻最多處理一個(gè)任務(wù)。請(qǐng)就本題給出的條件，求出最優(yōu)分配。每步分配一件任務(wù)，且按任務(wù)開始時(shí)間的非遞減次序進(jìn)行分配。在選擇機(jī)器時(shí)，采用以下貪婪準(zhǔn)則：根據(jù)欲分配任務(wù)的開始時(shí)間，若此時(shí)有舊的機(jī)器可用，則將任務(wù)分給舊的機(jī)器。 如 圖 ，根據(jù)本