搜索問(wèn)題

    graph TB
    subgraph 盲目搜索
    深度優(yōu)先
    寬度優(yōu)先
    end
    subgraph 啟發(fā)式搜索
    A算法
    A*算法
    end

盲目搜索

深度優(yōu)先算法

沿著一個(gè)路徑按照一定規(guī)則順序搜索，直到搜到目標(biāo)，或者搜到非法值。搜到非法值時(shí)，則返回到上一個(gè)點(diǎn)。

非法值有兩種形式，一種是問(wèn)題本身定義的非法點(diǎn)（deadend），比如下棋的非法落子點(diǎn)；一種是當(dāng)前點(diǎn)已經(jīng)被充分展開(kāi)，其展開(kāi)點(diǎn)都被搜索過(guò)，最終都是非法點(diǎn)。

深度優(yōu)先算法有兩個(gè)問(wèn)題，對(duì)應(yīng)的解決方法為：

• 深度問(wèn)題
  • 可以對(duì)搜索深度加以限制
• 死循環(huán)問(wèn)題
  • 記錄從初始狀態(tài)到當(dāng)前狀態(tài)的搜索路徑

深度優(yōu)先搜索的性質(zhì)：

• 一般不能保證找到最優(yōu)解
• 當(dāng)深度限制不合理的時(shí)候可能找不到解
• 最壞的情況是窮舉
• 是一個(gè)通用方法，與問(wèn)題無(wú)關(guān)
• 節(jié)省內(nèi)存。只儲(chǔ)存從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。主要是因?yàn)榘错樞蛩阉?/li>

My Remark：

• 深度優(yōu)先是一個(gè)很好的框架，在這個(gè)框架上可以衍生出很多算法。課上給出的LISP寫的框架要理解，每一步的作用，為什么這樣做。
• 深度優(yōu)先的典型例子：四王后問(wèn)題 4Queen

寬度優(yōu)先算法

優(yōu)先擴(kuò)展深度淺的結(jié)點(diǎn)
學(xué)寬度優(yōu)先的時(shí)候第一次引入了OPEN表和CLOSE表（大概？）那節(jié)課沒(méi)去聽(tīng)不知道怎么講的。

每一層每一層展開(kāi)，對(duì)于每一層，遍歷OPEN表，展開(kāi)之后把父結(jié)點(diǎn)放進(jìn)CLOSE表中。

寬度優(yōu)先算法的性質(zhì)：

• 當(dāng)問(wèn)題有解時(shí)，一定能找到解
• 當(dāng)問(wèn)題為單位耗散值，且有解時(shí)，一定能找到最優(yōu)解
• 與寬度優(yōu)先一樣，有通用性
• 效率比較低
• 儲(chǔ)存量大

My Remark
感覺(jué)寬度優(yōu)先不是很有用，特別是問(wèn)題比較復(fù)雜（可能的情況很多）的時(shí)候。
迭代加深搜索

寬度優(yōu)先和深度優(yōu)先都有明顯的缺點(diǎn)，所以就有了這個(gè)迭代加深搜索，來(lái)解決上述兩個(gè)方法不能找到最優(yōu)解的問(wèn)題。主要思想是給深度優(yōu)先方法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解，或者遍歷全局（反正最后都是有可能遍歷全局還找不到解的啊www）。

迭代加深搜索的計(jì)算時(shí)間分析

對(duì)于一個(gè)滿b叉樹(shù)，設(shè)最佳深度為d，則：

• 寬度優(yōu)先產(chǎn)生的節(jié)點(diǎn)數(shù)：
  N_{SF}=\sum_{i=0}^u0z1t8osb{i}=\dfrac{b^{d+1}-1}{b-1}
• 迭代加深搜索產(chǎn)生的節(jié)點(diǎn)數(shù)：
  N_{IDBT}=\sum_{i=0}^b(d-i+1)bi=\dfrac{b-1}N_{BF}-\dfrac{d+1}{b-1}
• b>2\Rightarrow N_{IDBT}<\dfrac{b-1}N_{BF}

啟發(fā)式搜索

相比盲目搜索的。盲目搜索相當(dāng)于，要么優(yōu)先深度，要么優(yōu)先寬度，按照指定的方法來(lái)搜，跟問(wèn)題沒(méi)有關(guān)系。事實(shí)上我們總是能對(duì)問(wèn)題做出一些基礎(chǔ)分析，來(lái)降低搜索的工作量。這些基礎(chǔ)分析，構(gòu)成啟發(fā)信息，就是啟發(fā)式搜索了。所以啟發(fā)式搜索方法的一個(gè)顯著優(yōu)點(diǎn)是可以降低工作量。但是因?yàn)橛幸恍┮龑?dǎo)信息，所以可能找到的解不是最優(yōu)解。而且由于需要計(jì)算啟發(fā)信息，在最差的情況下，退化成盲目搜索，而且比盲目搜索工作量大（但是很少這么倒霉的啦）。

