程序的設(shè)計(jì)實(shí)習(xí)課程-PPT課件

1、程序設(shè)計(jì)實(shí)習(xí)第八講 搜索主講教師：田永鴻/cpp2019/tyh//jiaoxue-CPP/cpp08.htm2019年3月19日1學(xué)習(xí) 教程 教材 多媒體課件【友情分享】GOOD GOOD STUDAY, DAY DAY UP內(nèi)容提要搜索廣度優(yōu)先搜索深度優(yōu)先搜索影響搜索效率的因素POJ 1011 木棍問題作業(yè)2搜索搜索：高級(jí)枚舉有順序有策略地枚舉狀態(tài)空間中的結(jié)點(diǎn)，尋找問題的解3搜索POJ1077八數(shù)碼問題：經(jīng)典搜索問題有一個(gè)3*3的棋盤，其中有0-8 9個(gè)數(shù)字，0表示空格，其他的數(shù)字可以和0交換位置。求由初始狀

2、態(tài)1 2 34 5 67 8 0到達(dá)目標(biāo)狀態(tài)步數(shù)最少的解？ 12345678823146574搜索狀態(tài)空間82341657823415768234165 78241357682341576823416575廣度優(yōu)先搜索廣度優(yōu)先搜索優(yōu)先擴(kuò)展淺層結(jié)點(diǎn)，逐漸深入第一層第二層第三層8234165782341576823416578241357682341576823416576廣度優(yōu)先搜索廣度優(yōu)先搜索用隊(duì)列保存待擴(kuò)展的結(jié)點(diǎn)，從隊(duì)首隊(duì)取出結(jié)點(diǎn)，擴(kuò)展出的新結(jié)點(diǎn)放入隊(duì)尾，直到找到目標(biāo)結(jié)點(diǎn)（問題的解）82341657823415768241357682341576823416577廣度優(yōu)先搜索廣度優(yōu)先搜索的代

3、碼框架BFS()初始化隊(duì)列while(隊(duì)列不為空且未找到目標(biāo)結(jié)點(diǎn))取隊(duì)首結(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的結(jié)點(diǎn)放入隊(duì)尾8深度優(yōu)先搜索深度優(yōu)先搜索優(yōu)先深入遍歷靠前的結(jié)點(diǎn)82341657823415768234165078241357682341576823416579深度優(yōu)先搜索深度優(yōu)先搜索可以用棧實(shí)現(xiàn)，在棧中保存從起始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)一般用遞歸實(shí)現(xiàn)10深度優(yōu)先搜索深度優(yōu)先搜索的非遞歸框架DFS()初始化棧while(棧不為空 且 未找到目標(biāo)結(jié)點(diǎn))取棧頂結(jié)點(diǎn)擴(kuò)展，擴(kuò)展出的結(jié)點(diǎn)放回棧頂11深度優(yōu)先搜索深度優(yōu)先搜索的遞歸框架DFS(type cur_node, int depth)for(cur

4、_node的每個(gè)子結(jié)點(diǎn)child_node)DFS(child_node, depth+1)問題：在深度優(yōu)先搜索中，若狀態(tài)空間的圖結(jié)構(gòu)不要顯式的存下來，該如何處理？12深度優(yōu)先搜索深度優(yōu)先搜索的遞歸框架在深度優(yōu)先搜索中，狀態(tài)空間的圖結(jié)構(gòu)并不一定需要顯式的存下來。type node;void DFS(int depth)for(node的每一個(gè)可行變化)改變node;DFS(depth + 1);恢復(fù)node;此種做法需要一個(gè)全局?jǐn)?shù)組array來存放每個(gè)走過的node，arraydepth就是進(jìn)入DFS函數(shù)時(shí)需要擴(kuò)展的節(jié)點(diǎn)13判重判重新擴(kuò)展出的結(jié)點(diǎn)如果和以前擴(kuò)展出的結(jié)點(diǎn)相同，則則個(gè)新節(jié)點(diǎn)就不必再

5、考慮如何判重？重復(fù)?823416578234157682341650782413576823415768234165714判重需要考慮的問題狀態(tài)數(shù)目巨大，如何存儲(chǔ)？怎樣才能較快的找到重復(fù)結(jié)點(diǎn)？時(shí)間空間15判重合理編碼，減小存儲(chǔ)代價(jià)不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別82341657方案一：每個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)九進(jìn)制數(shù)，則4個(gè)字節(jié)就能表示一個(gè)結(jié)點(diǎn)。（ 99=387,420,489）判重需要一個(gè)標(biāo)志位序列，每個(gè)狀態(tài)對應(yīng)于標(biāo)志位序列中的1位，標(biāo)志位為0表示該狀態(tài)尚未擴(kuò)展，為1則說明已經(jīng)擴(kuò)展過了標(biāo)志位序列可以用字符數(shù)組存放。數(shù)組的每個(gè)元素存放8個(gè)狀態(tài)的標(biāo)志位。位序列最多需要99位，因此存放位序列的

