一、動態(tài)規(guī)劃

找到兩點間的最短路徑，找最匹配一組點的線，等等，都可能會用動態(tài)規(guī)劃來解決。

參考如何理解動態(tài)規(guī)劃中，第二個回答。冒泡

想要找到最短的從A到 Z的路徑。

貪心算法：就是每次選擇最優(yōu)。
對應到參考的回答中，是每次選擇最短的路徑，對應到python數(shù)據(jù)結構教材中，就是每次先找面額最大的硬幣。

貪心算法的缺點：
在路徑問題中，是在A到I，I到Z的過程，都可以任意選擇的。然而若是加了條件限制，比如走了I就不能再走H了。這樣即使第一步選擇了最短的路徑，也不能保證，往后走得就是最優(yōu)路徑。

窮舉算法：
為了避免上述情況的發(fā)生，我們可以走完所有的路徑，然后選擇一條最好的。這就是窮舉。
對應到教材中，就是把所有可能找零的硬幣數(shù)都列出來，然后挑最少的。

接下來就教材中的硬幣例子，說明動態(tài)規(guī)劃。

遞歸與動態(tài)規(guī)劃：
首先，對于需要找零63美分的情況。硬幣面額有1,5,10,25美分。
我們可以這么利用遞歸思想：

• 1.一開始，假設63美分的最優(yōu)解里已經(jīng)找了一個硬幣。那么這個硬幣可能是上面四個面額。mincoin=0+1=1
• 2、既然已經(jīng)找了一個硬幣，那么還剩63-coin的面額。然后再從剩下的面額的最優(yōu)解中，再找一個硬幣，這個硬幣也可能是1.5.10.25美分。此時 ，mincoin= 1+1=2
• 3、循環(huán)上面，一直找到最優(yōu)解為止。
  即：

但是，這個就相當于窮舉了，算法太低效。

重點：
從教材中可知，上面算法，有許多重復的路徑，比如剩余面額為16的時候，就在不同的遞歸路徑中出現(xiàn)了。所以，我們?yōu)榱吮苊膺@種重復的面額還要被遞歸，可以將已經(jīng)出現(xiàn)的面額所需要的最小找零 硬幣個數(shù)存起來。比如將16的最小找零面額3存起來，等下次再遞歸遇到16時，直接判斷出現(xiàn)過16，返回3即可。

這次，算法就比較高效了。里面已經(jīng)有了動態(tài)規(guī)劃的思想：把已經(jīng)知道的最好的路徑存起來，下次遇到可以直接用。

def recDC(coinValueList,change,knownResults):
   minCoins = change
   if change in coinValueList:
      knownResults[change] = 1
      return 1
#遇到了已經(jīng)出現(xiàn)了的面額，而我們又已經(jīng)計算出了需要的最少硬幣數(shù)，可以直接調出來返回該數(shù)就行了。
   elif knownResults[change] > 0:
      return knownResults[change]
   else:
       for i in [c for c in coinValueList if c <= change]:
         numCoins = 1 + recDC(coinValueList, change-i,
                              knownResults)
         if numCoins < minCoins:
            minCoins = numCoins
            knownResults[change] = minCoins
   return minCoins
print(recDC([1,5,10,25],63,[0]*64))

重要思想：構造一個列表，存儲已經(jīng)出現(xiàn)過的面額需要的最小硬幣數(shù)。在遞歸過程中，遇到了已經(jīng)出現(xiàn)了的面額，而我們又已經(jīng)計算出了需要的最少硬幣數(shù)，可以直接調出來返回該數(shù)就行了。

但是，我們采用的還不是動態(tài)規(guī)劃的方法。我們只是“緩存”了面額，改善了程序的性能。

真正的動態(tài)規(guī)劃：
真正的動態(tài)規(guī)劃會采用更系統(tǒng)化的方法來解決問題。
動態(tài)規(guī)劃的解決方法是從為1分錢找零的最優(yōu)解開始，逐步遞加上去，直到我們需要的找零錢數(shù)。這就保證了在算法的每一步過程中，我們已經(jīng)知道了兌換任何更小數(shù)值的零錢時所需的硬幣數(shù)量的最小值。

