NOI導(dǎo)刊-搜索順序的選取與剪枝策略

搜索的剪枝策略與

搜索對(duì)象、搜索順序的選擇長(zhǎng)沙市雅禮中學(xué)朱全民條件1：V=nπH=m層形狀：每層都是一個(gè)圓柱體。條件2：設(shè)從下往上數(shù)第i(1<=i<=m)層蛋糕是半徑為Ri,高度為Hi的圓柱。當(dāng)i<m時(shí)，要求Ri>Ri+1且Hi>Hi+1。條件3：外表積Q最小，令Q=Sπ問(wèn)題：給出的n和m，找出蛋糕的制作方案〔適當(dāng)?shù)腞i和Hi的值〕，使S最小。(除Q外，以上所有數(shù)據(jù)皆為正整數(shù))輸入n(n<=10000)，m(m<=20)輸出S〔假設(shè)無(wú)解那么S=0〕。圓柱公式

V=πR2HS側(cè)=2πRHS底=πR2生日蛋糕〔NOI99〕解析法？

轉(zhuǎn)變思路，搜索？數(shù)據(jù)庫(kù) 用(i,Ri,Hi,Vi,Si)表示第i層蛋糕的一個(gè)狀態(tài)。其中Ri,Hi分別為第i層蛋糕的半徑和高，Vi,Si分別表示做完第i層蛋糕后剩下的蛋糕體積和當(dāng)前蛋糕的外表積?？梢?jiàn)，初始狀態(tài)：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)目標(biāo)狀態(tài)：(m,Rm,Hm,0,Sm) 于是，我們的目標(biāo)是找到一條從初始狀態(tài)到任意目標(biāo)狀態(tài)的路徑，并且Sm最小.擴(kuò)展的規(guī)那么 (i,Ri,Hi,Vi,Si)(i+1,Ri+1,Hi+1,Vi+1,Si+1) 滿足: 〔1〕Ri>Ri+1〔2〕Hi>Hi+1 〔3〕Vi+1=Vi-Ri+1*Ri+1*Hi+1〔4〕Si+1=Si+2*Ri+1*Hi+1確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件1〕是否做到了m層2〕是否最終體積為03〕是否當(dāng)前面積最小假設(shè)上述條件成立，那么保存當(dāng)前最優(yōu)值，否那么繼續(xù)做下一層蛋糕，假設(shè)重做蛋糕根本算法Search(i,Ri,Hi,Si,Vi){對(duì)每層蛋糕進(jìn)行搜索}if(i=m)and(Vi=0)then更新最優(yōu)值else forRi+1

Ri-1downtoi forHi+1

Hi-1downtoi[ Si+1

Si+2*Ri+1*Hi+1 Vi+1

Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]Problem-Cake {枚舉所有的初始狀態(tài)-----第一層蛋糕的大小}forR1mtosqrt(n)do/*假設(shè)H1=1，只做一層蛋糕*/ forH1ndiv(R1*R1)downtomdo[ S1=2*R1*H1+R1*R1 V1=n-R1*R1*H1 Search(1,R1,H1,S1,V1) ]優(yōu)化？？〔1〕因?yàn)橹烙嘞碌牡案怏w積,因此可以估算一下余下側(cè)面積,這樣我們可以就參加如下剪枝條件:if當(dāng)前的外表積+余下的側(cè)面積>當(dāng)前最優(yōu)值thenexit設(shè)已經(jīng)做了i層蛋糕,那么還需做m-i層,Si’：為第i層蛋糕的側(cè)面積,FSi：余下的側(cè)面積,怎么求FSi?因?yàn)?2Vi=2Ri+1*Ri+1*Hi+1+...+2Rm*Rm*Hm=Ri+1*Si+!’+...+Rm*Sm’≤Ri+1*(Si+1’+...+Sm’)=Ri+1*FSi所以:FSi≥2Vi/Ri+1因此剪枝條件為：ifSi-1+2*Vi-1/Ri>當(dāng)前最優(yōu)值thenexit優(yōu)化？？(2)如果剩下的蛋糕材料太少，不能保證做到m層,那么沒(méi)有必要繼續(xù)往下做了，設(shè)， 最m層半徑和高都為1，Rm=Hm=1