6、數(shù)組需要99/8 個(gè)字節(jié)如果某個(gè)狀態(tài)對應(yīng)于一個(gè)9進(jìn)制數(shù)a,則其標(biāo)志位就是標(biāo)志位序列中的第a位（其所屬的數(shù)組元素下標(biāo)是a/8)16判重合理編碼，減小存儲(chǔ)代價(jià)不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別82341657方案一：每個(gè)節(jié)點(diǎn)對應(yīng)于一個(gè)九進(jìn)制數(shù)，則4個(gè)字節(jié)就能表示一個(gè)節(jié)點(diǎn)。此方案需要編寫字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。17判重合理編碼，減小存儲(chǔ)代價(jià)不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別82341657方案二：為結(jié)點(diǎn)編號(hào)把每個(gè)結(jié)點(diǎn)都看一個(gè)排列，以此排列在全部排列中的位置作為其編號(hào)排列總數(shù)：9!=362880只需要一個(gè)整數(shù)(4字節(jié))即可存下一個(gè)結(jié)點(diǎn)判重用的標(biāo)志數(shù)組只需要3628

7、80字節(jié)即可。此方案比方案1省空間此方案需要編寫給定排列求序號(hào)和給定序號(hào)求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。18判重時(shí)間與空間的權(quán)衡對于狀態(tài)數(shù)較小的問題，可以用最直接的方式編碼以空間換時(shí)間對于狀態(tài)數(shù)太大的問題，需要利用好的編碼方法以時(shí)間換空間具體問題具體分析19廣搜與深搜的比較廣搜一般用于狀態(tài)表示比較簡單、求最優(yōu)策略的問題需要保存所有擴(kuò)展出的狀態(tài)，占用的空間大每次擴(kuò)展出結(jié)點(diǎn)時(shí)所走過的路徑均是最短路深搜幾乎可以用于任何問題只需要保存從起始狀態(tài)到當(dāng)前狀態(tài)路徑上的結(jié)點(diǎn)根據(jù)題目要求憑借自己的經(jīng)驗(yàn)和對兩個(gè)搜索的熟練程度做出選擇20影響搜索效率的因素影響搜索效

