搜索算法在經(jīng)典問(wèn)題中的運(yùn)用

《搜索算法在經(jīng)典問(wèn)題中的運(yùn)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、搜索算法在經(jīng)典問(wèn)題中的運(yùn)用搜索方式經(jīng)典問(wèn)題深度優(yōu)先搜索（DeepFirstSearch）求割頂和割邊求有向圖中的強(qiáng)連通分量求歐拉回路Hanoi塔等遞歸求解問(wèn)題廣度優(yōu)先搜索（BroadFirstSearch）求單源最短路徑（迭代的思想）特別的，當(dāng)任兩點(diǎn)間的權(quán)值都相等時(shí)，廣度優(yōu)先搜索的時(shí)間復(fù)雜度為O（n+e），優(yōu)于傳統(tǒng)的Dijkstra算法。求網(wǎng)絡(luò)流問(wèn)題中的增廣軌表中所列大部分都是圖論中的基礎(chǔ)問(wèn)題，很多題目都以其為基本模型而出。可見(jiàn)，搜索算法早已成為選手必須掌握的基本功，而它廣泛的靈活性和實(shí)用性則是以下我們所要探討的關(guān)鍵。3.1.2常用的搜索算法一迭代加深搜索先限定搜索樹(shù)的最

2、大深度MaxDeep再搜索。如果無(wú)解就加大MaxDeep繼續(xù)搜。雖然這樣進(jìn)行了很多重復(fù)的工作，但是由于搜索的工作量與深度成指數(shù)關(guān)系，因此上一次（重復(fù)的）工作量比起當(dāng)前的搜索量來(lái)是較小的。這種方法適用于搜索樹(shù)較寬且深、但可行解較淺的題目。這樣的題目用一般的深度優(yōu)先搜索可能陷入很深又沒(méi)有解的死胡同，而用廣度優(yōu)先搜索空間規(guī)模又難以承受。[例一]埃及分?jǐn)?shù)（OIBH練習(xí)賽試題）在古埃及，人們使用單位分?jǐn)?shù)的和(形如1/a的，a是自然數(shù))表示一切有理數(shù)。如：2/3=1/2+1/6，但不允許2/3=1/3+1/3，因?yàn)榧訑?shù)中有相同的。對(duì)于一個(gè)分?jǐn)?shù)a/b,表示方法有很多種，但是哪種最好呢？

3、首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?shù)越大越好。如：19/45=1/3+1/12+1/180，19/45=1/3+1/15+1/4519/45=1/3+1/18+1/30，19/45=1/4+1/6+1/180，19/45=1/5+1/6+1/18。最好的是最后一種，因?yàn)?/18比1/180，1/45，1/30，1/180都大。給出a，b(0

4、分母a/b=1/a1+1/a2+…+1/ann不妨設(shè)a1＜a2＜…＜an。2剪枝手段——定分母的上下界設(shè)限定的搜索層數(shù)為D，當(dāng)前搜到第C層，當(dāng)前正要枚舉分母ak，還需枚舉總和為x/y的分?jǐn)?shù)。answer[D]表示當(dāng)前最優(yōu)解中的第D個(gè)分母，如果還沒(méi)有得到解則表示正無(wú)窮。則必然有：Max(?y/x?，ak-1)+1≤ak≤Min(?(D-C+1)*y/x?，?Maxlongint/x?，answer[D]-1)枚舉的初值容易得出，但終值的確定則要用到我們一開(kāi)始對(duì)分母有序性的假設(shè)了。值得注意的是，直接限界避免了搜索過(guò)程中屢次使用可行性剪枝，一定程度上提高了程序的運(yùn)行速度。實(shí)際上

5、本題還有一種剪枝手段——借助動(dòng)態(tài)規(guī)劃預(yù)見(jiàn)后續(xù)搜索是否有意義。這一點(diǎn)將在下一節(jié)“搜索的基本優(yōu)化手段”中的“最優(yōu)性和可行性剪枝”一欄的例題“彩票問(wèn)題”中得到詳盡的分析。至此，本題已得到較好的解決。在編程過(guò)程中我們可以發(fā)現(xiàn)，迭代加深搜索具有以下特點(diǎn)：1空間耗費(fèi)小這是它最大的優(yōu)點(diǎn)。2時(shí)間效率不低雖然它確實(shí)做了一些重復(fù)的工作，但是正如前面所分析的那樣，之前的搜索量與當(dāng)前的搜索量比起來(lái)是“小巫見(jiàn)大巫”的。3便于剪枝4實(shí)現(xiàn)方便，易于調(diào)試也正是基于以上優(yōu)點(diǎn)，迭代加深的思想才被廣泛應(yīng)用于各類模型當(dāng)中。二記憶化搜索記憶化搜索可以說(shuō)是動(dòng)態(tài)規(guī)劃的搜索實(shí)現(xiàn)方式?；谟行﹦?dòng)態(tài)規(guī)劃的規(guī)劃方程不好用簡(jiǎn)單

6、的式子描述，記憶化搜索就以其簡(jiǎn)潔清晰省事的語(yǔ)言，代替了傳統(tǒng)的規(guī)劃模式。雖然說(shuō)記憶化搜索的本質(zhì)是動(dòng)態(tài)規(guī)劃——目標(biāo)明確沒(méi)有重復(fù)，但是與后者相比，它還是存在占用?？臻g過(guò)多、時(shí)間效率較低的缺點(diǎn)。因此高級(jí)選手不到萬(wàn)不得已是很少使用記憶化搜索的。[例一]選課問(wèn)題（經(jīng)典問(wèn)題）有N（N≤1000）門功課，第i門功課有Si個(gè)學(xué)分，每門功課可能有一門直接選修課（即必須選完它的直接選修課才能選這門功課），求選M門功課所得的最大學(xué)分。分析這是一道樹(shù)形結(jié)構(gòu)的動(dòng)態(tài)規(guī)劃試題，我們可以用循環(huán)實(shí)現(xiàn)，也可以用遞歸實(shí)現(xiàn)。后者稱之為記憶化搜索，本題中相對(duì)于前者可讀性更高。下面我們來(lái)介紹它的實(shí)現(xiàn)方式。1建模增設(shè)虛

7、課程γ為所有無(wú)直接選修課程的功課的直接選修課，其學(xué)分為0。本題的模型是一棵多叉樹(shù)，為了降低規(guī)劃方程的維數(shù)，先用兒子~兄弟法將其轉(zhuǎn)化成二叉樹(shù)。設(shè)F[i,j]表示在以節(jié)點(diǎn)i為根節(jié)點(diǎn)的子樹(shù)中選j個(gè)節(jié)點(diǎn)所能得到的最大分?jǐn)?shù)，其中節(jié)點(diǎn)i必選。lc為i的左兒子節(jié)點(diǎn)，rc為i的右兒子節(jié)點(diǎn)，mark[i]為第i門功課的學(xué)分。則：F[i,j]=Max(F[lc,k]+F[rc,j-k-1])+mark[i]2實(shí)現(xiàn)從根節(jié)點(diǎn)開(kāi)始遞歸求解，直至找到葉子節(jié)點(diǎn)后回溯，自底向上依次求得F函數(shù)值。在求某節(jié)點(diǎn)的F函數(shù)值時(shí)，若它的兒子節(jié)點(diǎn)的F函數(shù)值已經(jīng)求出，則直接