第m-1層半徑和高都為2，Rm-1=Hm-1=2…………

第i+1層半徑和高都為i,Ri=Hi=m–i

這樣，余下的m-i層的最小體積為

因此,剪枝條件為,ifVi<MINithenexit(3)如果剩下的蛋糕材料太多，以最大的方式做完m層,仍有材料剩余,那么沒(méi)有必要繼續(xù)往下做了，設(shè)， 第i+1層半徑和高分別為，Ri+1=Ri–

1

，Hi+1=Hi–1

第i+2層半徑和高分別為，Ri+2=Ri–2

，Hi+2=Hi–2

…………

第ｍ層半徑和高分別為，Ri+m=Ri–m

，Hi+m=Hi–m

這樣，余下的m-i層的最大體積為優(yōu)化？？因此,剪枝條件為,ifVi＞MAXi,R,Hthenexit計(jì)算MINifori1tondo[S

S+i*i*i;

MINm-i

S

]計(jì)算MAXi,R,HforR

1tosqrt(n)doforH

1tondiv(R*R)do[

S

0;forimdownto1do[

S

S+(R-i)*(R-i)*(H-i);

MAXi,R,H

S ] ]初始化Search(i,Ri,Hi,Si,Vi){對(duì)每層蛋糕進(jìn)行搜索}

ifSi+2*Vi/Ri>當(dāng)前最優(yōu)值thenexit;{剪枝1}ifVi<MINithenexit;{剪枝2}ifVi

＞MAXithenexit;{剪枝3}ifi<mthen forRi+1

Ridowntoi forHi+1min(Vidiv(Ri+1*Ri+1),Hi)downtoi[ Si+1

Si+2*Ri+1*Hi+1 Vi+1

Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]ElseifVi=0then更新最優(yōu)值Problem-Cake1.計(jì)算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假設(shè)H1=1，只做一層蛋糕*/3.forH1ndiv(R1*R1)downtomdo[4.S1=2*R1*H1+R1*R15. V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.]小節(jié)可行性剪枝剪枝2：ifVi<MINithenexit剪枝3：ifVi＞MAXi,R,Hthenexit最優(yōu)化剪枝剪枝1：ifSi-1+2*Vi-1/Ri>當(dāng)前最優(yōu)值thenexit剪枝原那么正確、高效埃及分?jǐn)?shù)在古埃及，人們使用單位分?jǐn)?shù)的和(形如1/a的,a是自然數(shù))表示一切有理數(shù)。如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因?yàn)榧訑?shù)中有相同的。對(duì)于一個(gè)分?jǐn)?shù)a/b,表示方法有很多種，但是哪種最好呢？首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?shù)越大越好。如：19/45=1/3+1/12+1/18019/45=1/3+1/15+1/4519/45=1/3+1/18+1/30,19/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都大。給出a,b(0<a<b<1000),編程計(jì)算最好的表達(dá)方式。輸入：ab輸出：假設(shè)干個(gè)數(shù)，自小到大排列，依次是單位分?jǐn)?shù)的分母。例如：輸入：1945輸出：5618分析1.節(jié)點(diǎn)類(lèi)型是一個(gè)K元組〔a1,a2,...ak〕,代表當(dāng)前解中的分母a1,a2..ak.2.節(jié)點(diǎn)擴(kuò)展方法按照a1<a2<a3..<ak的順序擴(kuò)展,擴(kuò)展第k層節(jié)點(diǎn)的時(shí)候，最簡(jiǎn)單的方法就是從a[k-1]+1開(kāi)始枚舉a[k],一直到預(yù)先確定的最大值。但是這個(gè)最大值怎么確定呢？直觀的講，a[k]總不能太大，因?yàn)槿绻鸻[k]太大，1/a[k]就很小，1/a[k+1]..1/a[k+2]..就更小，那么，盡管加了很多項(xiàng)，還可能不夠a/b.例如：例如已經(jīng)擴(kuò)展到19/45=1/5+????如果第二項(xiàng)是1/100,那么由于19/45-1/5=2/9=0.22222...那么接下來(lái)至少要0.2222/(1/100)=22項(xiàng)加起來(lái)才足夠2/9,所以繼續(xù)擴(kuò)展下去至少還要擴(kuò)展22項(xiàng),加起來(lái)才差不多夠a/b?？勺兩疃鹊乃阉魉惴≒ROCEDURESearch(k,a,b);{決定第k個(gè)分母d[k]}1.

