(HDUACM201209版-08)搜索之入門

ACM程序設計杭州電子科技大學劉春英acm@2/5/20231每周一星（7）：李博2/5/20232第八講一招制敵之搜索題2/5/20233 根據(jù)“信息學初學者之家”網(wǎng)站的統(tǒng)計，Ural（俄羅斯的Ural州立大學的簡稱，有名的UralOnlineProblemSet就是該校的系統(tǒng)）的題目類型大概呈如下的分布：

搜索動態(tài)規(guī)劃貪心構(gòu)造圖論

約10%約15%約5%約5%約10% 計算幾何純數(shù)學題數(shù)據(jù)結(jié)構(gòu)其它

約5%約20%約5%約25%

統(tǒng)計信息：2/5/20234什么是搜索算法呢？ 搜索算法是利用計算機的高性能來有目的地窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。

搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點的過程。2/5/20235本講主要內(nèi)容二分搜索三分搜索DFSBFS（略）2/5/20236第一部分：二分查找2345681220324565748695100假設給出若干個（可以很多）有序的整數(shù)，請查找某個元素是否存在，比如—— 請查找以上數(shù)列中是否存在某個整數(shù)（比如25）， 若有，請輸出其位置，否則請輸出NO~2/5/20237第一部分：二分查找2345681220324565748695100headmidtail再次提醒：二分查找的前提——數(shù)據(jù)的單調(diào)性2/5/20238思考：1、在一百萬個元素里查找某個元素大約需要比較多少次？2、時間復雜度：O(logN)2/5/20239二分查找-例題1HDOJ-2199給出方程：

8*x4+7*x3+2*x2+3*x+6=Y其中，實數(shù)Y滿足(fabs(Y)<=1e10)請輸出x在區(qū)間[0,100]的解，結(jié)果精確到小數(shù)點后4位。2/5/202310題目分析常規(guī)暴力枚舉？當測試數(shù)據(jù)足夠多->效率低下指定區(qū)間內(nèi)的單調(diào)性（如何證明?）推薦方法：二分求解2/5/202311二分查找-參考代碼1//HDOJ-2199#include<iostream>#include<cmath>usingnamespacestd;doubleY;doublel,r,m;doublef(doublex){return8*pow(x,4.0)+7*pow(x,3.0)+2*pow(x,2.0)+3*x+6;}intmain(){intt;scanf("%d",&t);while(t--){scanf("%lf",&Y);if(f(0)<=Y&&Y<=f(100)){l=0;r=100;while(r-l>1e-6){m=(l+r)/2;doubleans=f(m);if(ans>Y){r=m-1e-7;}elsel=m+1e-7;}printf("%.4lf\n",(l+r)/2);}elseprintf("Nosolution!\n");}}

2/5/202312二分查找-例題2HDOJ-2899給出函數(shù)：F(x)=6*x7+8*x6+7*x3+5*x2-y*x其中，實數(shù)y滿足(0<y<1e10)請輸出x在區(qū)間[0,100]時函數(shù)F(x)的最小值，結(jié)果精確到小數(shù)點后4位。2/5/202313題目分析指定區(qū)間內(nèi)是否滿足單調(diào)性?顯然不滿足->不能直接二分滿足凸性？如何證明？極值點的特點？是否可以二分？2/5/202314二分查找-參考代碼2//HDOJ-2899#include<stdio.h>#include<math.h>constdoubleeps=1e-8;doubley;doublecal(doublex){return42.0*pow(x,6.0)+48.0*pow(x,5.0)+21.0*pow(x,2.0)+10.0*x;}doubleans(doublex){return6.0*pow(x,7.0)+8.0*pow(x,6.0)+7.0*pow(x,3.0)+5.0*pow(x,2.0)-y*x;}intmain(){intT;doublef,l,mid;scanf("%d",&T);while(T--){scanf("%lf",&y);if(cal(100.0)-y<=0.0){printf("%.4lf\n",ans(100.0));continue;}f=0.0,l=100.0;while(l-f>eps){mid=(f+l)/2.0;if(cal(mid)-y<0.0){f=mid;}else{l=mid;}}printf("%.4lf\n",ans(mid));}return0;2/5/202315新問題如果函數(shù)滿足凸性特點，但是——求導不方便！該如何處理？2/5/202316三分查找（TernarySearch）2/5/202317三分查找（TernarySearch）2/5/202318三分查找（TernarySearch）2/5/202319三分查找（TernarySearch）2/5/202320三分查找-參考代碼遞歸和非遞歸2種方式的實現(xiàn)（略）（請模仿二分的寫法自己實現(xiàn)）提醒：三分的前提——數(shù)據(jù)的凸性再提醒：凸性并不要求可導！2/5/202321典型搜索——迷宮搜索2/5/202322SampleInput

