搜索及其優(yōu)化.

1、搜索及其優(yōu)化 楊志燦 搜索 搜索樹 初始狀態(tài) 目標(biāo)狀態(tài) 狀態(tài)的表示與擴(kuò)展 圖搜索 N皇后 搜索 狀態(tài)的擴(kuò)展順序 深度優(yōu)先搜索 DFS(Depth-First Search) 優(yōu)先擴(kuò)展新狀態(tài) 遞歸/回溯/人工棧 寬度優(yōu)先搜索 BFS(Breadth-First Search） 依狀態(tài)的產(chǎn)生順序擴(kuò)展 隊(duì)列 Spiders 通過(guò)將一棵樹的某個(gè)節(jié)點(diǎn)與另一棵樹的節(jié)點(diǎn)合并使兩棵樹 合并為新的樹 給定n棵樹，將其合并為一棵樹，使新樹的最長(zhǎng)鏈盡量長(zhǎng)， 輸出長(zhǎng)度 1=n=100， 樹大小=100 CodeForces 120 F Spiders 新樹的最長(zhǎng)鏈等于n棵樹最長(zhǎng)鏈長(zhǎng)度之和。 求最長(zhǎng)鏈 從樹的每個(gè)節(jié)點(diǎn)D

2、FS/BFS，不斷更新最長(zhǎng)鏈長(zhǎng)度。 O(n2) 從樹的任意一個(gè)節(jié)點(diǎn)DFS/BFS，找出距離最遠(yuǎn)的點(diǎn)P，從點(diǎn)P進(jìn)行 DFS/BFS，再次求最遠(yuǎn)的點(diǎn)Q，PQ即為最長(zhǎng)鏈。 O(n) DP O(n) 迭代加深搜索 DFS在一些問(wèn)題模型中可能無(wú)限擴(kuò)展 如8數(shù)碼問(wèn)題 增加深度限制：假設(shè)目標(biāo)狀態(tài)所處深度不超過(guò)某閾值。 問(wèn)題條件或人為假設(shè) 當(dāng)搜索深度到達(dá)閾值時(shí)直接剪枝，不再往下搜索。 迭代加深搜索 Iterative Deepening Depth-First Search 求最優(yōu)/深度最低/步數(shù)最少解 不斷放寬迭代深度限制 第一次找到的目標(biāo)狀態(tài)即為最優(yōu)解 與DFS不同 何時(shí)用IDDFS而不用BFS 空間限制

3、極強(qiáng)時(shí) 時(shí)間限制內(nèi)求較優(yōu)解 計(jì)算機(jī)博弈、規(guī)劃等 當(dāng)狀態(tài)的存儲(chǔ)與表示比較麻煩/費(fèi)時(shí)時(shí) 迭代加深搜索 效率對(duì)比 設(shè)解所在深度為d，每個(gè)狀態(tài)都能擴(kuò)展出b個(gè)狀態(tài)。 BFS Nbfs=1+b+b2+bd = (bd+1-1)/(b-1) IDDFS (d+1)+d*b+(d-1)*b2+2bd-1+bd = b/(b-1) * (bd+1-1)/(b-1) - (d+1)/(b-1) = b/(b-1)*Nbfs - (d+1)/(b-1) 兩種算法的擴(kuò)展節(jié)點(diǎn)數(shù)漸進(jìn)相同 雙向廣度搜索 從初始狀態(tài)和目標(biāo)狀態(tài)兩個(gè)方向BFS 用hash等方法將兩者的搜索路徑相接 例 八數(shù)碼 雙向廣度搜索 效率對(duì)比 設(shè)解所在深

4、度為d，每個(gè)狀態(tài)都能擴(kuò)展出b個(gè)狀態(tài)。 BFS Nbfs=1+b+b2+bd = (bd+1-1)/(b-1) Bidirectional BFS (1+b+b2+bd/2) * 2 = 2 * (bd/2+1-1)/(b-1) Hash/數(shù)據(jù)結(jié)構(gòu)判重 Knight Moves 一個(gè)L*L的象棋棋盤，給定馬的起點(diǎn)和終點(diǎn)，求最少步數(shù) 4 = L = 300 POJ 1915 可行性剪枝 在搜索的同時(shí)，實(shí)時(shí)判斷是否可能存在可行解 若不可能存在任何可行解，進(jìn)行剪枝 判斷方法 放縮、放寬條件限制 舉例 精確覆蓋問(wèn)題 重復(fù)覆蓋問(wèn)題 精確覆蓋問(wèn)題 Exact Cover Problem 全集X，X的子集的集

5、合為S 精確覆蓋 S的子集S*，滿足X中的每一個(gè)元素在S*中恰好出現(xiàn)一次 精確覆蓋問(wèn)題 求最小的精確覆蓋 舉例 數(shù)獨(dú) N皇后 NP完全問(wèn)題 重復(fù)覆蓋問(wèn)題 Set Cover Problem 全集X，X的子集的集合為S 重復(fù)覆蓋 S的子集S*，滿足X中的每一個(gè)元素在S*中至少出現(xiàn)一次 重復(fù)覆蓋問(wèn)題 求最小的重復(fù)覆蓋 舉例 數(shù)獨(dú) 八皇后 NP完全問(wèn)題 最優(yōu)性剪枝 在搜索的同時(shí)，實(shí)時(shí)判斷是否可能存在比當(dāng)前最優(yōu)解更優(yōu) 的解 若不可能存在比當(dāng)前最優(yōu)解更優(yōu)的解，進(jìn)行剪枝 判斷方法 放縮、放寬條件限制 可用貪心/構(gòu)造等方法預(yù)處理出一些較優(yōu)解為最優(yōu)性剪枝 提供方便 舉例 精確覆蓋問(wèn)題 重復(fù)覆蓋問(wèn)題 飄飄乎數(shù)獨(dú)

6、 飄飄乎數(shù)獨(dú)共n行，每行的數(shù)字都由1m自然數(shù)填滿（每 行中每個(gè)數(shù)字用且只能用一次） 3=n, m Ri+1且Hi Hi+1。 希望蛋糕外表面（最下一層的下底面除外）的面積Q最小。 令Q = S 對(duì)給出的N和M，找出蛋糕的制作方案（適當(dāng)?shù)腞i和Hi的 值），使S最小。 （除Q外，以上所有數(shù)據(jù)皆為正整數(shù)） N = 10000, M = 20 NOI 1999 生日蛋糕 體積V = R2H 側(cè)面積A = 2RH 底面積A = R2 DFS 從下到上確定每層蛋糕的半徑與高度 可行性剪枝 最大化體積 N 最優(yōu)性剪枝 最大化表面積 堆/平衡樹 優(yōu)點(diǎn) 相比盲目搜索，更快搜索到較/最優(yōu)解 使最優(yōu)性剪枝更強(qiáng)，避