Ifk=depth+1thenexit{depth需要進(jìn)行枚舉}2.

elseif(a=1)and(b>d[k-1])then[

｛a整除b的情況｝3.

d[k]:=b;4.

ifnotfoundor(d[k]<answer[k])then更新解;5.

]6.

else[7.

s:=max{bdiva,d[k-1]+1};{確定d[k]的上下界s,t;}t:=(depth-k+1)*bdiva

8.

fori:=stotdo[9.

d[k]:=i;10.m:=gcd(a,b);｛a,b的最大公約數(shù)為m｝11.

search(k+1,(i*a-b)divm,(b*i)divm);12.

]13.

]

0143142551321線路一線路二線路三0351314142125間隔為14間隔為11間隔為8汽車(chē)到站情況例如圖：同一條線路上的公共汽車(chē)以相同的時(shí)間間隔到站時(shí)間單位用“分”表示，從0到59。每條公共汽車(chē)線路至少有兩輛車(chē)到達(dá)本站。公共汽車(chē)線路數(shù)K一定≤17，汽車(chē)數(shù)目N一定小于300。來(lái)自不同線路的公共汽車(chē)可能在同一時(shí)刻到達(dá)本站。不同公共汽車(chē)線路的車(chē)首次到站時(shí)間和到站的時(shí)間間隔都有可能相同。目標(biāo)：編一個(gè)調(diào)度表，公共汽車(chē)線路數(shù)目最少的情況下，使公共汽車(chē)到達(dá)本站的時(shí)刻滿足輸入數(shù)據(jù)的要求。問(wèn)題要素時(shí)間車(chē)輛路線題目要求的是車(chē)和線路的關(guān)系，時(shí)間在其中起的是描述作用和條件制約作用，搜索對(duì)象應(yīng)該是車(chē)或線路這兩個(gè)關(guān)鍵要素。以車(chē)輛為搜索對(duì)象搜索策略是：按到達(dá)的時(shí)間順序，看車(chē)輛是屬于哪條線路。1〕某車(chē)屬于新線路的第一輛車(chē)2〕屬于已有線路的第二輛車(chē),此時(shí)確定了一條路線以車(chē)輛為搜索對(duì)象擴(kuò)展的搜索樹(shù)以線路為搜索對(duì)象搜索策略是：枚舉每條線路包含哪些車(chē)，確定該線路,搜索每層都要確定一條路線。1〕將未確定歸屬路線的到達(dá)時(shí)間最小的車(chē)固定為新路線的第一輛車(chē)。2〕其后枚舉這條路線的第二輛車(chē)，從而確定該路線。以線路為搜索對(duì)象擴(kuò)展的搜索樹(shù)策略比較

1〕誰(shuí)易于優(yōu)化剪枝

可行性剪枝〔方法1好〕

與最優(yōu)解比較剪枝〔方法1好〕

排除重復(fù)剪枝〔差不多〕

2〕誰(shuí)的操作量小

主遞歸程序的枚舉循環(huán)〔17<60〕