那么此時，動態(tài)規(guī)劃的函數(shù)需要有三個參數(shù)，
一個是有效硬幣面額列表[1.5.10.25],
一個是包含從1到63美分的change的最優(yōu)解的列表，這個列表就是動態(tài)規(guī)劃的重點。把重要的都存了起來。
一個是需要找零的change，63.

教材里的代碼沒有用遞歸函數(shù)寫?？梢杂胒or循環(huán)來寫。
這段代碼，需要先定義兩個字典

• 一個是minCoins，用來存儲cents對應的最少找零數(shù)。
• 一個是coinUserd，用來存儲cents對應的倒數(shù)第一個找零的硬幣 ，比如63對應21，下次會找到42對應21，21對應21，可以用來輸出cents所有找零面額。

def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
   for cents in range(change+1):#從1分到63美分挨個計算
      coinCount = cents#先初始化找零的硬幣數(shù)，假設都用1美分找零
      newCoin = 1
#把下面的循環(huán)，用例子寫出來就能看懂了。重要的是理解思想。
      for j in [c for c in coinValueList if c <= cents]:
#這一句是精髓，用來確定當前cents找零的最小硬幣數(shù)目
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
               newCoin = j
      minCoins[cents] = coinCount
      coinsUsed[cents] = newCoin
   return minCoins[change]

最后，再加上一個追蹤硬幣的功能，就算利用動態(tài)規(guī)劃完成了找零的任務。

理解BFS以及DFS主要就是程序中的幾個要點。記住了就好。

二、廣度優(yōu)先搜索（BFS）

2.1 、通過詞梯問題，了解BFS。

詞梯問題：。比如，將單詞“ FOOL”轉變成單詞“ SAGE”。在詞梯問題中，你必須以一次只改變一個字母的方式來逐步轉變單詞。每一步你都必須將一個單詞轉變成另一個單詞，并且不允許轉變成一個不存在的單詞。

詞梯問題還有很多的變形。比如你可能被要求以給定的步數(shù)完成單詞轉換，或者你必須使用一個特定的單詞。在本節(jié)內容中，我們感興趣的是如何算出從開始單詞到目標單詞所需要的最小轉換次數(shù)。

為了能用圖解決這個問題，我們通過兩步來達到目標：

• 1、先建立一個圖，描繪出單詞之間的關系。
  可以建立一個圖的類graph。
• 2、圖已經(jīng)建立好，再用廣度優(yōu)先搜索（BFS）的圖算法找到最短路徑。

2.2 圖的表現(xiàn)形式

圖的表現(xiàn)形式主要有兩個，一個是鄰接矩陣，一個是鄰接表。

對于鄰接矩陣和鄰接表的介紹參見教材7.5-7.6節(jié)。

鄰接表：一個實現(xiàn)稀疏圖的更高效的方案是使用鄰接表 adjacency list。在這個實現(xiàn)方法中，我們維護一個包含所有頂點的主列表（master list），主列表中的每個頂點，再關聯(lián)一個與自身有邊連接的所有頂點的列表。在實現(xiàn)頂點類的方法里，我們使用字典而不是列表，此時字典中的鍵（key）對應頂點標識，而值（value）則可以保存頂點連接邊的權重。

實現(xiàn)鄰接表，需要用到兩個類，一個是圖graph，一個是頂點vertex。

2.3 建立word ladder圖

把問題細化再優(yōu)化：

• 1、就像動態(tài)規(guī)劃中，我們把對63美分的零錢找零一樣，我們先把問題細化成一次找一個硬幣（貪心，窮舉）來找到最優(yōu)解，然后再優(yōu)化（優(yōu)化成動態(tài)規(guī)劃）。
• 2、就像打算用圖解決問題一樣，我們細化問題，先建立一個圖，再用圖算法。
• 3、同樣，這里也是。我們把“建立詞梯圖”問題細化成：首先明確建立什么樣的圖，再考慮怎么建立這個圖。

2.3.1 建立什么樣的圖

