課件lecture 08搜索入門(mén)

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

&&

OPPO

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

Ural（俄羅斯的Ural州立大學(xué)的簡(jiǎn)稱(chēng)，那里設(shè)立了一個(gè)Ural

Online

Problem

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

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

約20%約5%

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

的地窮舉一個(gè)問(wèn)題的部分或所有的可能情況，從而求出問(wèn)題的解的一種方法。搜索過(guò)程實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹(shù)并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過(guò)程。預(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、在一百萬(wàn)個(gè)元素里查找某個(gè)元素大約需要比較多少次？2、時(shí)間復(fù)雜度：O(logN)舉例分析122021/7/7從簡(jiǎn)單的字符串搜索講起HDOJ_1238132021/7/7Substrings題目鏈接Sample

Input23ABCDBCDFFBRCD2roseorchidSampleOutput22題目分析：142021/7/7這是一道入門(mén)級(jí)別的搜索題，基本思想比較簡(jiǎn)單，但是如果用最樸素的算法，可能會(huì)超時(shí)如何降低算法的復(fù)雜度呢？下面的算法如何：先將字符串按長(zhǎng)度從短到長(zhǎng)排序，枚舉最短的字符串的子串，判斷是否都是別的字符串的子串，求出最大長(zhǎng)度即可。說(shuō)明：152021/7/7本題除了可以練習(xí)基本搜索算法，也是練習(xí)字符串處理的好題目，題中用到的相關(guān)知識(shí)點(diǎn)有：求反串求子串字符串查找求字符串長(zhǎng)度強(qiáng)烈推薦！！再來(lái)一道數(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)需要找到兩個(gè)數(shù)(不妨設(shè)為p,q)滿足以下 條件：p,q均為質(zhì)數(shù)；p*q<=m;a/b

<=

p/q

<=

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

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

num:質(zhì)數(shù)的個(gè)數(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ù)備知識(shí)——樹(shù)的遍歷242021/7/7樹(shù)的遍歷主要有如下四種方法：先根/序遍歷中根/序遍歷后根/序遍歷層次遍歷分別有什么特點(diǎn)呢？（1）先根遍歷252021/7/7對(duì)樹(shù)的訪問(wèn)次序是:先訪問(wèn)根結(jié)點(diǎn)再訪問(wèn)左子樹(shù)最后訪問(wèn)右子樹(shù)對(duì)于左右子樹(shù)的訪問(wèn)也要滿足以上規(guī)則示例如下：2135746以上二叉樹(shù)的先根遍歷序列是：？？1、2、4、5、3、6、7262021/7/7（2）中根遍歷272021/7/7對(duì)樹(shù)的訪問(wèn)次序是:先訪問(wèn)左子樹(shù)再訪問(wèn)根結(jié)點(diǎn)最后訪問(wèn)右子樹(shù)對(duì)于左右子樹(shù)的訪問(wèn)也要滿足以上規(guī)則示例如下：2135746以上二叉樹(shù)的中根遍歷序列是：？？4、2、5、1、6、3、7282021/7/7（3）后根遍歷292021/7/7對(duì)樹(shù)的訪問(wèn)次序是:先訪問(wèn)左子樹(shù)再訪問(wèn)右子樹(shù)最后訪問(wèn)根結(jié)點(diǎn)對(duì)于左右子樹(shù)的訪問(wèn)也要滿足以上規(guī)則示例如下：2135746以上二叉樹(shù)的后根遍歷序列是：？？4、5、2、6、7

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

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

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

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

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

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

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

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

WUTRQA

BF

G搜索過(guò)程如下：SC

D

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

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

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

H，R，

F，C，

DEABCDEOPEN

CLOSEDS

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

Tempter

of

the

Bone462021/7/7Sample

Input445S.X...X...XD....345S.X...X....D000SampleOutputNOYES要點(diǎn)分析：472021/7/7典型的迷宮搜索，做出該題將具有里程碑式的意義！每個(gè)block只能走一次要求恰好某個(gè)給定的時(shí)間到達(dá)出口想到了什么剪枝條件？482021/7/7如果可走的block的總數(shù)小于時(shí)間，將會(huì)產(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的格子走一步，必然走向?yàn)?

的格子從為1的格子走一步，必然走向?yàn)?

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

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

走1->1

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

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

走向

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

、1312、1372(以上題目類(lèi)似于1010)1238、1239、1015、10161401、1515、1548522021/7/7課后一定要練習(xí)！532021/7/7ACM,天天見(jiàn)！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