程序的設(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 木棍問(wèn)題作業(yè)2搜索搜索：高級(jí)枚舉有順序有策略地枚舉狀態(tài)空間中的結(jié)點(diǎn)，尋找問(wèn)題的解3搜索POJ1077八數(shù)碼問(wèn)題：經(jīng)典搜索問(wèn)題有一個(gè)3*3的棋盤(pán)，其中有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)（問(wè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)問(wèn)題：在深度優(yōu)先搜索中，若狀態(tài)空間的圖結(jié)構(gòu)不要顯式的存下來(lái)，該如何處理？12深度優(yōu)先搜索深度優(yōu)先搜索的遞歸框架在深度優(yōu)先搜索中，狀態(tài)空間的圖結(jié)構(gòu)并不一定需要顯式的存下來(lái)。type node;void DFS(int depth)for(node的每一個(gè)可行變化)改變node;DFS(depth + 1);恢復(fù)node;此種做法需要一個(gè)全局?jǐn)?shù)組array來(lái)存放每個(gè)走過(guò)的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判重需要考慮的問(wèn)題狀態(tài)數(shù)目巨大，如何存儲(chǔ)？怎樣才能較快的找到重復(fù)結(jié)點(diǎn)？時(shí)間空間15判重合理編碼，減小存儲(chǔ)代價(jià)不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別82341657方案一：每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)九進(jìn)制數(shù)，則4個(gè)字節(jié)就能表示一個(gè)結(jié)點(diǎn)。（ 99=387,420,489）判重需要一個(gè)標(biāo)志位序列，每個(gè)狀態(tài)對(duì)應(yīng)于標(biāo)志位序列中的1位，標(biāo)志位為0表示該狀態(tài)尚未擴(kuò)展，為1則說(shuō)明已經(jīng)擴(kuò)展過(guò)了標(biāo)志位序列可以用字符數(shù)組存放。數(shù)組的每個(gè)元素存放8個(gè)狀態(tài)的標(biāo)志位。位序列最多需要99位，因此存放位序列的

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

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

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

10、OJ1164輸入：程序從標(biāo)準(zhǔn)輸入設(shè)備讀入數(shù)據(jù)。第一行是兩個(gè)整數(shù)，分別是南北向、東西向的方塊數(shù)。在接下來(lái)的輸入行里，每個(gè)方塊用一個(gè)數(shù)字(0p50)描述。用一個(gè)數(shù)字表示方塊周?chē)膲Γ?表示西墻，2表示北墻，4表示東墻，8表示南墻。每個(gè)方塊用代表其周?chē)鷫Φ臄?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解題思想對(duì)任意的方塊(i,j)，在輸入描述中用p表示p8 (i,j)沒(méi)有南墻,(i+1,j)與(i,j)屬于同一房間所有與(i+1,j) 屬于同一房間的方塊也與(i,j)屬于同一房間p%84 (i,j)沒(méi)有東墻， (i,j+1)與(i,j)屬于同一房間所有與(i,j+1)屬于同一房間的方塊也與(i,j)屬于同一房間p%42(i,j) 沒(méi)有北墻 ，(i-1,j)與(i,j)屬于同一房間所有與(i-1,j)屬于同一房間的方塊也與(i,j)屬于同一房間p%2=0 (i,j)沒(méi)有西墻，(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í)房間是否被訪問(wèn)過(guò)void markRoom(int x,int y);/搜尋與(x,y)屬于同一房間的方塊30問(wèn)題如何設(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：木棒問(wèn)題(POJ1011)問(wèn)題描述：?jiǎn)讨文脕?lái)一組等長(zhǎng)的木棒，將它們隨機(jī)地裁斷，使得每一節(jié)木棒的長(zhǎng)度都不超過(guò)50個(gè)長(zhǎng)度單位。然后他又想把這些木棒恢復(fù)到為裁截前的狀態(tài)，但忘記了木棒的初始長(zhǎng)度。請(qǐng)你設(shè)計(jì)一個(gè)程序，幫助喬治計(jì)算木棒的可能最小長(zhǎng)度。每一節(jié)木棒的長(zhǎng)度都用大于零的整數(shù)表示輸入：由多個(gè)案例組成，每個(gè)案例包括兩行。第一行是一個(gè)不超過(guò)64的整數(shù)，表示裁截之后共有多少節(jié)木棒。第二行是經(jīng)過(guò)裁截后，所得到的各節(jié)

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

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

17、部分的最后一節(jié)木棒37程序?qū)崿F(xiàn)boolDfs(int nUnusedSticks, int nLeft ) ;表示: 當(dāng)前有nUnusedSticks根未用木棒，而且當(dāng)前正在拼的那根棍子比假定的棍子長(zhǎng)度短了nLeft, 那么在這種情況下能全部否拼成功。38程序?qū)崿F(xiàn)Dfs的基本遞推關(guān)系：boolDfs(int nUnusedSticks, int nLeft) .找一根長(zhǎng)度不超過(guò)nLeft的木棒(假設(shè)長(zhǎng)為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;/說(shuō)明不能用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 比還缺的長(zhǎng)度if( nUnusedSticks = 0 & nLeft = 0 )return true;if( nLeft = 0 ) /一根剛剛拼完nLeft = L; /開(kāi)始拼新的一根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;/說(shuō)明不能用i作為/第條，/那么