我們第一個問題是去解決如何將大量單詞組成的集合轉變成圖。我們想要的是在兩個僅差一個字母的單詞之間連一條邊。如果我們可以創(chuàng)建一個這樣的圖表，那么任一從一個單詞到另一個單詞的路徑都是某個詞梯問題的一個解。圖中顯示了一個由一些單詞構成的小圖，可以解決從“ FOOL”轉變成“SAGE”的詞梯問題。值得注意的是，該圖是無向圖，并且邊是沒有權的。

2.3.2 怎么建造這個圖

簡單粗暴的方法：
假設有一個單詞列表，這個列表中所有的單詞長度都是4。

• 我們?yōu)檫@個列表中每個單詞創(chuàng)建一個頂點。
• 為了將這些單詞連接起來，我們可以將列表中的每個詞與所有其他單詞進行比較。
• 若是該單詞，和比較的單詞只有一個字母不同，就可以在圖中創(chuàng)建一條連接他們的邊。

但是這個方法的時間復雜度是O(n²)。假設有5110個單詞，n²比2600萬還大。

優(yōu)化這個方法：
上面的方法， 是每次來一個單詞，都與所有的單詞進行比較。比如來了pope，會和第一個字母不同的單詞（rope，nope，hope），也會和第二個字母不同的單詞（pipe，pape）進行比較，然后再將有聯(lián)系的單詞連接起來。以此類推。這樣會比較冗余。

我們可以把同一個單詞類型，都放到一個桶里。
比如_ope，就是只要第一個字母不同的單詞，都放到這個桶里去，不用再去和別的單詞進行比較了。
對應到上面的，就是，來一個pope，我們放到_ope里去，下一次來了rope，我們也放到_ope去，這樣就避免了讓新來的單詞跟所有的單詞“見面”，只需要找到屬于自己的桶就行了。

這樣結束以后，我們可以認為，在同一個_ope桶里的，都是第一個字母不一樣的，相互連接的單詞。
如下圖：

上述方法，用Python實現(xiàn)的話，就是把桶的表示作為字典key，把桶里的單詞作為value。
構建圖的時候，對一個桶的m個單詞，兩兩之間添加聯(lián)系。

for word1 in d[bucket]:
    for word2 in d[bucket]:
        if word1 != word2:
            g.addEdge(word1,word2)

最后返回圖就行了。

2.3.3 用廣度優(yōu)先搜索法（BFS）解決這個圖問題

直觀理解：在搜索完第k層的節(jié)點之前，是不會搜索第k+1層的節(jié)點的。

想像BFS的運行原理：
BFS過程，就是建造一棵以頂點 s 為根的樹的過程，一次建造樹的一層，同時，BFS在增加k+1層次之前，會保證將所有的k層的子頂點都添加在了樹中。

追蹤這個過程：

• 1、BFS 算法在搜索過程中，會給每一個頂點染色為白色、灰色或黑色。
• 2、每一個頂點在被構建時都被初始化為白色，在這之后，白色代表的是尚未被發(fā)現(xiàn)的頂點。
• 3、當一個頂點被第一次發(fā)現(xiàn)后，它被染成灰色（下次別的點搜索到這個點時，發(fā)現(xiàn)是灰色就說明已經(jīng)被發(fā)現(xiàn)了，就不會再進行搜索了。）
• 4、當廣度優(yōu)先搜索(BFS)完全探索完一個頂點后，它被染成黑色。
  這意味著一旦一個節(jié)點染成了黑色，它就沒有鄰近的白色節(jié)點；而另一方面，如果一個頂點被標識為了灰色，這就意味著其附近可能還存在著未探索的頂點等待被探索。

代碼實現(xiàn)：
廣度優(yōu)先搜索算法使用的是前文出現(xiàn)過的鄰接表來實現(xiàn)的圖。此外，它還使用了一個隊列來決定下一步應該探索哪一個頂點。

隊列的作用：掃描到一個頂點，會把該頂點添加到隊尾。由于隊列的后進后出。只有當把距離為k的頂點都從隊列中彈出完了以后，隊首才會是距離為k+1的頂點，然后接著把距離為k+2的頂點掃到隊尾。