剪枝函數(shù)消耗時(shí)間〔差不多〕兩種搜索方法的實(shí)際比較多處理機(jī)調(diào)度問(wèn)題設(shè)定有假設(shè)干臺(tái)相同的處理機(jī)P1,P2Pn,和m個(gè)獨(dú)立的作業(yè)J1,J2jm,處理機(jī)以互不相關(guān)的方式處理作業(yè)，現(xiàn)約定任何作業(yè)可以在任何一臺(tái)處理機(jī)上運(yùn)行，但未完工之前不允許中斷作業(yè)，作業(yè)也不能拆分成更小的作業(yè)，作業(yè)Ji需要處理機(jī)處理的時(shí)間為T(mén)i〔i=1,2m〕。編程完成以下兩個(gè)任務(wù)：任務(wù)一：假設(shè)有n臺(tái)處理機(jī)和m個(gè)作業(yè)及其每一個(gè)作業(yè)所需處理的時(shí)間Ti存放在文件中，求解一個(gè)最正確調(diào)度方案，使得完成這m個(gè)作業(yè)的總工時(shí)最少并輸出最少工時(shí)。任務(wù)二：假設(shè)給定作業(yè)時(shí)間表和限定完工時(shí)間Ｔ于文件中，求解在限定時(shí)間Ｔ?xún)?nèi)完成這批作業(yè)所需要最少處理機(jī)臺(tái)數(shù)和調(diào)度方案。搜索對(duì)象選取方法一：按順序搜索每個(gè)作業(yè)。當(dāng)搜索一個(gè)作業(yè)時(shí)，將其放在每臺(tái)處理機(jī)搜索一次。方法二：按順序搜索每臺(tái)處理機(jī)。當(dāng)搜索一臺(tái)處理機(jī)時(shí)，將每個(gè)作業(yè)放在上面搜索一次。優(yōu)劣性分析對(duì)于方法一：只能根據(jù)目前已確定的需時(shí)最長(zhǎng)的處理機(jī)的耗時(shí)與目前最正確解比較。對(duì)于方法二：可約定Time[1]>Time[2]>Time[3]>>Time[n]〔Time[i]表示第i臺(tái)處理機(jī)的處理時(shí)間〕,從而可以設(shè)定檻值：如當(dāng)前處理機(jī)的處理時(shí)間>=目前最正確解，或剩下的處理機(jī)臺(tái)數(shù)×上一臺(tái)處理機(jī)的處理時(shí)間<剩余的作業(yè)需要的處理時(shí)間，那么回溯。因?yàn)樵谇懊娴募s束條件下，已經(jīng)不可能有解。因此，從上面的比較來(lái)看，第二種方法顯然是比第一種要好的。下面就針對(duì)第二種方法更深一層的進(jìn)行探討。對(duì)于任務(wù)一，首先可以用貪心求出Time[1]的上界。然后，還可以Time[1]的下界，UP〔作業(yè)總時(shí)間/處理機(jī)臺(tái)數(shù)〕?！睻P表示大于等于該小數(shù)的最小整數(shù)〕。搜索便從上界開(kāi)始，找到一個(gè)解后，假設(shè)等于下界即可停止搜索。對(duì)于任務(wù)二，可采用深度+可變下界。下界為：UP〔作業(yè)總時(shí)間/限定時(shí)間〕，即至少需要的處理機(jī)臺(tái)數(shù)。并設(shè)定Time[1]的上界為T(mén)?！鹃g隔排列】問(wèn)題 有2N個(gè)木塊，每個(gè)木塊標(biāo)上1到N的自然數(shù)中的一個(gè)，每個(gè)數(shù)字會(huì)出現(xiàn)在兩個(gè)木塊上。把這些木塊排成一排，要求是：標(biāo)號(hào)為i的兩個(gè)木塊之間要間隔i個(gè)其它木塊。比方說(shuō)N=3的情況，下面就是一個(gè)可行的排列：3，1，2，1，3，2。編程實(shí)現(xiàn)，對(duì)給定的N(n<=40)，求出一個(gè)可行排列。運(yùn)行效果比較N從大到小搜索從小到大搜索110.00sec0.00sec150.00sec0.11sec200.00sec36.32sec320.00sec超時(shí)400.00sec超時(shí)選擇搜索順序的根本原那么1、取值范圍小的搜索元素先搜索。2、一個(gè)搜索元素確定以后對(duì)其它搜索元素取值范圍的影響稱(chēng)為制約力。制約力較大的搜索元素先搜索。

3、先搜索對(duì)解影響較大的元素可以使剪枝時(shí)的估價(jià)函數(shù)更準(zhǔn)確，使剪枝更加有效?！舅惴谱g】〔NOI2000〕

題意簡(jiǎn)述：古梅算符由小寫(xiě)字母a到m組成，分別對(duì)應(yīng)于現(xiàn)代算符中的0,1,2,3,4,5,6,7,8,9,+,*,=中的一個(gè)。給出一組古梅算符表示的等式，假設(shè)存在滿足等式的對(duì)應(yīng)關(guān)系，那么輸出所有能夠確定的古梅算符和現(xiàn)代算符的對(duì)應(yīng)關(guān)系；否那么輸出‘noway’。INPUTOUPUT2a6abcdecb*cdefed=f+在上例中，可能對(duì)應(yīng)的現(xiàn)代表達(dá)式為{6*2=12，2=1+1}，{6*4=24，4=2+2}，{6*8=48，8=4+4}?？梢?jiàn)，能夠確定的對(duì)應(yīng)關(guān)系只有a對(duì)應(yīng)6，b對(duì)應(yīng)*，d對(duì)應(yīng)=，f對(duì)應(yīng)+，應(yīng)該輸出；三個(gè)最特殊的元素