8、率的因素搜索對象(枚舉什么）搜索順序（先枚舉什么，后枚舉什么）剪枝(及早判斷出不符合要求的情況）21搜索一種解決問題的方法，與枚舉的思想類似。例如：求從北大到北京站的最短行車距離，假設(shè)只能走北京市五環(huán)以及五環(huán)以內(nèi)的道路。有很多種走法從北大東門出來，有三條路：城府路、沿白頤路向南、沿白頤路向北沿白頤路向南走到北四環(huán)路口又有三種選擇：繼續(xù)往南、沿北四環(huán)向東、沿北四環(huán)向西。22搜索從北大到北京站的最短行車距離假設(shè)的條件表明，只有有限種可能的走法解決方法：列出每一種可能的路徑：確定了搜索的空間對每一種可能的路徑，分別計(jì)算行車距離從中找到最短的行車距離2324搜索的思想：遍歷根據(jù)所知道的知識(shí)，依次猜測各

9、個(gè)可能的答案。對每個(gè)可能的答案進(jìn)行評(píng)估，確定所需要的答案進(jìn)行新的猜測時(shí)：從兩個(gè)方面利用已經(jīng)完成的猜測的結(jié)果將正在進(jìn)行的猜測與已經(jīng)完成的猜測進(jìn)行比較，及早結(jié)束“無用”的猜測。從北大出發(fā)，所走的車程已經(jīng)超過已經(jīng)發(fā)現(xiàn)的路徑的長度利用已經(jīng)完成的猜測，快速生成新的猜測。已經(jīng)找到一條從北大到北京站的路徑，改變該路徑上某個(gè)叉路口的選擇可以得到新的路徑。新路徑與原路徑的開始一段是相同的，包括從北大到該叉路口25程序設(shè)計(jì)練習(xí)1：城堡問題(POJ1164)問題描述：圖1是一個(gè)城堡的地形圖。請你編寫一個(gè)程序，計(jì)算城堡一共有多少房間最大的房間有多大城堡被分割成mn(m50，n50)個(gè)方塊，每個(gè)方塊可以有04面墻26P

10、OJ1164輸入：程序從標(biāo)準(zhǔn)輸入設(shè)備讀入數(shù)據(jù)。第一行是兩個(gè)整數(shù)，分別是南北向、東西向的方塊數(shù)。在接下來的輸入行里，每個(gè)方塊用一個(gè)數(shù)字(0p50)描述。用一個(gè)數(shù)字表示方塊周圍的墻，1表示西墻，2表示北墻，4表示東墻，8表示南墻。每個(gè)方塊用代表其周圍墻的數(shù)字之和表示。城堡的內(nèi)墻被計(jì)算兩次，方塊(1,1)的南墻同時(shí)也是方塊(2,1)的北墻。輸入的數(shù)據(jù)保證城堡至少有兩個(gè)房間輸出：城堡的房間數(shù)、城堡中最大房間所包括的方塊數(shù)。結(jié)果顯示在標(biāo)準(zhǔn)輸出設(shè)備上。27POJ1164樣例輸入4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8

11、10 12 13 樣例輸出5928解題思想對任意的方塊(i,j)，在輸入描述中用p表示p8 (i,j)沒有南墻,(i+1,j)與(i,j)屬于同一房間所有與(i+1,j) 屬于同一房間的方塊也與(i,j)屬于同一房間p%84 (i,j)沒有東墻， (i,j+1)與(i,j)屬于同一房間所有與(i,j+1)屬于同一房間的方塊也與(i,j)屬于同一房間p%42(i,j) 沒有北墻 ，(i-1,j)與(i,j)屬于同一房間所有與(i-1,j)屬于同一房間的方塊也與(i,j)屬于同一房間p%2=0 (i,j)沒有西墻，(i,j-1)與(i,j)屬于同一房間所有與(i,j-1)屬于同一房間的方塊也與(i

12、,j)屬于同一房間29參考程序#include int r, c, p5050, rooms, max, modules;/r,c：南北向、東西向的方塊數(shù) /p5050：輸入的每個(gè)方塊的數(shù)字/rooms：城堡的房間數(shù)/max：最大房間的面積/modules：當(dāng)前房間的面積bool visit5050; /標(biāo)識(shí)房間是否被訪問過void markRoom(int x,int y);/搜尋與(x,y)屬于同一房間的方塊30問題如何設(shè)計(jì)void markRoom(int x,int y)函數(shù)？算法的復(fù)雜度是多少？31int main()while(scanf(%d %d,&r,&c)=2) rooms

13、=max=0;int i,j;for(i=0;ir;i+) for(j=0;jc;j+) scanf(%d,&pij);visitij=false;for(i=0;ir;i+) for(j=0;jmax)max=modules;printf(%dn%dn,rooms,max);return 0;32void markRoom(int x,int y)if(visitxy) return; else visitxy=true;modules+;if ( pxy8 ) markRoom(x+1, y);elsepxy = pxy%8;if ( pxy4 ) markRoom(x, y+1);els

14、epxy = pxy%4;if ( pxy2 ) markRoom(x-1, y);elsepxy = pxy%2;if ( pxy=0 ) markRoom(x, y-1);33程序設(shè)計(jì)練習(xí)2：木棒問題(POJ1011)問題描述：喬治拿來一組等長的木棒，將它們隨機(jī)地裁斷，使得每一節(jié)木棒的長度都不超過50個(gè)長度單位。然后他又想把這些木棒恢復(fù)到為裁截前的狀態(tài)，但忘記了木棒的初始長度。請你設(shè)計(jì)一個(gè)程序，幫助喬治計(jì)算木棒的可能最小長度。每一節(jié)木棒的長度都用大于零的整數(shù)表示輸入：由多個(gè)案例組成，每個(gè)案例包括兩行。第一行是一個(gè)不超過64的整數(shù)，表示裁截之后共有多少節(jié)木棒。第二行是經(jīng)過裁截后，所得到的各節(jié)

15、木棒的長度。在最后一個(gè)案例之后，是零。輸出：為每個(gè)案例，分別輸出木棒的可能最小長度。每個(gè)案例占一行。34解題思路初始狀態(tài)：有N節(jié)木棒最終狀態(tài)：這N節(jié)木棒恰好被拼接成若干根等長的木棒從初始狀態(tài)到最終狀態(tài)最多有多少條不同的“路徑”？Sum maxParts。其中Sum是全部N節(jié)木棒的長度之和，maxParts是最長一節(jié)木棒的長度每條“路徑”對應(yīng)一個(gè)木棒的長度。從木棒長度最小的那條可能“路徑”開始，如果成功地的找到了這條“路徑”，就解決了問題35解題思路構(gòu)造一條木棒長度為L的“路徑”：拼接木棒在未被拼接的木棒中，找出一節(jié)最長的，開始拼接從未拼接的木棒中，選擇一個(gè)長度合適的木棒，使得拼接后的木棒長度L

16、找到了在前面的拼接過程中曾試圖用過相同長度的一節(jié)其他木棒，但發(fā)現(xiàn)這樣拼接不成功，繼續(xù)尋找能夠進(jìn)行拼接的木棒把找到的那節(jié)木棒拼接上去。繼續(xù)進(jìn)行拼接繼續(xù)拼接成功，找到了“路徑”繼續(xù)拼接不成功，把剛拼接的那節(jié)木棒拿下來，繼續(xù)找下一個(gè)合適的未拼接木幫沒有找到：拼接失敗36已拼接部分未拼接部分長度為L的木棒長度為L1的未拼接木棒，共有N1根長度為L2的未拼接木棒，共有N2根長度為L3的未拼接木棒，共有N3根在已拼接部分未用長度為L1的木棒，則表明用長度為L1的木棒來拼接時(shí)是不成功的下次拼接時(shí)也不能選擇長度為L1的木棒，而應(yīng)該選擇長度為L2或L3的木棒如果長度為L2或L3的木棒也不能選擇，則需要替換已拼接

17、部分的最后一節(jié)木棒37程序?qū)崿F(xiàn)boolDfs(int nUnusedSticks, int nLeft ) ;表示: 當(dāng)前有nUnusedSticks根未用木棒，而且當(dāng)前正在拼的那根棍子比假定的棍子長度短了nLeft, 那么在這種情況下能全部否拼成功。38程序?qū)崿F(xiàn)Dfs的基本遞推關(guān)系：boolDfs(int nUnusedSticks, int nLeft) .找一根長度不超過nLeft的木棒(假設(shè)長為len，拼在當(dāng)前棍子上，然后return Dfs(nUnusedSticks 1,nLeft len );39程序?qū)崿F(xiàn)Dfs的終止條件：boolDfs(int nUnusedSticks, in

18、t nLeft ) if( nUnusedSticks = 0 & nLeft = 0)return true; 拼接嘗試處理return false;40程序?qū)崿F(xiàn)Dfs的剪枝處理：boolDfs(int nUnusedSticks, int nLeft ) for( int i = 0;i S;i +) if( !anUsedi & anLengthi 0 ) if( anUsedi-1 = false & anLengthi = anLengthi-1)continue; /剪枝3anUsedi = 1;if ( Dfs( nUnusedSticks - 1, nLeft - anLeng

19、thi)return true;else anUsedi = 0;/說明不能用i作為第條，那么要拆以前 /的棍子， i還可能用在以前的棍子里， /因此要anUsedi = 0;if( anLengthi = nLeft | nLeft = L) return false;/剪枝2、1.第一次剪枝處理第二次剪枝處理41#include #include #include int T, S;int L;int anLength65;int anUsed65;int i,j,k;int Dfs(int nUnusedSticks, int nLeft);int MyCompare( const vo

20、id * e1, const void * e2) int * p1, * p2;p1 = (int * ) e1;p2 = (int * ) e2;return * p2 - * p1;42main()while(1) cin S;if( S = 0 )break;int nTotalLen = 0;for( int i = 0; i anLengthi;nTotalLen += anLengthi;qsort(anLength,S,sizeof(int),MyCompare);43 for( L = anLength0; L = nTotalLen / 2; L + ) if( nTota

21、lLen % L)continue;memset( anUsed, 0,sizeof(anUsed);if( Dfs( S,L) cout L nTotalLen / 2 )cout nTotalLen endl; / while44int Dfs( int nUnusedSticks, int nLeft)/ nLeft表示當(dāng)前正在拼的棍子和 L 比還缺的長度if( nUnusedSticks = 0 & nLeft = 0 )return true;if( nLeft = 0 ) /一根剛剛拼完nLeft = L; /開始拼新的一根for( int i = 0;i S;i +) if( !anUsedi & anLengthi 0 ) if( anUsedi-1 = false & anLengthi = anLengthi-1)continue; /剪枝3anUsedi = 1;45if ( Dfs( nUnusedSticks - 1, nLeft - anLengthi)return true;else anUsedi = 0;/說明不能用i作為/第條，/那么