廣度優(yōu)先搜索（BFS） 從起始頂點 s 開始，此時 s 的顏色被設置為灰色，代表它現(xiàn)在已經(jīng)被發(fā)現(xiàn)了，另外兩個參數(shù)——距離和父頂點，對于起始節(jié)點 s 初始設置為了 0 和 None。隨后，起始節(jié)點會被加入到一個隊列中，下一步便是系統(tǒng)地探索隊首頂點。這個過程通過迭代（遍歷）隊首頂點的鄰接列表來完成，每檢查鄰接表中的一個頂點，便會維護這個頂點的顏色參量，如果顏色是白色的，就說明這個節(jié)點尚未被探索，也就會按下述四步操作：

• 1、 把這個新的未探索的節(jié)點 nbr，標記為灰色；

• 2、 nbr 的父頂點被設置為當前節(jié)點 currentVert；
  比如，我是從a點向下搜索到了b點，那么a就為b的父節(jié)點

• 3、 nbr 的距離被設置為當前節(jié)點的距離加一；
  比如從頂點s到a的距離是sa，那么從頂點s到b的距離一定是sa+1.

• 4、 nbr 被加入隊尾，直到在當前頂點的鄰接列表中的所有頂點nbr被搜索完后，才能夠進行下一層次的探索操作。

假設隊列的隊首頂點是a，a到頂點的距離是sa，那么，會在搜索完a的下一層的所有距離為sa+1的頂點。把a的顏色標記為黑色。彈出a。此時a后面的節(jié)點變?yōu)殛犑住?br> 若a2距離頂點的距離一樣等于sa，那么也會搜索完a2的下一層所有距離為sa+1的頂點。
這樣循環(huán)下去。

from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue

def bfs(g,start):
  start.setDistance(0)
  start.setPred(None)
  vertQueue = Queue()
  vertQueue.enqueue(start)
  while (vertQueue.size() > 0):
    #當前點是隊首的點
    currentVert = vertQueue.dequeue()
    for nbr in currentVert.getConnections():#遍歷當前點的所有nbr節(jié)點
      if (nbr.getColor() == 'white'):#如果是白色，就按照上述四步進行操作。
        nbr.setColor('gray')
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        vertQueue.enqueue(nbr)
    #當前節(jié)點的nbr節(jié)點被遍歷完，將當前節(jié)點標記為黑色。
    currentVert.setColor('black')

如果，當 bfs 函數(shù)從節(jié)點a檢查到節(jié)點 b 時，發(fā)現(xiàn)它的顏色已經(jīng)染為了灰色，這代表它已經(jīng)被發(fā)現(xiàn)過了，并且表明從起始節(jié)點到 b之間有一條更短的路徑。

• 1、頂點s到a的距離為sa，s到b的距離為sa+1。又因為BFS只有在搜索當前層節(jié)點以后，才會搜索下一層的節(jié)點。
• 2、說明在搜到a之前，已經(jīng)搜索過b了，而且，之前那條路徑從頂點s到b的距離小于等于sa。
• 3、所以表明，此時從頂點s到b之間有一個更短的路徑，于是可以放棄當前的從s到a再到b的路徑。

于是，由上面分析，可以知道，確實，代碼構建的樹實現(xiàn)了每次從節(jié)點s到b都是最短的路徑。

更加形象的例子參考教材Python算法

總結

所以，BFS也就是開始說的兩步：

• 1、構建圖：用相鄰表構建，用到了字典的知識
• 2、BFS搜索，主要是理解兩點：一、搜索思想，搜索完第k層以后，才會搜索第k+1層。二、追蹤節(jié)點，就是上面的發(fā)現(xiàn)節(jié)點以后的四小步：若是白節(jié)點b，變灰-->當前節(jié)點a設置為節(jié)點b的父節(jié)點-->該節(jié)點距離設置為sa+1-->把b添加到隊尾。

理順了，BFS也就理解了。

另外，BFS還能夠讓我們從樹的任一節(jié)點出發(fā)，沿著父節(jié)點返回到根節(jié)點，從而得到從這個節(jié)點的詞到根節(jié)點的詞的最短詞梯。

廣度優(yōu)先搜索的時間復雜度分析:

盡管是兩個循環(huán)，while跟for，就相當于，兩個for，第一個for的循環(huán)次數(shù)是1。第二個for的循環(huán)次數(shù)是該節(jié)點的相鄰點的個數(shù)。

