北大暑期學校6.高級搜索算法

暑期課《ACM/ICPC競賽訓練信息學 課程網(wǎng)頁 A*,迭代加深，Alpha-Beta剪本講義并非全 232172176843518726345f(n)=g(n)+ 2,6,1,8,4,5都不在位，因此h(nf*(n)=g*(n)最小步數(shù)(真實值）。g*(n):從S0出發(fā)，到達n的最少步數(shù)（真實值）h*(n從n出發(fā)，到達目標節(jié)點的最少步數(shù)（真實值）fn)=g(nh(n),g(n)>0且g(n)>=g*(n)h(n)<=h*(n)且h(n)相容，則A算法轉(zhuǎn)變?yōu)锳*算法。A*正確性證明h(s1)<=h(s2)+hg(s1)+h(s1)<=g(s1)+h(s2)+c(s1,s2)=f(s1f(s2)即f是遞增A*算法偽代碼(在節(jié)點信息中記錄了其父節(jié)點whileopenifn==Targetthenreturn從Start到n的路徑找到elseforn的每個子結(jié)點xifxinopen計算新的比較open表中的舊f(x)和新if新f(x舊f(x刪掉open表里的舊x，加入新}//新舊x的父親，以及f值不}A*算法偽代碼(在節(jié)點信息中記錄了其父節(jié)點elseifxinclosed計算新的比較closed表中的舊f(x)和新if新f(x舊f(xremovexfromaddxto}}比較新f(x)和舊f(x實際上比的就是新舊g(x),因h(x)相else計算f(xaddxto}forn的每個子結(jié)點addnto}}h(n)方案二.h(n)為不在位的數(shù)字到其該呆的位置的曼哈頓距離structNodeintint int intint charmove//multiset<Node //按fmultiset<Nodeclosed//按fmap<int, tor>map<int,multiset<Node>::i tor>inClosed;元素的POJ上可用A*算法解決的題迭代加深搜索>例：旋轉(zhuǎn)游戲例：旋轉(zhuǎn)游戲例：旋轉(zhuǎn)游戲 最多的那個數(shù)字的個數(shù)n，要達 區(qū)域數(shù)字都相同，至少需要8-n次極大極小搜等,結(jié)果有三種可能：勝利、失敗和平局。n步。極大極小搜索極大極小搜索，……直到分出勝負或者達到了搜索深度的限制。若達到搜索極大極小搜索確定價函計個棋節(jié)的價正X 有I方估值，對MN 利估值小。從當前棋局的節(jié)點要決定下一步如何走時，以當前棋局節(jié)點為根，成一棵深度為n的搜索樹。不妨總是假設當前棋局節(jié)點是MAX用局面估價函數(shù)計算出每個葉子若某個非葉子節(jié)點是極大節(jié)點，則其估價值為其子節(jié)點中估價值最大那個節(jié)點的估價若某個非葉子節(jié)點是極小節(jié)點，則其估價值為其子節(jié)點中估價值最的那個節(jié)點的估極大極小搜索選當前棋局節(jié)點functionminimax(nodedepth指定當前節(jié)點和還要搜索的深//如果勝負已分或者深度為零，使用評估函數(shù)返回局面得ifnodeisaterminalnodeordepth=0returntheheuristicvalueofnode//如果輪到對手走棋，即node是極小節(jié)點，選擇一個得分最小的走iftheadversaryis yatletα:=foreachchildofα:=min(α,minimax(child,depth-//如果輪到自己走棋，是極大節(jié)點，選擇一個得分最大的走else{weare yatletα:=-foreachchildofα:=max(α,minimax(child,depth-return具體的做法intMinMax(intdepth函數(shù)的評估都是以MAX方的角度來評if(SideToMove()==return}

returnintMax(intdepth)intbest=-if(depth<= return while(MovesLeft()){val=Min(depth-if(val> best=}returnbest;intMin(intdepth){intbest=INFINITY;if(depth<=0)

注意這里不同于“最大”算return while(MovesLeft())val=Max(depth-if(val< best=

注意這里不同于“最大}return}Alpha–beta剪XYXY節(jié)點進行考查的過程中，如果一旦發(fā)現(xiàn)某子節(jié)點的估價b,則不必再考RKXYRKXY當搜索節(jié)點時，若求某子節(jié)的值為，因為是一個極節(jié)點那X節(jié)點到的定不于因X節(jié)點子節(jié)使都索值也不會超過。而節(jié)點K值，由于是一個M節(jié)點，那么的值已經(jīng)可以肯定不會X的取值了。因節(jié)點的后面子點可以忽，即第三沒數(shù)字節(jié)點忽略此ah 因被掉節(jié)點是極大節(jié)點。相應的也有beta剪枝，即被剪掉的節(jié)點是極小節(jié)beta剪若結(jié)點x是Max節(jié)點，其兄弟節(jié)點(父節(jié)點相同的節(jié)點）中，已經(jīng)求到的最估價值是a（有些兄弟節(jié)點的估價值,可能還沒有算出來那么在對x的子節(jié)點進行考查的過程中，如果一旦發(fā)現(xiàn)某子>=a,則不必再考查后面的x的子節(jié)點functionalphabeta(node,depth,α,β, ifdepth=0ornodeisaterminalnodereturntheheuristicvalueof αINF//foreachchildofα:=max(α,alphabeta(child,depth-1,α, ifβα//β是node Betacut-off,

returnβINF//foreachchildofβ:=min(β,alphabeta(child,depth-1,α, ifβα//α是node Alphacut-offreturn初始調(diào)用alphabeta(origindepthinfinity+infinity注紅色字母處，隨便寫什么值都可在搜到底的情況下，infinity不一定是無窮大infinity應該是主角贏的那Alphabeta剪枝例題POJ給定一個4*4四子連珠棋棋盤的局面，現(xiàn)在輪到x先，問x下在哪里可以必Alphabeta剪枝例題POJ三種取值，正(in，0inf必勝無論對手(B,(A,此步行棋，若能找到一個走法，其對應的usingnamespace//程序改編自網(wǎng)上博客源#defineinf1<<30//inf取1charintboolcheck(intx,inty){//…. //判斷一個局面是否是棋局結(jié)束的intMinSearch(intx,inty,intintMaxSearch(intx,inty,intintMinSearch(intx,inty,int/*本節(jié)點是A剛下完剛剛下在了(x,y)該輪到BMaxSearch的值如ans已經(jīng)小于等于alpha,那么立即停止枚舉，返回ans,表示本節(jié)點的估價值就是ans如果ansalpha*/intans=inf;ifcheck(x,y)//自己剛走了一步，如果棋局分出勝負，那么定是自己勝利returninf;if(chess==16return0//for(inti=0;i<4;for(intj=0;j<4;++j)if(str[i][j]=='.')str[i][j]='o';++inttmpMaxSearch(i,j,ansans是betastr[i][j]='.';--ans=if(ans<=alpha)return}}}return}intMaxSearch(intx,inty,int用MinSearch求其估價值，返回估價值最大的那個走法的估價值。MinSearch的值如ans已經(jīng)大于等于beta,ans,表示本節(jié)點的估價值就是如果ansbeta，那么本節(jié)點就不會被B選擇intansinf//if(returnif(chess==16returnfor(inti=0;i<4;++for(intj=0;j<4;++j)if(str[i][j]=='.')str[i][j]='x';inttmp=MinSearch(i,j,ans//ans是beta值，即在本節(jié)點的各個子節(jié)點中，目前找到的最大的估價str[i][j]='.';--ans=if(ans>=betareturn}}return}bool{intalpha=-for(inti=0;i<4;++for(intj=0;j<4;++j)if(str[i][j]=='.')str[i][j]='x';++inttmp=str[i][j]='.';--if(tmp==inf)X=Y=return}}}return}intcharfor(int}}if(Solve())elseprintf(“#####\n//無必勝走}return}例：2012金華邀請賽ProblemF例：2012金華邀請賽ProblemF誤區(qū)采用和POJ1568一樣的估價函數(shù)定義來？OX？