7、免大量無(wú)用搜索/分支 A算法 八數(shù)碼問(wèn)題 h(n) 不在位的數(shù)字個(gè)數(shù) 不在位的數(shù)字的距離和 h(n)=0 無(wú)后效性 動(dòng)態(tài)規(guī)劃 Dijkstra A算法可能/需要重復(fù)擴(kuò)展節(jié)點(diǎn) 極端舉例：h是隨機(jī)值 A*算法 若滿足h(n)=h*(n)，則稱為A*算法 A*第一次擴(kuò)展目標(biāo)節(jié)點(diǎn)t時(shí)，就找到了最優(yōu)解 要求耗散值均為非負(fù)數(shù) 證明順序： 在有限問(wèn)題中，若存在可行解，A算法一定成功結(jié)束 A*結(jié)束前，必存在f(n)f*(s)的待擴(kuò)展節(jié)點(diǎn)（n是在最佳路徑上的 節(jié)點(diǎn)） A*選作擴(kuò)展的任一節(jié)點(diǎn)n，有f(n)f*(s) 任一f(n)h1(n)） 則A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié) 點(diǎn)至少和A

8、2一樣多 K短路 在有向/無(wú)向有權(quán)無(wú)負(fù)環(huán)圖中，求s到t的K短路 兩條路不同，當(dāng)且僅當(dāng)訪問(wèn)節(jié)點(diǎn)序列不同 解法 h(n)為n到t的最短路 從t出發(fā)倒著做一遍最短路求h() 第i次擴(kuò)展目標(biāo)節(jié)點(diǎn)t時(shí)即為i短路 只需維護(hù)f值前k小的待擴(kuò)展節(jié)點(diǎn) 傳教士和野人 N個(gè)傳教士和N個(gè)野人準(zhǔn)備渡河，河岸有一條船，每次至 多可供k人乘渡 為了安全起見，任何時(shí)刻在河的兩岸以及船上的野人數(shù)目 總是不超過(guò)傳教士的數(shù)目（但允許在河的某一岸只有野人 而沒(méi)有傳教士） 求最少擺渡次數(shù) 傳教士和野人 啟發(fā)式搜索 常用方法 優(yōu)先搜索分支少、限制多的 精確覆蓋問(wèn)題 重復(fù)覆蓋問(wèn)題 優(yōu)先搜索更有可能出最優(yōu)解的 A算法 A*算法 myster

9、ious permutation 給定一數(shù)字串，求有多少分隔方法，使其成為從1開始的 自然數(shù)的全排列 例：13927111104831265 排列1：13,9,2,7,1,11,10,4,8,3,12,6,5 排列2：13,9,2,7,11,1,10,4,8,3,12,6,5 數(shù)字串長(zhǎng)度不超過(guò)192 mysterious permutation 數(shù)字串長(zhǎng)度不超過(guò)192 數(shù)字從1至多到100 直覺(jué)上可行解數(shù)目不多 搜索 預(yù)處理篩出無(wú)解情況 數(shù)字個(gè)數(shù)不對(duì) 某個(gè)數(shù)字從沒(méi)出現(xiàn)過(guò) 多于5個(gè)相同連續(xù)數(shù)字 mysterious permutation 只需搜索11至99的位置 因沒(méi)有前導(dǎo)零，故100和整十的位置固定 搜索完二位數(shù)和三位數(shù)后，1至9必然有且只有一種填法 優(yōu)先搜索可填入位置少的數(shù)字 實(shí)時(shí)維護(hù)可填入位置數(shù) 攻占黃金鄉(xiāng) 一個(gè)長(zhǎng)方體空間，用(0,0,0)(n-1,m-1,k-1)表示里面的 每一個(gè)單位區(qū)域 t艘不同等級(jí)的戰(zhàn)艦出現(xiàn)在t個(gè)不同的區(qū)域，從戰(zhàn)艦上涌出 山羊。 每一個(gè)單位時(shí)刻，山羊們會(huì)從自己所在的區(qū)域向四周6個(gè) 方向擴(kuò)展一個(gè)區(qū)域（如果那個(gè)相鄰的區(qū)域已經(jīng)被占領(lǐng)了， 就不擴(kuò)展），如