由于每個節(jié)點僅被發(fā)現(xiàn)一次，因此每個節(jié)點入棧和出棧各一次，時間均為O(1),故所有V個節(jié)點入棧和出?？倳r間為O(V)
由于需要對每個節(jié)點的鄰接表進行掃描，時間為O(Adj[u]),總時間為O(E);

V代表節(jié)點總數(shù)，E代表圖的所有邊的總數(shù)。一次while和for，只是遍歷了一次一個節(jié)點的所有nbr。一個節(jié)點出入棧一次，時間為1，遍歷這個節(jié)點nbr時間為adj[u]（也就是判斷這個節(jié)點具有幾個nbr），所以這次的while和for的時間復雜度是1+adj[u]。
那么V各節(jié)點，找了E次，就是V+E。

注意，這里不能認為while同等于for遍歷V次。
首先因為while循環(huán)的條件是棧不為空，這個棧一共會出棧進棧V個節(jié)點，所以while會循環(huán)V次。
?。?！但是！?。?，每次循環(huán)時，for所查找的每個節(jié)點的相鄰點的個數(shù)是不一樣的?。?！都是不確定的，所以不能單純的就是相乘。
比如第一次while循環(huán)時，for找到了當前點有2個相鄰點，下次的vert，for可能只找到了一個。

綜上所示，廣度優(yōu)先搜索的時間復雜度為O(V+E).即是圖鄰接表大小的線性函數(shù)。

三、深度優(yōu)先搜索（DFS）

我們用于解決騎士周游問題的搜索算法是 Depth First Search (DFS)——深度優(yōu)先搜索算法。前面討論的 BFS（廣度優(yōu)先搜索算法）是一次建立搜索樹的一層，而 DFS 算法則是盡可能深的搜索樹的一枝。

同理于用BFS解決詞梯問題的步驟，對于用DFS解決騎士周游問題也是采用兩步走的方案：

• 1、建立一個圖。
  將棋盤上合法的走棋次序表示為一個圖。
• 2、利用圖搜索算法找到答案。
  利用DFS算法搜索一個長度為（行 x 列 -1）的路徑，此路徑上恰好包含每個頂點一次。

3.1 建立騎士周游圖

問題細化：

• 1、將棋盤的每個格子用圖的頂點表示。見左下
• 2、騎士從點a可以合法移動到點b，則在圖中，a和b就用邊連接起來。

根據(jù)上面兩點，可以構建圖：

• 1、for每行，for每列，得到一個棋盤上的點的行列信息。
• 2、用一個pos_to_nodeid函數(shù)將棋盤上點位置的行列信息轉換成一個線性頂點數(shù)。（如上左圖的表示方法）。
• 3、用gen_legal_Moves函數(shù)來創(chuàng)建當前這個格子上騎士所有合法移動的列表。
• 4、將得到列表中的每個點和當前點用addEdge方法，用邊連接起來。

于是得到一個圖。

3.2 用DFS算法解決問題

3.2.1 DFS算法的思想

DFS算法盡可能深的搜索每個樹枝，一直搜索到最深的那一個為止。
所以DFS很適合用于發(fā)現(xiàn)一條包含63條邊的路徑。
當DFS走到一條死路（再也沒有可能的合法移動的方式）時，它會沿著樹返回直到該節(jié)點有路可走。然后繼續(xù)往深處探索。

3.3.2 DFS的遞歸函數(shù)

在DFS中，我們遞歸調用knightTour函數(shù)，將節(jié)點傳入此函數(shù)，這個函數(shù)能夠返回這個節(jié)點能夠走的最長的path。

knightTour函數(shù)需要四個傳遞參量：

• n ，當前樹的深度；
• path ，這個節(jié)點前所有已訪問的點的列表；
• u ，我們能夠探索的點；
• limit ，搜索總深度限制。

該函數(shù)遞歸使用：當 knightTour 被調用時，首先檢查基礎狀態(tài)：如果 path 包含有 64 個節(jié)點，函數(shù) knightTour返回 True 表示已經(jīng)找到一條可周游的路徑；如果 path 還不夠長，我們繼續(xù)選擇一個新節(jié)點并以此為參數(shù)調用自身。

