搜索方法中剪枝優(yōu)化

中學(xué)【】本文討論了搜索方法中最常見(jiàn)的一種優(yōu)化技巧——剪一、1應(yīng)用剪枝優(yōu)化的問(wèn)題是設(shè)計(jì)剪枝判斷方法即確定哪些枝條應(yīng)當(dāng)就應(yīng)當(dāng)首先分析一下設(shè)計(jì)剪枝判斷方法的時(shí)候，需要遵循的一些原則。效果這恐怕也是得不償失很多情況下能否較好的解決這個(gè)，NBetsy能采用的所有的旅行路線的數(shù)目。我們用深度優(yōu)先的回溯方法來(lái)解決這個(gè)問(wèn)題：Betsy從左上角出N2-1步并達(dá)到左下角時(shí)，即得到了一條新的N=6的個(gè)尚過(guò)的格子都與至少兩個(gè)尚過(guò)的格子相鄰（除非當(dāng)時(shí)Betsy就在它旁邊。這里，我們是從微觀的角度分析問(wèn)題。能都有至少兩個(gè)相鄰的空的格子，但它們作為一個(gè)整體，Betsy已經(jīng)我們?cè)诿看渭糁ε袛鄷r(shí)，都簡(jiǎn)單的對(duì)N2個(gè)格子進(jìn)行一遍掃描，其效率的低下可想而知。因此，須盡可能的簡(jiǎn)化判斷的過(guò)程。與每個(gè)格子相鄰的沒(méi)被經(jīng)過(guò)的格子的數(shù)目，Betsy每次移動(dòng)到一個(gè)新BetsyBetsy圖 剪枝原理示意PrimeCircleACMAsianRegional96)界，即所謂估價(jià)函數(shù)hh大于當(dāng)前保存的優(yōu)度的下界，是該題目簡(jiǎn)述：由xxn，其中n為輸（1）一個(gè)數(shù)列ai，滿足aaia

j

