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

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