445

S.X.

..X.

..XD

....

345

S.X.

..X.

...D

000SampleOutput

NO

YES

HDOJ_1010TempteroftheBone2/5/202323要點分析：典型的迷宮搜索，熟練掌握該題將具有里程碑式的意義！每個block只能走一次要求恰好某個給定的時間到達出口2/5/202324剪枝條件？如果可走的block的總數(shù)小于時間，將會產(chǎn)生什么情況？還想到什么剪枝？2/5/202325奇偶性剪枝可以把map看成這樣：010101101010010101101010010101從為0的格子走一步，必然走向為1的格子從為1的格子走一步，必然走向為0的格子即：0->1或1->0必然是奇數(shù)步0->0走1->1必然是偶數(shù)步

結(jié)論：所以當遇到從0走向0但是要求時間是奇數(shù)的，或者，從1走向0但是要求時間是偶數(shù)的都可以直接判斷不可達！2/5/202326參考源碼（HDOJ_1010）附錄：hdoj_1010月下版#include<iostream.h>#include<string.h>#include<stdlib.h>charmap[9][9];intn,m,t,di,dj;boolescape;intdir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};voiddfs(intsi,intsj,intcnt){inti,temp;if(si>n||sj>m||si<=0||sj<=0)return;

if(cnt==t&&si==di&&sj==dj)escape=1;

if(escape)return;

temp=(t-cnt)-abs(si-di)-abs(sj-dj);if(temp<0||temp&1)return;for(i=0;i<4;i++){if(map[si+dir[i][0]][sj+dir[i][1]]!='X') {map[si+dir[i][0]][sj+dir[i][1]]='X';dfs(si+dir[i][0],sj+dir[i][1],cnt+1);map[si+dir[i][0]][sj+dir[i][1]]='.';}}return;}intmain(){ inti,j,si,sj; while(cin>>n>>m>>t) { if(n==0&&m==0&&t==0)break; intwall=0; for(i=1;i<=n;i++)for(j=1;j<=m;j++) {cin>>map[i][j];if(map[i][j]=='S'){si=i;sj=j;}elseif(map[i][j]=='D'){di=i;dj=j;}elseif(map[i][j]=='X')wall++;}if(n*m-wall<=t) { cout<<"NO"<<endl;

continue; } escape=0;map[si][sj]='X';

dfs(si,sj,0);if(escape)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return0;}

2/5/202327這個題目沒問題了吧？HDOJ_1010TempteroftheBone2/5/202328——摘自《ACM競賽之新人向?qū)А?“算法中最基本和常用的是搜索，這里要說的是，有些初學者在學習這些搜索基本算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運行的時間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。 實際上參賽選手基本上都會使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了?！碧貏e提醒：2/5/202329思考（變化）：求某給定時間以內(nèi)能否找到出口找到出口的最短時間條件變?yōu)榭梢酝Ａ?/5/202330四、深度優(yōu)先搜索

基本思想：從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個結(jié)點，檢查是否出現(xiàn)目標狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結(jié)點，再檢查是否為目標節(jié)點G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進行到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當它仍不是目標狀態(tài)G時，回溯到上一層結(jié)果，取另一可能擴展搜索的分支。生成新狀態(tài)節(jié)點。若仍不是目標狀態(tài)，就按該分支一直擴展到葉節(jié)點，若仍不是目標，采用相同的回溯辦法回退到上層節(jié)點，擴展可能的分支生成新狀態(tài)，…，一直進行下去，直到找到目標狀態(tài)G為止。2/5/202331DFS算法（1）把起始節(jié)點S線放到OPEN表中。（2）如果OPEN是空表，則失敗退出，否則繼續(xù)。（3）從OPEN表中取最前面的節(jié)點node移到CLOSED表中。（4）若node節(jié)點是葉結(jié)點（若沒有后繼節(jié)點），則轉(zhuǎn)向（2）。（5）擴展node的后繼節(jié)點，產(chǎn)生全部后繼節(jié)點，并把他們放在OPEN表的前面。各后繼結(jié)點指針指向node節(jié)點。（6）若后繼節(jié)點中某一個是目標節(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。2/5/202332三、廣度優(yōu)先搜索