課件lecture 08搜索入門

ACM程序設(shè)12021/7/7計計算機(jī)學(xué)院劉春英今天，你了嗎？22021/7/7每周一星（7）：NPEG-MP4

&&

OPPO

MP432021/7/7第八講42021/7/7一招制敵之搜索題根據(jù)“信息學(xué)初學(xué)者之家”網(wǎng)站的統(tǒng)計，

Ural（俄羅斯的Ural州立大學(xué)的簡稱，那里設(shè)立了一個Ural

Online

Problem

Set，并且支持OnlineJudge。）的題目類型大概呈如下的分布：52021/7/7搜索約10%動態(tài)規(guī)劃約15%貪心約5%構(gòu)造 圖論約5%

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

約20%約5%

約25%統(tǒng)計信息：搜索題特點分析:62021/7/7題意容易理解算法相對固定編程有路可循競賽必備知識“算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運行的時間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。實際上參賽選手基本上都會使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了?！薄浴禔CM競賽之新人向?qū)А?2021/7/7引言什么是搜索算法呢？82021/7/7搜索算法是利用計算機(jī)的高性能來有目

的地窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的節(jié)點的過程。預(yù)熱一下：二分查找2

3

4

5

6

8

12

20

32

45

65

74

86

95

100head92021/7/7midtail查找示意圖：A[1]~A[15]A[1]~A[7]A[9]~A[15]A[1]~A[3]A[5]~A[7]A[1]~A[1]A[3]~A[3]……102021/7/7思考：112021/7/71、在一百萬個元素里查找某個元素大約需要比較多少次？2、時間復(fù)雜度：O(logN)舉例分析122021/7/7從簡單的字符串搜索講起HDOJ_1238132021/7/7Substrings題目鏈接Sample

Input23ABCDBCDFFBRCD2roseorchidSampleOutput22題目分析：142021/7/7這是一道入門級別的搜索題，基本思想比較簡單，但是如果用最樸素的算法，可能會超時如何降低算法的復(fù)雜度呢？下面的算法如何：先將字符串按長度從短到長排序，枚舉最短的字符串的子串，判斷是否都是別的字符串的子串，求出最大長度即可。說明：152021/7/7本題除了可以練習(xí)基本搜索算法，也是練習(xí)字符串處理的好題目，題中用到的相關(guān)知識點有：求反串求子串字符串查找求字符串長度強(qiáng)烈推薦??！再來一道數(shù)值型搜索題162021/7/7HDOJ_1239172021/7/7Calling

Extraterrestrial

Intelligence

Again題目鏈接SampleInput51299999

999

9991

12002

4

11000SampleOutput2

2313

31323

7343

4337

53獲取有用信息182021/7/7給定整數(shù)m,a,b(4<m<=100000

and 1<=a<=b<=1000)需要找到兩個數(shù)(不妨設(shè)為p,q)滿足以下 條件：p,q均為質(zhì)數(shù)；p*q<=m;a/b

<=

p/q

<=

