记忆化搜索的研究
記憶化搜索：
?
算法上依然是搜索的流程，但是搜索到的一些解用動(dòng)態(tài)規(guī)劃的那種思想和模式作一些保存。
一般說(shuō)來(lái)，動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無(wú)效狀態(tài)。
更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開(kāi)銷上往往比動(dòng)態(tài)規(guī)劃要低很多。
記憶化算法在求解的時(shí)候還是按著自頂向下的順序，但是每求解一個(gè)狀態(tài)，就將它的解保存下來(lái)，以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。這種方法綜合了搜索和動(dòng)態(tài)規(guī)劃兩方面的優(yōu)點(diǎn)，因而還是很有實(shí)用價(jià)值的。上傳/更換附件動(dòng)態(tài)規(guī)劃的另一種實(shí)現(xiàn)形式——記憶化搜索的應(yīng)用。
?
動(dòng)態(tài)規(guī)劃和記憶化搜索：
?
動(dòng)態(tài)規(guī)劃：就是一個(gè)最優(yōu)化問(wèn)題，先將問(wèn)題分解為子問(wèn)題，并且對(duì)于這些分解的子問(wèn)題自身就是最優(yōu)的才能在這個(gè)基礎(chǔ)上得出我們要解決的問(wèn)題的最優(yōu)方案，要不然的話就能找到一個(gè)更優(yōu)的解來(lái)替代這個(gè)解，得出新的最優(yōu)自問(wèn)題，這當(dāng)然是和前提是矛盾的。動(dòng)態(tài)規(guī)劃不同于 貪心算法，因?yàn)樨澬乃惴ㄊ菑木植孔顑?yōu)來(lái)解決問(wèn)題，而動(dòng)態(tài)規(guī)劃是全局最優(yōu)的。用動(dòng)態(tài)規(guī)劃的時(shí)候不可能在子問(wèn)題還沒(méi)有得到最優(yōu)解的情況下就做出決策，而是必須等待子問(wèn)題得到了最優(yōu)解之后才對(duì)當(dāng)下的情況做出決策，所以往往動(dòng)態(tài)規(guī)劃都可以用 一個(gè)或多個(gè)遞歸式來(lái)描述。而貪心算法卻是先做出一個(gè)決策，然后在去解決子問(wèn)題。這就是貪心和動(dòng)態(tài)規(guī)劃的不同。
一般遇到一個(gè)動(dòng)態(tài)規(guī)劃類型的問(wèn)題，都先要確定最優(yōu)子結(jié)構(gòu)，還有重疊子問(wèn)題，這兩個(gè)是動(dòng)態(tài)規(guī)劃最大的特征，然后就是要寫 動(dòng)態(tài)規(guī)劃的?狀態(tài)方程，這個(gè)步驟十分十分的重要的，寫動(dòng)歸方程是需要一定的經(jīng)驗(yàn)的，這可以通過(guò)訓(xùn)練來(lái)達(dá)到目的。接著就是要自底向上的求解問(wèn)題的，先將最小規(guī)模的子問(wèn)題的最優(yōu)解求出，一般都用一張表來(lái)記錄下求得的解，到后來(lái)遇到同樣的子問(wèn)題的時(shí)候就可以直接查表得到答案，最后就是通過(guò)一步一步的迭代得出最后問(wèn)題的答案了。
我的理解最重要的東西就是一定會(huì)要一個(gè)數(shù)組或者其他的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)得到的子問(wèn)題的解。這樣就可以省很多時(shí)間，也就是典型的空間換時(shí)間
動(dòng)態(tài)規(guī)劃的一種變形就是記憶化搜索，就是根據(jù)動(dòng)歸方程寫出遞歸式，然后在函數(shù)的開(kāi)頭直接返回以前計(jì)算過(guò)的結(jié)果，當(dāng)然這樣做也需要一個(gè)存儲(chǔ)結(jié)構(gòu)記下前面計(jì)算過(guò)的結(jié)果，所以又稱為記憶化搜索。
?
記憶化搜索/遞歸式動(dòng)態(tài)規(guī)劃：
?
1.記憶化搜索的思想
????記憶化搜索的思想是,在搜索過(guò)程中，會(huì)有很多重復(fù)計(jì)算,如果我們能記錄一些狀態(tài)的答案，就可以減少重復(fù)搜索量
2、記憶化搜索的適用范圍
????根據(jù)記憶化搜索的思想，它是解決重復(fù)計(jì)算，而不是重復(fù)生成，也就是說(shuō)，這些搜索必須是在搜索擴(kuò)展路徑的過(guò)程中分步計(jì)算的題目，也就是“搜索答案與路徑相關(guān)”的題目，而不能是搜索一個(gè)路徑之后才能進(jìn)行計(jì)算的題目，必須要分步計(jì)算，并且搜索過(guò)程中，一個(gè)搜索結(jié)果必須可以建立在同類型問(wèn)題的結(jié)果上，也就是類似于動(dòng)態(tài)規(guī)劃解決的那種。
也就是說(shuō)，他的問(wèn)題表達(dá)，不是單純生成一個(gè)走步方案，而是生成一個(gè)走步方案的代價(jià)等，而且每走一步，在搜索樹(shù)/圖中生成一個(gè)新?tīng)顟B(tài)，都可以精確計(jì)算出到此為止的費(fèi)用，也就是，可以分步計(jì)算，這樣才可以套用已經(jīng)得到的答案
3、記憶化搜索的核心實(shí)現(xiàn)
?????a.?首先，要通過(guò)一個(gè)表記錄已經(jīng)存儲(chǔ)下的搜索結(jié)果，一般用哈希表實(shí)現(xiàn)
?????b.狀態(tài)表示，由于是要用哈希表實(shí)現(xiàn)，所以狀態(tài)最好可以用數(shù)字表示，常用的方法是把一個(gè)狀態(tài)連寫成一個(gè)p進(jìn)制數(shù)字，然后把這個(gè)數(shù)字對(duì)應(yīng)的十進(jìn)制數(shù)字作為狀態(tài)
????c.在每一狀態(tài)搜索的開(kāi)始，高效的使用哈希表搜索這個(gè)狀態(tài)是否出現(xiàn)過(guò)，如果已經(jīng)做過(guò)，直接調(diào)用答案，回溯
????d.如果沒(méi)有，則按正常方法搜索
4、記憶化搜索是類似于動(dòng)態(tài)規(guī)劃的，不同的是，它是倒做的“遞歸式動(dòng)態(tài)規(guī)劃”。
?
?
?下面POJ 1691 paint a borad的題目：
?
先用普通的深度優(yōu)先搜索來(lái)解答。
在這道題中需要注意的是：
1、如何記錄某個(gè)矩形的信息，這里包括了坐標(biāo)、顏色、是否涂色、上方矩形的個(gè)數(shù)、下方有哪幾個(gè)矩形。
這些都是從便于程序設(shè)計(jì)的角度抽象出來(lái)的。
2、為了得到最少使用刷子的次數(shù)，涂色策略應(yīng)該為：把當(dāng)前可以涂色的矩形全部涂色。
3、還需要注意如何通過(guò)坐標(biāo)判斷：緊鄰的處于上方的矩形
?
[cpp]?view plaincopy
?
通過(guò)這道題可以看到dfs搜索算法的特點(diǎn)是這樣的：
?
核心的搜索算法一般使用遞歸的形式，而且遞歸函數(shù)的參數(shù)往往直接和問(wèn)題的求解對(duì)象有一定的關(guān)聯(lián)。還有就是，在搜索算法函數(shù)的開(kāi)頭一般先放上剪枝條件，這樣主要是起到回溯的作用，否則的話，函數(shù)就會(huì)無(wú)限遞歸了。可以發(fā)現(xiàn)對(duì)深度搜索進(jìn)行合適的剪枝可以大大提高搜索的效率。另外，在執(zhí)行遞歸之前，一般先對(duì)當(dāng)前的局面狀態(tài)進(jìn)行保存，在遞歸函數(shù)返回時(shí)，在進(jìn)行恢復(fù)。這有點(diǎn)類似于回溯算法的特點(diǎn)。其實(shí)dfs函數(shù)的參數(shù)表示的就是局面的一種狀態(tài)。
?
?
下面對(duì)于這個(gè)問(wèn)題使用記憶化搜索算法：
總結(jié)
- 上一篇： poj2362 DFS+剪枝
- 下一篇： HDU1978 记忆化搜索