算法合集之《匹配算法在搜索問題中的應(yīng)用》.ppt

匹配算法在搜索問題中的應(yīng)用 浙江省杭州第十四中學(xué)樓天城loutiancheng 很多題目 如果我們可以建立數(shù)學(xué)模型 應(yīng)該盡量用解析法來處理 因為簡單的模型更清晰地反映了事物之間的關(guān)系 但是 并不是所有的題目都可以建立簡單的數(shù)學(xué)模型 我們這時必須使用搜索的方法 也就是枚舉所有可能情況來尋找可行解或最優(yōu)解 前言 由于搜索一般建立在枚舉之上 所以搜索常常和低效是分不開的 有時搜索的運算量非常大 實在是一件痛苦的事情 于是我們需要利用很多技巧來提高效率 可行性剪枝 最優(yōu)性剪枝 調(diào)整搜索順序 等方法都很有用 在它們的幫助下 我們可以大大提高搜索的效率 而有些題目 這些常規(guī)的優(yōu)化方法很難有用武之地 這時我們必須使用一些非常規(guī)的搜索方法 本文中我們將討論非常規(guī)搜索中的一種 部分搜索 匹配算法 引題 N個物品與N個位置 給定每個物品可能放的位置集合 要求尋找一一對應(yīng)的關(guān)系 但還給出物品位置之間的限制 例如 如果1放在3則2不能放在1 求一組可行解 或給每一種對應(yīng)關(guān)系一個權(quán) 求滿足條件的最優(yōu)解 由于事物之間的限制關(guān)系非常復(fù)雜 很難建立簡單的二分圖關(guān)系 或者用網(wǎng)絡(luò)流來解決 面對這一系列類似的問題 我們一般只有搜索 如何搜索又如何優(yōu)化呢 簡單分析 如果我們枚舉每一個物品的位置 然后判斷 這樣的時間復(fù)雜度為O n 好像似乎也只能這樣 進(jìn)一步分析 我們看一個例子 n 6 其它限制有4條 a b c d 表示如果a放在b則c不能放在d1356225331413262我們發(fā)現(xiàn) 如果我們一旦確定了3和5的位置 其它4個物品的位置之間已經(jīng)沒有限制關(guān)系了 這樣其它4個物品的位置可以通過匹配來解決 這時我們發(fā)現(xiàn)一個新的搜索方法 部分搜索 匹配 1356225331413262 部分搜索 匹配 搜索一部分變量 使得余下變量之間的關(guān)系簡化 然后通過一些高效算法 匹配 完成余下問題 就本題而言就是 先搜索一定數(shù)量 而不是全部 物品的位置 使問題內(nèi)其它物品的關(guān)系簡化為二分圖關(guān)系 用二分圖匹配來解決余下的物品 通過部分搜索為匹配算法提供條件 例如上面的例子創(chuàng)造二分圖關(guān)系 而匹配算法代替搜索 高效地完成余下的任務(wù) 部分搜索 匹配的方法充分發(fā)揮了搜索和匹配算法的雙重優(yōu)勢 搜索的優(yōu)勢在于應(yīng)用性廣 可以克服復(fù)雜的情況 匹配算法的優(yōu)勢在于效率高 兩者相互促進(jìn) 同時也彌補對方的不足 這也是這個方法成功的關(guān)鍵 例如上面的例子 如果我們先知道了3和5的位置后 不用匹配 其實我們是在用搜索來求匹配 效率當(dāng)然不會高 部分搜索 匹配的方法已經(jīng)在很多題目中得到了應(yīng)用 一個部分搜索 匹配算法的經(jīng)典例子 智破連環(huán)陣 題目簡述 NOI2003二試第三題 B國的連環(huán)陣由M個武器組成 最初 1號武器處于攻擊狀態(tài) 其他武器都處在無敵自衛(wèi)狀態(tài) 以后 一旦第i 1 i M 號武器被消滅 1秒鐘以后第i 1號武器就自動從無敵自衛(wèi)狀態(tài)變成攻擊狀態(tài) A國有N個炸彈 每個炸彈的作用半徑均為k 且會持續(xù)爆炸5分鐘 在這5分鐘內(nèi) 瞬間消滅離它直線距離不超過k的 處在攻擊狀態(tài)的B國武器 不會炸毀本國炸彈 任務(wù) 決定一個序列a1 a2 a3 使得在第ax號炸彈引爆的時間內(nèi)連環(huán)陣被摧毀 這里的x應(yīng)當(dāng)盡量小 輸入 N M及武器和炸彈的坐標(biāo) 測試數(shù)據(jù)中的坐標(biāo)是隨機生成的 初步分析 A國炸彈i可以炸到B國武器j的條件 u i x j 2 v i y j 2 R2 結(jié)論 很難找到求最優(yōu)解的多項式算法 面對此類問題 一般只有搜索策略 進(jìn)一步分析 每一顆炸彈必定炸掉B國武器中編號連續(xù)的一段 5分鐘只是表明每一顆炸彈可以炸掉任意多個編號連續(xù)的B國武器 普通的搜索方法 每次尋找一個編號最小的沒有被炸掉的B國武器 選擇一顆沒有使用過并能炸到此武器的A國炸彈 然后使用這顆炸彈炸掉B國武器連續(xù)的一段 繼續(xù)深度優(yōu)先搜索下一顆炸彈的編號 如果發(fā)現(xiàn)B國武器已經(jīng)全部炸毀就可以回溯 搜索的時間復(fù)雜度為O n 即使加上優(yōu)化 程序效率也不是很高 部分搜索 此題使用部分搜索的算法需要一些轉(zhuǎn)化 如果已經(jīng)將B國武器根據(jù)編號分為x段 其中第i段為 Si Ti S1 1 Ti Si Ti 1 Si 1 然后的任務(wù)就是判斷是否可以從A國的N顆炸彈中選出x顆 分別可以炸掉其中的一段 其實我們把搜索分為了兩部分 將B國武器根據(jù)編號分為x段 判斷是否可以從A國的N顆炸彈中選出x顆 分別可以炸掉其中的一段 其實第二部分可以用匹配來解決 建圖 C S T I 表示A國炸彈I是否可以炸到B國武器S S 1 T 1 T C S S I u I x S 2 v I y S 2 R2 C S T I C S T 1 I C T T I S T 求C的時間復(fù)雜度為O n3 建圖 左邊x個點 表示B國武器根據(jù)編號分為的x段 右邊N個點 表示A國的N顆炸彈 左邊第i個點到右邊第j個點有邊的條件即 C Si Ti j 下面任務(wù)就是將B國武器根據(jù)編號劃分為若干段 二分圖匹配判斷 樣例1 43606666000150311 性能分析 1 搜索的基本框架已經(jīng)建立 雖然數(shù)據(jù)是隨機生成的 但是m個B國武器的劃分方案還是非常多的 有時可能高達(dá)2m 時間上很難承受 如果使用卡時 正確性受到影響 效果不會很好 只有4個數(shù)據(jù)可以在時限內(nèi)出解 另外6個如果卡時 有2個也可以得到最優(yōu)解 優(yōu)化 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析 優(yōu)化一 最優(yōu)性 如果A國炸彈可以重復(fù)使用 設(shè) Dist i 炸掉B國武器i m的最少使用炸彈數(shù) 可以用動態(tài)規(guī)劃計算Dist值 狀態(tài)轉(zhuǎn)移方程如下 Dist m 1 0 Dist i min Dist j 1 C i j 1 k 0 k n 1 i N i j N 1 求Dist的時間復(fù)雜度為O n3 從而產(chǎn)生了一個最優(yōu)性剪枝條件 if 當(dāng)前已經(jīng)使用的炸彈數(shù) Dist 當(dāng)前已經(jīng)炸掉的B國武器數(shù) 1 當(dāng)前找到的最優(yōu)解 then剪枝 優(yōu)化二 可行性 部分搜索 匹配的方法一般都可以用兩個效果很好的可行性優(yōu)化 1 提前判斷是否可以匹配成功 避免多余的搜索 2 每次匹配可以從以前的匹配開始擴展 不需要重新開始 如果當(dāng)前的劃分方法已經(jīng)無法匹配成功 就沒有搜索下去的必要了 只要每搜索新的一段時立即通過匹配判斷即可 每次求匹配只要從原來的基礎(chǔ)上擴展就可以了 沒有必要從頭開始 性能分析 2 通過上述兩個優(yōu)化 程序效率有了很大提高 10個測試數(shù)據(jù)中有8個可以在時限內(nèi)出解 另外2個如果卡時 也可以得到最優(yōu)解 進(jìn)一步優(yōu)化 優(yōu)化二雖然排除了許多不必要的劃分 但是在判斷時浪費了不少時間 因此 在枚舉劃分長度時 可以通過以前的劃分和匹配情況 被匹配的邊 用O n2 的時間復(fù)雜度的寬度優(yōu)先搜索計算出下一個劃分的最大長度maxL 顯然下一個劃分的長度在 1 maxL 都一定可以找到可行的匹配 這樣既節(jié)省了判斷的時間 又可以使每次劃分長度從長到短枚舉 使程序盡快逼近最優(yōu)解 從而同時增強剪枝條件一的效果 這一部分的實現(xiàn) 首先需要求MaxT MaxT i S 炸彈i 從S開始炸 可以炸到的最大編號 如果 炸彈i炸不到S 則MaxT i S S 1 求MaxT i S 可以用動態(tài)規(guī)劃的方法解決 狀態(tài)轉(zhuǎn)移方程為 MaxT i S 炸彈i炸不到SS 1炸彈I炸得到SMaxT I S 1 MaxT I m 1 m求MaxT的時間復(fù)雜度為O n2 具體實現(xiàn)方法 考慮二分圖右邊的n個結(jié)點 n顆炸彈 如果結(jié)點i未匹配 則i被認(rèn)為可以使用 如果結(jié)點i已匹配 假如從任何一個未匹配點出發(fā)存在一條到達(dá)i的交錯路 并且i為外點 則i也被認(rèn)為可以使用 所以maxL Max maxT i S i可以使用 具體實現(xiàn)方法 計算所有從未匹配點出發(fā)的交錯路所能到達(dá)的已匹配點 從每一個未匹配點出發(fā) 寬度優(yōu)先搜索 只要O n2 的時間 可以證明 從未匹配點出發(fā)的交錯路上的已匹配點一定為外點 注意判斷重復(fù) 如果一個已匹配點已經(jīng)被確定為可以使用 那么不需要對它再擴展一次 因為當(dāng)把這個已匹配點確定為可以使用的結(jié)點的時候 已經(jīng)從這個結(jié)點擴展過 如果再擴展必將產(chǎn)生無謂的重復(fù) 如果已經(jīng)求出了MaxL 可以先求一組長度為MaxL的匹配A 這樣對于所有長度在1 MaxL范圍內(nèi)的劃分 A都是一組可行匹配 擴展一次增廣路的復(fù)雜度為O n2 這樣大大節(jié)省了優(yōu)化二的時間 性能分析 3 通過以上的優(yōu)化 所有數(shù)據(jù)都是瞬間出解 并且所有結(jié)果都是最優(yōu)解 甚至對n 200的隨機數(shù)據(jù) 也可以在瞬間出解 可見程序的效率有了很大的提高 總結(jié) 本文中的兩個例子都可以應(yīng)用部分搜索 匹配的方法高效解決 它們在思想上有著明顯的相同點 一般的思維過程如下 一般的優(yōu)化包括 1 提前通過匹配判斷 避免多余的搜索 2 判斷時盡可能充分利用以前的結(jié)果 減少匹配的重復(fù)運算 部分搜索同樣可以和解方程 貪心 動態(tài)規(guī)劃等高效算法結(jié)合 部分搜索 匹配算法體現(xiàn)了搜索與其他方法的有機結(jié)合 充分發(fā)揮兩者的長處 相互彌補對方的不足 這