該函數(shù)結束條件，path包含64個節(jié)點，或者當前節(jié)點不能再走下去。

DFS對節(jié)點的追蹤：
DFS 算法還需要使用“顏色”來追蹤圖中哪些節(jié)點已經(jīng)被訪問過了。未訪問的節(jié)點染為白色，訪問過的染為灰色。

DFS使用棧：
在 BFS 里面我們用 queue（隊列）來跟蹤要訪問的節(jié)點，而在 DFS 里由于我們使用了遞歸，也即默認使用了 Stack（棧）來實現(xiàn)我們的回溯機制。

具體的解釋：
當我們從knightTour函數(shù)返回 False時（ 代碼第11行），我們依然在 while 循環(huán)里面并在 nbrList 中尋找下一個要搜索的節(jié)點。也就是說，對于深度為path_a的節(jié)點a來說，它的相鄰點b（path_a+1的點）有若干個，若其中一個b1調用knightTour后返回了False，說明從a到b1再往后就走不通了。
此時不會跳出while循環(huán)，會繼續(xù)對另一個b2調用這個函數(shù)，如果不返回false，說明從a到b2再往后還有路走，那就一直深挖下去。
如果a的所有相鄰點都最終返回了false，可能此時從頂點s到a到a的相鄰點的路深度分別為path_sab1=20,path_sab2=30,path_sab3=25,都小于63，那么說明經(jīng)過a點也不會找到最長路徑，那么此時以a為參數(shù)的遞歸調用也返回false。

from pythonds.graphs import Graph, Vertex
def knightTour(n,path,u,limit):
        u.setColor('gray')
        path.append(u)
        if n < limit:#當path小于63時，繼續(xù)往深了搜索
            nbrList = list(u.getConnections())
            i = 0
            done = False
            while i < len(nbrList) and not done:#保證將當前節(jié)點的相鄰點都深度搜索完
                if nbrList[i].getColor() == 'white':
                    #當找不到路，或者是path不符合條件時，返回false
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # prepare to backtrack
                #如果按照上述方法探索后，這個路徑不能達到最深，那么說明這個路徑不對
                #因為要遍歷每一個節(jié)點，所以最優(yōu)的路徑還是會用到這個節(jié)點            
                #因此需要將這個節(jié)點但從棧中彈出，并且將這個點的顏色還原為白色，保證還能再用
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done

DFS總結

也是說的兩步走：

• 1、建立圖
• 2、用棧的思想，探索一個節(jié)點a，就標記為灰色然后入棧，繼續(xù)探索下面的節(jié)點b，b的深度為sa+1，b入棧，標記為灰色。若是探索完b返回false，那么就將b彈出，b變回白色。再探索a的另一個相鄰點b1。
• 3、直到探索的點的深度達到要求。

3.3.3 目前DFS的缺點--搜的太傻，不如啟發(fā)式搜索

當前騎士周游算法是一個時間復雜度為O(k^N)的算法，N是棋盤格的數(shù)目，k是一個小的常數(shù)?？梢暬?/p>

假設搜索到的節(jié)點下面有8個合法的位置，然后就要先把下面的每個位置往深了使勁找完以后再才能再回到當前節(jié)點。然后進行新的節(jié)點的搜索。即使這個節(jié)點時錯誤的，算法也會忠實的搜索完。

啟發(fā)式搜索：

直觀地說，就是下一步選擇有最少可能移動位置的頂點。
比如：
不用啟發(fā)式：頂點a下面的點有b1，b2，b3，b4.按理說，就是從a挨個向下探索，a到b1，再到下下層的c1...
用啟發(fā)式：先判斷b1，b2，b3，b4下面有幾個相鄰節(jié)點，把具有相鄰節(jié)點數(shù)目最小的比如b3，排在第一位。下次a就會先從b3搜索。

假設選擇有最多可能移動位置的節(jié)點作為下一個頂點的問題在于騎士將傾向于在周游的早期訪問棋盤中間的方格。當這樣的事情發(fā)生的時候，騎士將容易被困在棋盤的一邊而不能到達棋盤另一邊未被訪問的方格。

