noip2014夏令營-搜索及優(yōu)化

搜索及優(yōu)化山東省青島第二中學(xué)鄭遠(yuǎn)航2014.7.17一、深度優(yōu)先搜索例1：一個(gè)n*m*k的長方體，在長方體的6個(gè)面上有兩個(gè)特殊方格，一個(gè)是入口，一個(gè)是出口?，F(xiàn)在要使用不超過6個(gè)下圖所示的L型彎管在長方體內(nèi)部進(jìn)行連接，要求從入口連接到出口。問是否可能，如果可能，問最少需要幾根彎管。一、深度優(yōu)先搜索深度優(yōu)先搜索的優(yōu)化1.剪枝(1)可行性剪枝(2)最優(yōu)性剪枝2.搜索順序的確定3.迭代加深搜索一、深度優(yōu)先搜索1.剪枝(1)可行性剪枝當(dāng)搜索到某一狀態(tài)時(shí)，發(fā)現(xiàn)這一狀態(tài)后面的狀態(tài)都不可行，則不繼續(xù)搜索該狀態(tài)。(2)最優(yōu)性剪枝當(dāng)搜索到某一狀態(tài)時(shí)，發(fā)現(xiàn)這一狀態(tài)后面的狀態(tài)無論如何都不可能達(dá)到當(dāng)前的最優(yōu)解，則不繼續(xù)搜索該狀態(tài)。一、深度優(yōu)先搜索例2：有N種套餐，每種套餐都有自己的價(jià)格Ai。M個(gè)人，每個(gè)人都要一份套餐。其中第i個(gè)人要第j種套餐可以得到的人品值為Bij?，F(xiàn)在有k元錢，如果必須給每個(gè)人買一份套餐，問可以得到的人品值的最大值是多少。(N<=10,M<=15,k<=109)一、深度優(yōu)先搜索例3：N個(gè)隊(duì)伍進(jìn)行循環(huán)賽，勝者得3分，負(fù)者得0分。如果兩個(gè)隊(duì)出現(xiàn)平局則各得1分?，F(xiàn)在給出循環(huán)賽的最終得分情況，問可能的比賽結(jié)果情況有多少種？(N<=8)例如一共有3個(gè)隊(duì)伍，最終得分為3,3,3，則比賽結(jié)果情況可能有兩種：(1)隊(duì)伍1勝隊(duì)伍2，隊(duì)伍2勝隊(duì)伍3，隊(duì)伍3勝隊(duì)伍1；(2)隊(duì)伍1勝隊(duì)伍3，隊(duì)伍2勝隊(duì)伍1，隊(duì)伍3勝隊(duì)伍2。一、深度優(yōu)先搜索例4：有一個(gè)N*M的方格網(wǎng)，左下角為(0,0)，右上角為(N-1,M-1)。在方格網(wǎng)中有3個(gè)檢查點(diǎn)（這3個(gè)檢查點(diǎn)在不同的位置）。有一個(gè)人要從(0,0)經(jīng)過一邊所有格子，最終走到(0,1)。但是有一個(gè)特殊要求：在第(n*m*i/4)步（如果不能整除時(shí)下取整）時(shí)必須在第i個(gè)檢查點(diǎn)。求方案數(shù)。一、深度優(yōu)先搜索例5：一個(gè)N*M的方陣，每個(gè)格子填了一個(gè)小于P的非負(fù)整數(shù)，設(shè)這個(gè)矩陣為A。有一個(gè)新的N*M的方陣，它的元素B(i,j)=A(i,j)+A(i-1,j)+A(i,j-1)+A(i-1,j-1)，其中i>1，j>1。而B(1,j)=B(i,1)=0。給定B矩陣，求一個(gè)可能的字典序最小的A矩陣。N,M<=200。一、深度優(yōu)先搜索2.搜索順序的確定好的搜索順序有時(shí)可以使程序運(yùn)行速度提升。一、深度優(yōu)先搜索例6：給定16個(gè)整數(shù)，要求將它們排列成一個(gè)4階幻方?；梅降亩x為：一個(gè)方陣，每行、每列及兩條對(duì)角線上的數(shù)之和均相等。一、深度優(yōu)先搜索3.迭代加深搜索對(duì)于一些搜索問題，我們可以先確定最大搜索深度，然后再搜索。如果不行，再次確定深度，繼續(xù)搜索，直到搜索到答案為止。一、深度優(yōu)先搜索例7：單位分?jǐn)?shù)是指分子為1，分母為正整數(shù)的數(shù)?，F(xiàn)在給定分?jǐn)?shù)a/b(0<a<b<1000)，要求用數(shù)量最少的不同的單位分?jǐn)?shù)之和表示a/b，如果兩個(gè)方案數(shù)量相同，則最小的那個(gè)單位分?jǐn)?shù)最大的方案最好。求出最好的方案。一、深度優(yōu)先搜索例如19/45=1/3+1/12+1/18019/45=1/3+1/15+1/4519/45=1/3+1/18+1/3019/45=1/4+1/6+1/18019/45=1/5+1/6+1/18其中最好的是最后一種，因?yàn)?/18比1/180、1/45、1/30、1/180都要大。一、深度優(yōu)先搜索例8：有M根木板，其中第i根木板的長度為ai?，F(xiàn)在需要N根木板，其中需要的第i根木板長度為bi?？梢詫⒃械哪景迳锨邢滦枰哪景?。問最多可以切出多少根需要的木板。M<=50,N<=1000。二、廣度優(yōu)先搜索例9：一個(gè)4*4的方格網(wǎng)，每個(gè)格子中的顏色為黑色或白色。每次操作可以選擇一個(gè)格子，將它和與它有公共邊的格子的顏色改變（黑->白，白->黑）。問把所有格子的顏色都變成白色最少需要多少步。二、廣度優(yōu)先搜索廣度優(yōu)先搜索的優(yōu)化1.A*2.雙向廣度優(yōu)先搜索二、廣度優(yōu)先搜索1.A*A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為：f(n)=g(n)+h(n)，其中f(n)表示從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(n)表示在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)表示從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。二、廣度優(yōu)先搜索2.雙向廣度優(yōu)先搜索有時(shí)廣度優(yōu)先搜索的搜索空間過大，可以采用雙向廣度優(yōu)先搜索的方法。每次可以從起點(diǎn)那一邊或者終點(diǎn)那一邊擴(kuò)展，直到兩邊相遇位置。實(shí)際上每次從節(jié)點(diǎn)數(shù)少的那一邊擴(kuò)展是更好的。二、廣度優(yōu)先搜索例10：有一個(gè)如圖1的玩具。圖1二、廣度優(yōu)先搜索將它的左邊的輪子順時(shí)針旋轉(zhuǎn)一次，可以得到圖2所示