1;輸出所有滿足以上條件的p,q中乘積最大 的一對p,q算法分析192021/7/7典型的搜索從所有可能的p,q中尋找滿足條件的一對p,q的要求p,q均為質(zhì)數(shù),且p<=q<=100000;按上述思想流程應(yīng)為從1—100000中搜出質(zhì)數(shù)兩層循環(huán)，試遍所有的組合(p,q可能相等）每種組合去判斷是否符合條件，如是，將

p*q與當(dāng)前最大值比較，判斷，保存面臨的問題：202021/7/7超時！從1—100000的質(zhì)數(shù)運算約為1e+8,而這只是準(zhǔn)備工作。因此，如不加以分析簡化此題無法在規(guī)定時間內(nèi)出解深入分析不會超過9091）212021/7/7p,q的范圍其實可在2—50000(why?)然而，這是最小的范圍嗎？考慮大于10000的某個質(zhì)數(shù)，不妨設(shè)為Q，另一個質(zhì)數(shù)為P，則：如果P<10，P/Q<0.001如果P>10，P*Q>100000而考慮到a,b的取值范圍(1<=a<=b<=1000)可知min(a/b)=0.001同時，要求：p*q<=m<=100000所以無論如何質(zhì)數(shù)都不能超過10000。（事實上，搜索時的技巧：222021/7/7搜索順序很重要。建議從大往小搜（

num:質(zhì)數(shù)的個數(shù)）for

(i=num-1;i>=0;i--)for

(j=i;j<=num-1;j++)……注意剪枝：If

(

a[j]>m

||

a[j]*a[i]>m

||

(

(double)a[i]/a[j])<s

)……真正的搜索題232021/7/7迷宮搜索預(yù)備知識——樹的遍歷242021/7/7樹的遍歷主要有如下四種方法：先根/序遍歷中根/序遍歷后根/序遍歷層次遍歷分別有什么特點呢？（1）先根遍歷252021/7/7對樹的訪問次序是:先訪問根結(jié)點再訪問左子樹最后訪問右子樹對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2135746以上二叉樹的先根遍歷序列是：？？1、2、4、5、3、6、7262021/7/7（2）中根遍歷272021/7/7對樹的訪問次序是:先訪問左子樹再訪問根結(jié)點最后訪問右子樹對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2135746以上二叉樹的中根遍歷序列是：？？4、2、5、1、6、3、7282021/7/7（3）后根遍歷292021/7/7對樹的訪問次序是:先訪問左子樹再訪問右子樹最后訪問根結(jié)點對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2135746以上二叉樹的后根遍歷序列是：？？4、5、2、6、7

、3、1302021/7/7（4）層次遍歷312021/7/7對樹的訪問次序是:先訪問根結(jié)點再訪問根結(jié)點的子節(jié)點（即第二層節(jié)點）再訪問第三層節(jié)點……示例如下：2135746以上二叉樹的層次遍歷序列是：？？1、2、3、4、5、6、7322021/7/7幾個基本概念：332021/7/7初始狀態(tài)：略目標(biāo)狀態(tài)：略狀態(tài)空間：由于求解問題的過程中分枝有很

多（主要是求解過程中求解條件的不確定性、不完備性造成的），使得求解的路徑很多，這就構(gòu)成了一個圖，我們說這個圖就是狀態(tài)空間。狀態(tài)空間搜索：就是將問題求解過程表現(xiàn)為

從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程，可以從求解的開始到問題的結(jié)果。初始狀態(tài)：342021/7/7目標(biāo)狀態(tài)：2831647512384765例 九宮重排問題2831647583214765283147652831647528314765231847652831647528314765231847652318476528371465352021/7/723184765123847651238476512378465362021/7/7三、廣度優(yōu)先搜索372021/7/7基本思想：從初始狀態(tài)S開始，利用規(guī)則，生成所有可能的狀態(tài)。構(gòu)成樹的下一

層節(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未

出現(xiàn)，就對該層所有狀態(tài)節(jié)點，分別順序

利用規(guī)則。生成再下一層的所有狀態(tài)節(jié)點，對這一層的所有狀態(tài)節(jié)點檢查是否出現(xiàn)G，若未出現(xiàn)，繼續(xù)按上面思想生成再下一層

的所有狀態(tài)節(jié)點，這樣一層一層往下展開。直到出現(xiàn)目標(biāo)狀態(tài)為止。BFS算法：382021/7/7把起始節(jié)點S線放到OPEN表中如果OPEN是空表，則失敗退出，否則繼續(xù)。在OPEN表中取最前面的節(jié)點node移到CLOSED

表中。擴(kuò)展node節(jié)點。若沒有后繼（即葉節(jié)點），則轉(zhuǎn)向（2）循環(huán)。把node的所有后繼節(jié)點放在OPEN表的末端。各后繼結(jié)點指針指向node節(jié)點。若后繼節(jié)點中某一個是目標(biāo)節(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。OPLV

WUTRQA

BF

G搜索過程如下：SC

D

E廣度優(yōu)先搜索示意圖392021/7/7例1、示意圖節(jié)點的搜索SL，O，PQ，R，TU，V，WA，B，CSL

OPQR廣度優(yōu)先搜索過程中的OPEN表和CLOSED表402021/7/7OPENCLOSED四、深度優(yōu)先搜索412021/7/7基本思想：從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個結(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結(jié)點，再檢查是否為目標(biāo)節(jié)點G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進(jìn)行到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當(dāng)它仍不是目標(biāo)狀態(tài)G時，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。生成新狀態(tài)節(jié)點。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴(kuò)展到葉節(jié)點，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點，擴(kuò)展可能的分支生成新狀態(tài)，…，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。42搜索過程如下：HALIFBCDEJGKS深度優(yōu)先搜索示意圖2021/7/7DFS算法432021/7/7把起始節(jié)點S線放到OPEN表中。如果OPEN是空表，則失敗退出，否則繼續(xù)。從OPEN表中取最前面的節(jié)點node移到CLOSED

表中。若node節(jié)點是葉結(jié)點（若沒有后繼節(jié)點），則轉(zhuǎn)向（2）。擴(kuò)展node的后繼節(jié)點，產(chǎn)生全部后繼節(jié)點，并把他們放在OPEN表的前面。各后繼結(jié)點指針指向node節(jié)點。若后繼節(jié)點中某一個是目標(biāo)節(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。例、節(jié)點搜索示意圖A，

H，R，

F，C，

DEABCDEOPEN

CLOSEDS

S442021/7/7小結(jié)：452021/7/7廣度和深度優(yōu)先搜索有一個很大的缺陷,就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測的情況下就不可取了。他的效率實在太低，甚至不可完成。所以，在這里再次強(qiáng)調(diào)“剪枝”！HDOJ_1010

Tempter

of

the

Bone462021/7/7Sample

Input445S.X...X...XD....345S.X...X....D000SampleOutputNOYES要點分析：472021/7/7典型的迷宮搜索，做出該題將具有里程碑式的意義！每個block只能走一次要求恰好某個給定的時間到達(dá)出口想到了什么剪枝條件？482021/7/7如果可走的block的總數(shù)小于時間，將會產(chǎn)生什么情況？還想到什么剪枝？奇偶性剪枝492021/7/7可以把map看成這樣：0

1

0

1

0

11

0

1

0

1

00

1

0

1

0

11

0

1

0

1

00

1

0

1

0

1從為0的格子走一步，必然走向為1

的格子從為1的格子走一步，必然走向為0

的格子即：0->1或1->0

必然是奇數(shù)步0->0

走1->1

必然是偶數(shù)步結(jié)論：所以當(dāng)遇到從0走向0

但是要求時間是奇數(shù)的，或者，從1

走向

0但是要求時間是偶數(shù)的都可以直接判斷不可達(dá)！這個題目沒問題了吧？502021/7/7思考：512021/7/7求某給定時間以內(nèi)能否找到出口找到出口的最短時間條件變?yōu)榭梢酝Ａ舾戒洠和扑]搜索題：1010、1240、1241、12421072、1253

、1312、1372(以上題目類似于1010)1238、1239、1015、10161401、1515、1548522021/7/7課后一定要練習(xí)！532021/7/7ACM,天天見！542021/7/7int

main(){附錄：hdoj_1010月下版int

i,j,si,sj;#

include

<iostream.h>#

include

<string.h>while(cin>>n>>m>>t){#

include

<stdlib.h>char

map[9][9];int

n,m,t,di,dj;bool

escape;if(n==0&&m==0&&t==0)

break;int

wall=0;for(i=1;i<=n;i++)int

dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};void

dfs(int

si,int

sj,int

cnt){ int

i,temp;if(si>n||sj>m||si<=0||sj