另一方面，首先去訪問最少可能的格子會迫使騎士早早的進入邊角的格子。 進而保證騎士早早訪問那些不容易到達的角落，并且在需要的時候通過中間的方格跳躍著穿過棋盤。利用這種先驗的知識來改進算法性能的做法，稱作為“啟發(fā)式規(guī)則”。

人類每天應用啟發(fā)式規(guī)則來做決定，啟發(fā)式搜索經(jīng)常被用在人工智能領域。這個啟發(fā)式規(guī)則算法以 H. C. Warnsdorff 的名字來命名，被叫做 Warnsdorff 算法，他在1823 年發(fā)表了自己的想法。

3.3 通用深度優(yōu)先搜索

上述的DFS只建立了一個深度最深的樹。
在深度優(yōu)先搜索中建立不止一個樹，也是有可能的。（為什么要建立不止一個樹，比如下面的拓撲排序題，想要知道不同的樹，以及不同樹需要的時間，這就是通用DFS的用處了。）

對于通用深度優(yōu)先搜索算法的理解參考教材，其中開頭標題的注釋也講的比較明白了。不過，此算法的應用不是很理解，比如拓撲排序用此算法以后頂點確實能成線性了，但還是不知道怎么制作香餅。。

四、BFS與DFS的不同

4.1、直觀上的不同

4.1.1、BFS==> 搜完一層，才搜下一層

BFS是先搜索完一層的所有點，再搜索下一層。被搜索完第k層的節(jié)點，絕對不會再次被搜索到，因為這些節(jié)點的所有可能已經(jīng)被搜索完了。
想想的話，就是，既然目標是找最短的路徑，那么我就干脆一層一層的找，最短的路徑肯定是層數(shù)最少的，這種方法是可以的。

4.1.2、DFS==> 每搜一個節(jié)點，就是當前節(jié)點的下一層

DFS是每次搜索一層的一個點，然后搜下一層的一個點。即，先從根節(jié)點s使勁往下探索，探索到最深處再回來探索另一條路徑。
想想的話，就是既然目標是找最長的路徑，那最長的路徑肯定是需要一路往下找的。所以每次就一個點一個點的往下搜索。
理論上說，如果我用BFS，每次搜索完一一層，以最長的路徑目標，也是可以的。

4.2、所用的數(shù)據(jù)結構不同

4.2.1、BFS ==> 隊列

BFS所用的是隊列，每次新搜索一個點，就添加到隊尾，按照上面所說，因為是一層搜完才會搜下一層。所以搜索完這個點，就不會再對這個點進行搜索了。所以直接從隊列中刪掉就行。

4.2.2、DFS ==> 棧

DFS用的是棧，按照上面所說，因為是搜了k層的點a，再搜k+1層的點b，再 搜k+2層的點c。搜到c時，當前點標記為b，搜完c若返回false，那么就會回來從b再向下別的方向進行搜索。也就是說，搜索了這個點，還可能回來再搜這個點向下的別的方向。
因為會回溯，所以要用棧，將搜索的點壓入棧中，若返回false就pop出這個點，然后再搜索棧頂?shù)狞c的別的方向。

4.3、對節(jié)點的追蹤方式不同（標注顏色方式不同）

4.3.1、BFS ==> 三種顏色，白，灰，黑

上面也已經(jīng)說過，BFS搜索完一個點，這個點就不會被再次搜索了。

一個節(jié)點未被搜索前，是白色。
已經(jīng)被搜索，標記為灰色。（注意，搜索的目標--是--當前節(jié)點的下一層的節(jié)點）。
這個節(jié)點的下一層節(jié)點搜索完了，那么此時，當前節(jié)點標記為黑色表示不會再被搜索，當前節(jié)點的下一層節(jié)點標記為灰色。

4.3.2、DFS ==> 兩種顏色，白，灰

DFS中，已經(jīng)被搜索的點，還可能會被用到（代碼中的三行解釋）

節(jié)點被搜索前，是白色。
節(jié)點正在被搜索標記為灰色。（注意，搜索的目標--是--當前節(jié)點的不斷往下層前進的節(jié)點）
節(jié)點被搜索完以后，路徑是false ，節(jié)點從灰色再次標記為白色。說明在新的路徑中，此節(jié)點未被搜索到。