此題中有三個(gè)算符最特殊：‘=’、‘*’、‘+’，它們要滿足以下條件：1、這三個(gè)算符不能出現(xiàn)在等式的最左端和最右端。2、這三個(gè)算符兩兩不能相鄰。3、‘＝’，這是最特殊的算符，它在任何一個(gè)等式中必須出現(xiàn)且僅出現(xiàn)一次。確定搜索順序

從取值范圍方面考慮，‘＝’，‘＋’，‘*’的取值范圍在所有算符中是最小的；從制約力方面考慮，‘＝’和‘＋’，‘*’的制約力無(wú)疑都強(qiáng)于‘0’到‘9’這十個(gè)數(shù)字；從對(duì)剪枝有利的角度考慮，這三個(gè)算符對(duì)解的影響最大，因此‘＝’，‘＋’，‘*’這三個(gè)算符應(yīng)當(dāng)放在搜索序列的前面。對(duì)于這三個(gè)算符，由于‘＝’受到的限制更多，取值范圍更小，所以應(yīng)當(dāng)優(yōu)先搜索。由此得出的最優(yōu)搜索順序：先搜索‘＝’，其次是‘＋’，‘*’，最后是10個(gè)數(shù)字。靜態(tài)優(yōu)化搜索順序

在一些問(wèn)題中，搜索元素的制約力和取值范圍在搜索過(guò)程中變化不大，或變化對(duì)搜索效率影響不大。如果要?jiǎng)討B(tài)判斷元素的取值范圍和制約力需要花費(fèi)較大的代價(jià)，而且優(yōu)化效果不好。在這種情況下只需在搜索開(kāi)始前確定搜索順序，而不必在搜索過(guò)程中再改變搜索順序。動(dòng)態(tài)調(diào)整搜索順序

有時(shí)在搜索過(guò)程中元素的取值范圍和制約力會(huì)有較大的變化，而且這些變化直接影響到搜索樹(shù)的規(guī)模,因此需要?jiǎng)討B(tài)的調(diào)整搜索順序，也就是啟發(fā)式搜索。啟發(fā)式搜索繼承了回溯法占用空間少，編程簡(jiǎn)單的優(yōu)點(diǎn)，而啟發(fā)式搜索的最大優(yōu)點(diǎn)是可以在較短的時(shí)間內(nèi)找到一組可行解，這最適合解決一類(lèi)只需要求出一組可行解的搜索問(wèn)題?！举|(zhì)數(shù)方陣】〔IOI94〕題意簡(jiǎn)述：在一個(gè)5*5的方陣中填入數(shù)字，使得沿行，沿列及兩個(gè)對(duì)角線的5個(gè)數(shù)字都能構(gòu)成一個(gè)5位質(zhì)數(shù)〔5位質(zhì)數(shù)的首位不為0〕。所有質(zhì)數(shù)的各位數(shù)字之和必須等于一個(gè)常數(shù)。這個(gè)常數(shù)和方陣左上角中的數(shù)字預(yù)先給出。假設(shè)存在多個(gè)解，必須全部得出。input111output113511403330323532011331311351332033032314033333111331313043323035023113331搜索元素的性質(zhì)1、最后一行和最后一列：可以填的數(shù)字只有{1，3，7，9}。2、兩條對(duì)角線：與方陣中的所有五位素?cái)?shù)有關(guān)。3、其他行列：特殊性取決于行列中已經(jīng)確定的格子個(gè)數(shù)。根據(jù)元素取值范圍和制約力確定搜索順序

1、最后一行和最后一列是取值范圍最小的搜索元素，而且它們對(duì)其他所有的元素都有一定的制約力，因此要放在搜索序列的最前面。2、兩條對(duì)角線同樣影響到其他所有的搜索元素，制約力在剩下的格子中是最大