ii要求atn，并且使t取值范圍在ai11到ai1*2nai1*2開(kāi)始從大到小為ain。當(dāng)搜索到n出當(dāng)前的最大者是ai，即當(dāng)前搜索深度為ih n2 2i然而，這個(gè)估價(jià)函數(shù)的準(zhǔn)確性太差，特別是當(dāng)anh A*搜索方法，只要還使用這個(gè)估價(jià)函數(shù)，其優(yōu)化優(yōu)化之四：我們可以在搜索之前將n分解質(zhì)因數(shù)，對(duì)每個(gè)質(zhì)因數(shù)先使用上述搜索方法求解（1，優(yōu)化之五：當(dāng)數(shù)列中的當(dāng)前最大數(shù)an 以發(fā)揮作用了。但是，此后的最優(yōu)方案，實(shí)際上就等價(jià)于從a1到ai這i個(gè)數(shù)中，選出盡可能少的數(shù)（可重復(fù)，使它們的和等于n。這個(gè)問(wèn)A*算法的方法來(lái)解決（用改進(jìn)的估價(jià)函數(shù)作為優(yōu)度上界估計(jì)，即h*函數(shù)；前述的動(dòng)A*算法的結(jié)合以其較好的，個(gè)原則——正確、準(zhǔn)確和高效，才是貫穿于始終的。設(shè)計(jì)》王建德編著《InformaticsOlympic（N213248567（測(cè)試環(huán)境：PentiumIIi 最初的估價(jià)函數(shù)的設(shè)計(jì)思路實(shí)際上是在當(dāng)前數(shù)列a1,ai的基礎(chǔ)上理想化的構(gòu)造2a,4a,,2pa，當(dāng)2pan2p1ai 然而，這只是保證了能夠得到大于等于n的數(shù)，并不一定恰好得到n。我們首先，任何一個(gè)自然數(shù)i都可以表示成2k(2m (k,mZ)的形式，我可以設(shè)k(i表示一個(gè)自然數(shù)i所對(duì)應(yīng)的k值。顯然，對(duì)于任何兩個(gè)自然數(shù)a和b，a,

,,a,2a,4a,,2p

（2p

n2p1a ij1jp，使得k2jakn，由kabmini則有k2ta2pak2tak2jak jtii ii2t

2pa （kakb是ab的必要條件即2jai,,2pai中的任何一個(gè)數(shù)與2pai相加都不可能得到n所以，如果n2pai2j1ai，則在得到2pai后，至少還需要再進(jìn)行兩次加法才有可能得到n。估價(jià)函數(shù)的改進(jìn)，而不象在“Betsy的旅行”中那樣是互相補(bǔ)充的兩個(gè)方面，但（N（測(cè)試環(huán)境：PentiumPro當(dāng)n1000610(分段搜索123456723解，所以能夠使程序的效率得到比較明顯的改善，四個(gè)程序中，只有它能夠在一分鐘以內(nèi)完成表中所列出的每個(gè)測(cè)試數(shù)據(jù)，特別是n=1023化效果就會(huì)極不明顯（如n=719加入動(dòng)態(tài)規(guī)劃后的程序（4，實(shí)際上使得搜索過(guò)程主要集中在[n/2]以下，在相當(dāng)程度上避免了對(duì)[n/2]到n的估價(jià)函數(shù)幾乎沒(méi)有作用的部分的41。5，由于使用了初始定界，使搜索前就已經(jīng)有了比（n=719A*算法外，還結(jié)合使用了分枝定界的方法，否則時(shí)空效率更Betsy的旅行”的程序（使用兩種剪枝{$M }}fori:=0ton+1dobeginfori:=2ton-1dobeginfork:=1to4dobegindir:byte;{Betsy的移動(dòng)方向}fori:=1to4dobeginif(map[a,b]=-1)and((a<>nx)or(b<>ny))and(left[a,b]<=1)thenbeginif(dir=2)or(dir=4)thenbeginelsebeginand(map[nx+delta[d2,1],ny+delta[d2,2]]=-1)thenbeginif(map[fx+delta[d1,1],fy+delta[d1,2]]<>-1)and(map[nx+delta[d1,1],ny+delta[d1,2]]=-1)and(map[fx,fy]=-1)thenbeginif(map[fx+delta[d2,1],fy+delta[d2,2]]<>-1)and(map[nx+delta[d2,1],ny+delta[d2,2]]=-1)and(map[fx,fy]=-1)thenbegin ifable(nx,ny)then n('Thenumberoftoursis',s);{輸出結(jié)果}（{$M output中，對(duì)其進(jìn)行了轉(zhuǎn)換。}keep中給出所構(gòu)造的最優(yōu)冪次數(shù)列。} whilenotodd(num)dobeginnum:=numshr1;ifnum<=rangethenbegin{num在[n/2]以內(nèi)}fori:=step-1downto1dobeginifa[i]+a[i]<numthenbreak;iftime[num-a[i]]=1thenifp>rangethenfori:=a[step-1]+1topdoforj:=step-2downto2do{決策枚舉}whilenum<ndobeginnum:=numshl1;ifh(a[step])+step>=bestthencut1:=trueelsecut1:=false;rest:integer;{k(rest)=k(n)的數(shù)}ifh(a[step]+a[step-1])+step+1<bestthen

}ifpt>knthenrest:=a[step-1]ifpt=knthenrest:=a[step]elserest:=maxint;a[step+i+1]:=a[step+i]shl1;ifpt+i=knthenrest:=a[step+i];untila[step+i]>n;ifn-a[step+i]>rest)and(step+i+2>=bestthencut2:=trueelsecut2:=false;{剪枝判斷}ifa[step-1]+a[step-1]>=ntheniftime[n-a[step-1]]+step-1<bestthenbegin{判斷出解}fori:=kdowntoa[step-1]+1doifok(i)thenbeginifi<=rangethentime[i]:=1;ifcut1thenbreak;{ifcut2thencontinue;{2}}ifkeep[0]=bestthenifkeep[i]<=leftthenbeginiffoundthenexit;range:=ndiv}pfact:integer;{num的素因子的變量}b2:integer;{num2的因子的數(shù)目}s:integer;{n的估價(jià)步數(shù)}whilenotodd(num)dobeginnum:=numdiv2;fori:=2tobestdokeep[i+keep[0]-1]:=kp[i];while(pfact<=sq)and(nummodpfact>0)doinc(pfact,2);ifpfact<=sqthenbeginbest:=guess(numdivpfact);fori:=k+1tokeep[0]dokeep[i]:=pfact*keep[i];}fori:=k2+1tokeep[0dokeep[i]:=keep[i]*power2[b2