A算法

定義評(píng)價(jià)函數(shù)：

    f(n)=g(n)+h(n)
    
其中，f(n)為評(píng)價(jià)函數(shù)，h(n)為啟發(fā)函數(shù)

通俗地解釋，對(duì)于結(jié)點(diǎn)n，g是從起點(diǎn)到n的最短路徑（嚴(yán)格地說(shuō)，最短路徑的耗散值），h是n到目標(biāo)點(diǎn)的最短路徑的耗散值。定義f為g和h的和，顯然這個(gè)f是可以評(píng)價(jià)n這個(gè)結(jié)點(diǎn)的好壞的。

My Remarks

• A算法的一個(gè)例子是8數(shù)碼問(wèn)題。從這個(gè)例子可以感受到啟發(fā)式算法還是很神奇的。

A*算法

在A算法中，如果滿足條件：

$h(n)\leq h^*(n)$

那么稱A算法為A*算法。

• A*算法的兩個(gè)主要結(jié)論:
  • 如果從初始結(jié)點(diǎn)到終點(diǎn)，存在路徑，那么A＊一定能找打最優(yōu)解（可采納性定理）
  • 如果$h2(n)>h1(n)$,那么有$A1$的擴(kuò)展結(jié)點(diǎn)數(shù)$\geq A2$的擴(kuò)展結(jié)點(diǎn)數(shù)。
    • 注意這里，擴(kuò)展結(jié)點(diǎn)數(shù)指的是被擴(kuò)展的結(jié)點(diǎn)的個(gè)數(shù)，也就是說(shuō)每個(gè)結(jié)點(diǎn)最多只能被記數(shù)一次。
• h函數(shù)的生成方法：其中一個(gè)方法是，放寬原問(wèn)題的條件，使原問(wèn)題變?yōu)橐粋€(gè)易于求解h的問(wèn)題，用這個(gè)新問(wèn)題的h＊來(lái)代替h。

Vital Remarks

• A算法的停止條件，是到達(dá)目標(biāo)點(diǎn)（h（n）＝0），且目標(biāo)點(diǎn)的f值在OPEN表中最小。這一點(diǎn)需要特別注意，因?yàn)橛械臅r(shí)候，雖然達(dá)到了目標(biāo)點(diǎn)，但是并不是最優(yōu)路徑，或者并不是最優(yōu)目標(biāo)點(diǎn)。
• 在一些例子中，會(huì)發(fā)現(xiàn)，有些節(jié)點(diǎn)會(huì)被多次拓展。這是因?yàn)?，這個(gè)被多次拓展的結(jié)點(diǎn)，在第一次被拓展的時(shí)候，并不是按照最優(yōu)路徑拓展的。為了避免這種多次拓展，可以采取以下兩種方法：
  • 對(duì)h加以限制。如果h是單調(diào)的，那么就可以避免多次拓展。
    • h單調(diào)的定義：如果一個(gè)父結(jié)點(diǎn)到子節(jié)點(diǎn)的耗散值，大于子節(jié)點(diǎn)的h和父結(jié)點(diǎn)h之差，或者h(yuǎn)＝0，那么h是單調(diào)的。（h單調(diào)的本質(zhì)是，任何一個(gè)路徑，f的變化趨勢(shì)與g是一致的，不回因?yàn)閔的變化，使得f和g的變化趨勢(shì)不同。）
    • h單調(diào)是A＊算法的必要條件。（由h單調(diào)的定義，用反證法可以輕易證明。）
  • 對(duì)算法進(jìn)行修正。修正過(guò)程A：令$f_m$是目前已經(jīng)擴(kuò)展的結(jié)點(diǎn)中，最大的f。在進(jìn)行下一步拓展時(shí)，選取f值比$f_m$小的結(jié)點(diǎn)，形成NEST表。選取NEST表中g(shù)值最小的點(diǎn)進(jìn)行拓展。
    • 由于h＝0時(shí)，h是單調(diào)的，所以修正過(guò)程A中的h也是單調(diào)的，也就避免了重復(fù)擴(kuò)展的問(wèn)題。