HNUSTC語言基礎簡單數(shù)據(jù)結(jié)構acm入門第一講搜索.ppt

C語言基礎，簡單數(shù)據(jù)結(jié)構， ACM入門講座 搜索部分,Bjut：mark063 2010.10.30,1,C語言是什么,for while ifelse switch , case 函數(shù)調(diào)用 變量，數(shù)組，結(jié)構體聲明 ,2,ACM/ICPC,ACM-ICPC以團隊的形式代表各學校參賽，每隊由3名隊員組成。每位隊員必須是在校學生，有一定的年齡限制，并且最多可以參加2次全球總決賽和5次區(qū)域選拔賽。 比賽期間，每隊使用1臺電腦需要在5個小時內(nèi)使用C、C+或Java中的一種編寫程序解決7到10個問題。程序完成之后提交裁判運行，運行的結(jié)果會判定為正確或錯誤兩種,3,其他比賽,Topcoder，Codeforces平均每周一次，還定期有其他形式的比賽，要求快速準確的構造算法寫代碼能力 有道難題，百度之星，每年5，6月份 數(shù)學建模，校內(nèi)賽4，5月，全國9月,4,參考書目,圖書館有關acm的書 網(wǎng)上OJ,5,天津賽區(qū),哈爾濱賽區(qū),6,POJ 2027 No Brainer Time Limit: 1000MSMemory Limit: 30000K Total Submissions: 15196Accepted: 10314 Description Zombies love to eat brains. Yum. Input The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line “X Y“, where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive. Output For each data set, there will be exactly one line of output. This line will be “MMM BRAINS“ if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be “NO BRAINS“. Sample Input 3 4 5 3 3 4 3 Sample Output NO BRAINS MMM BRAINS MMM BRAINS,7,Description Zombies love to eat brains. Yum. Input The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line “X Y“, where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive. Output For each data set, there will be exactly one line of output. This line will be “MMM BRAINS“ if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be “NO BRAINS“.,8,ACM題型分類,1，基本算法 2，圖算法 3，數(shù)據(jù)結(jié)構 4，搜索 5，動態(tài)規(guī)劃 6，貪心 7，數(shù)學 8，計算幾何 9，模擬,9,10,搜索概論,搜索被稱為“通用解題法”，在算法和人工智能中占據(jù)重要地位。 但由于它巨大的局限性和自身靈活性，也被認為是最難學難用的算法之一。 本節(jié)目標：希望同學們對于任意一個問題， 1.很快建立狀態(tài)空間 2.提出一個合理算法 3.簡單估計時空性能,11,搜索分類,盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。 啟發(fā)式搜索：在搜索中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向發(fā)展，加速問題的求解過程并找到最優(yōu)解。,12,搜索算法,盲目搜索： 1. 廣度優(yōu)先搜索（Breadth First Search） 2. 深度優(yōu)先搜索（Depth First Search） 3. 純隨機搜索、重復式搜索、迭代加深搜索、 迭代加寬搜索、柱型搜索 啟發(fā)式搜索： 1. A*算法 2. IDA*算法,13,DFS&BFS,深搜例子：走迷宮，你沒有辦法用分身術來站在每個走過的位置。不撞南山不回頭。 廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠一點的地方,14,狀態(tài)空間,明確以下概念： 狀態(tài)：問題在某一時刻進展狀況的數(shù)學描述。 狀態(tài)轉(zhuǎn)移：問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。 狀態(tài)空間：一個“圖”，圖結(jié)點對應于狀態(tài)，點之間的邊對應于狀態(tài)轉(zhuǎn)移。 搜索：尋找一種可行的操作序列，從起始狀態(tài)經(jīng)過一系列狀態(tài)轉(zhuǎn)移，達到目標狀態(tài)。,搜索基礎,搜索是常人最容易想到的解題辦法，可以說所有題都可以用搜索解決，但是沒有剪枝搜索可以看成是窮舉法，時間上無法忍受,15,8皇后問題,給定8*8棋盤，要在上邊放子，要 求各棋子在同一行，同一列，同 一斜邊上不能有兩個或兩個以上的子，找到所有的放子方法，并輸出放子過程與種類數(shù)。,16,深搜：可運行代碼在備注中,17,一個從起始狀態(tài)到達目標狀態(tài)包含多步操作，而每一步操作又有幾種可能，只有正確的操作才能達到目標（如八皇后問題），這樣的問題可以看做是一個樹。 如果按照1-2-4-5-3-6-7的順序，叫深度優(yōu)先(DFS) 如果按照1-2-3-4-5-6-7的順序，叫廣度優(yōu)先(BFS),概述,18,void DFS(int k) /處理第k步 if (k=n) /已經(jīng)處理到第n步，到達目的狀態(tài) 輸出結(jié)果 else /處理第k步 for (int i=1; i=m; i+) /第k步中有m種可能 處理第k步 DFS(k+1)；/進入第k+1步 ,深度優(yōu)先(DFS)模板：,19,幫助小明,小明參加一個搶東西的電視節(jié)目。這個節(jié)目很有意思，一共有n個東西可以拿(n50)每個參加活動的人不能拿重量超過m(m2000)的東西，而每個東西都有它的價值v，有的高有的低，幫助小明安排要拿的東西，使總價值最高。,輸入 5 12 3 5 4 6 5 3 8 9 10 8 0 0,樣例輸出： 15,20,幫助小明,這是一個0-1背包問題。 對于每件物品，有兩種選擇： 1）拿這件物品（條件是最大重量不超過m） 2）不拿這件物品 下面程序給出0-1背包的dfs解法，效率無法忍受，但是理解簡單。 下一次會介紹動態(tài)規(guī)劃的0-1背包解法效率會提升很大（備注中給出0-1背包動態(tài)規(guī)劃解法）。,21,22,POJ 1088 滑雪,Michael喜歡滑雪百這并不奇怪， 因為滑雪的確很刺激?？墒菫榱双@得速度，滑的區(qū)域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個 區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點的高度。下面是一個例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-.-3-2-1更長。事實上，這是最長的一條。,23,POJ 1088 滑雪,Input 輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 = R,C = 100)。下面是R行，每行有C個整數(shù)，代表高度h，0=h=10000。 Output 輸出最長區(qū)域的長度。,24,這個搜的重復的過程太多了，交到OJ上給個TLE,25,記憶化搜索,26,BFS,廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠一點的地方,27,28,BFS程序基本結(jié)構,定義一個隊列; 起始點加入隊列; while(隊列不空) 取出隊頭結(jié)點; 若它是所求的目標狀態(tài),跳出循環(huán); 否則，從它擴展出子結(jié)點,全都添到隊尾; 若循環(huán)中找到目標,輸出結(jié)果; 否則輸出無解;,29,POJ 2243 Knight Moves,國際象棋棋盤上有一個馬，要從起點跳到指定目標，最少跳幾步？,輸入： a1 h8 輸出： To get from a1 to h8 takes 6 knight moves.,30,跳馬規(guī)則,a b c d e f g h,1 2 3 4 5 6 7 8,在23的矩形里：,31,例如：從a1到e4,當目標出現(xiàn)在所擴展出的結(jié)點里，結(jié)果就找到了。,To get from a1 to e4 takes 3 knight moves.,32,33,34,雙向BFS,從起點、終點同時開始,雙向BFS,有效地提高了時空效率。,從起點找2步能跳到的點,從終點找1步能跳到的點,35,POJ 1745 Divisibility,輸入N、K,然后輸入N個整數(shù)，N個整數(shù)可列出若干加減運算式；若存在一個算式，它的值能被K整除,輸出“Divisible”，否則輸出“Not divisible”.,輸入： 2 4 7 17 5 -21 15 4 5 17 5 -21 15,輸出： Divisible Not divisible,36,17，5，-21，15,17,5,5,-21,-21,-21,-21,15,15,15,15,15,15,15,15,+,+,+,17 + 5 + -21 + 15,+,+,+,+,-,-,-,-,-,-,-,17 - 5 + -21 - 15,37,最壞情況N=10000，二叉樹有10000層，結(jié)點總數(shù)210000-1。不可能枚舉所有表達式,本題的目標：判斷葉子結(jié)點上是否有值能被k 整除=判斷是否有值，除以k的余數(shù)為零。 計算中間值取余，不影響結(jié)果。 (a + b) % k = ( a % k + b % k) % k,因此只需記錄對k的余數(shù)。2=k=100，每層結(jié)點最多100個，不是指數(shù)級增加。,38,4 7 17 5 -21 15,每層最多7個結(jié)點 (定義數(shù)組)：,首先加入起點，17 % 7 = 3,擴展第2層結(jié)點 (3+5) % 7 = 1 (3 5 + 7) % 7 =5,+,-,擴展第3層結(jié)點 (1+ -21) % 7 = 1 (1 -21) % 7 = 1 (5+ -21) % 7 = 5 (5 -21) % 7 = 5,擴展第4層結(jié)點 (1+ 15) % 7 = 2 (1 15) % 7 = 0 (5 + 15) % 7 = 6 (5 15) % 7 = 4,39,例3 Holedox Moving,一條長度為L“貪吃蛇”在n*m的迷宮中，求它走到出口（1，1）的最少步數(shù)。 (2L 8;1n,m 20),輸入： 5 6 4 4 1 4 2 3 2 3 1 3 2 3 3 3 3 4 0 0 0,輸出： Case 1: 9,40,蛇頭在上、下、左、右四方向上的探索過程 注意： 蛇不能