一技健、動(dòng)態(tài)規(guī)劃

找到兩點(diǎn)間的最短路徑，找最匹配一組點(diǎn)的線惰拱，等等雌贱，都可能會(huì)用動(dòng)態(tài)規(guī)劃來解決。

參考如何理解動(dòng)態(tài)規(guī)劃中偿短，第二個(gè)回答欣孤。冒泡

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

貪心算法：就是每次選擇最優(yōu)昔逗。
對(duì)應(yīng)到參考的回答中降传，是每次選擇最短的路徑，對(duì)應(yīng)到python數(shù)據(jù)結(jié)構(gòu)教材中勾怒，就是每次先找面額最大的硬幣婆排。

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

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

接下來就教材中的硬幣例子默怨，說明動(dòng)態(tài)規(guī)劃谈为。

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

• 1.一開始书劝，假設(shè)63美分的最優(yōu)解里已經(jīng)找了一個(gè)硬幣损痰。那么這個(gè)硬幣可能是上面四個(gè)面額列粪。mincoin=0+1=1
• 2审磁、既然已經(jīng)找了一個(gè)硬幣，那么還剩63-coin的面額岂座。然后再從剩下的面額的最優(yōu)解中态蒂，再找一個(gè)硬幣，這個(gè)硬幣也可能是1.5.10.25美分费什。此時(shí) 钾恢，mincoin= 1+1=2
• 3、循環(huán)上面鸳址，一直找到最優(yōu)解為止瘩蚪。
  即：

但是，這個(gè)就相當(dāng)于窮舉了氯质，算法太低效募舟。

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

這次鸟悴，算法就比較高效了。里面已經(jīng)有了動(dò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)計(jì)算出了需要的最少硬幣數(shù)陋守，可以直接調(diào)出來返回該數(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))

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

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

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

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

教材里的代碼沒有用遞歸函數(shù)寫已骇±攵郏可以用for循環(huán)來寫票编。
這段代碼，需要先定義兩個(gè)字典

• 一個(gè)是minCoins卵渴，用來存儲(chǔ)cents對(duì)應(yīng)的最少找零數(shù)慧域。
• 一個(gè)是coinUserd，用來存儲(chǔ)cents對(duì)應(yīng)的倒數(shù)第一個(gè)找零的硬幣 浪读，比如63對(duì)應(yīng)21昔榴，下次會(huì)找到42對(duì)應(yīng)21，21對(duì)應(yīng)21碘橘，可以用來輸出cents所有找零面額互订。

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

最后，再加上一個(gè)追蹤硬幣的功能勇边，就算利用動(dòng)態(tài)規(guī)劃完成了找零的任務(wù)犹撒。

理解BFS以及DFS主要就是程序中的幾個(gè)要點(diǎn)。記住了就好粒褒。

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

2.1 、通過詞梯問題奕坟，了解BFS祥款。

詞梯問題：。比如月杉，將單詞“ FOOL”轉(zhuǎn)變成單詞“ SAGE”刃跛。在詞梯問題中，你必須以一次只改變一個(gè)字母的方式來逐步轉(zhuǎn)變單詞苛萎。每一步你都必須將一個(gè)單詞轉(zhuǎn)變成另一個(gè)單詞桨昙，并且不允許轉(zhuǎn)變成一個(gè)不存在的單詞。

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

為了能用圖解決這個(gè)問題，我們通過兩步來達(dá)到目標(biāo)：

• 1馍驯、先建立一個(gè)圖阁危，描繪出單詞之間的關(guān)系炊甲。
  可以建立一個(gè)圖的類graph。
• 2欲芹、圖已經(jīng)建立好卿啡，再用廣度優(yōu)先搜索（BFS）的圖算法找到最短路徑。

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

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

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

鄰接表：一個(gè)實(shí)現(xiàn)稀疏圖的更高效的方案是使用鄰接表 adjacency list官辽。在這個(gè)實(shí)現(xiàn)方法中，我們維護(hù)一個(gè)包含所有頂點(diǎn)的主列表（master list）粟瞬，主列表中的每個(gè)頂點(diǎn)同仆，再關(guān)聯(lián)一個(gè)與自身有邊連接的所有頂點(diǎn)的列表。在實(shí)現(xiàn)頂點(diǎn)類的方法里裙品，我們使用字典而不是列表俗批，此時(shí)字典中的鍵（key）對(duì)應(yīng)頂點(diǎn)標(biāo)識(shí)，而值（value）則可以保存頂點(diǎn)連接邊的權(quán)重市怎。

實(shí)現(xiàn)鄰接表岁忘，需要用到兩個(gè)類，一個(gè)是圖graph区匠，一個(gè)是頂點(diǎn)vertex干像。

2.3 建立word ladder圖

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

• 1、就像動(dòng)態(tài)規(guī)劃中驰弄，我們把對(duì)63美分的零錢找零一樣麻汰，我們先把問題細(xì)化成一次找一個(gè)硬幣（貪心，窮舉）來找到最優(yōu)解戚篙，然后再優(yōu)化（優(yōu)化成動(dòng)態(tài)規(guī)劃）五鲫。
• 2、就像打算用圖解決問題一樣已球，我們細(xì)化問題臣镣，先建立一個(gè)圖，再用圖算法智亮。
• 3忆某、同樣，這里也是阔蛉。我們把“建立詞梯圖”問題細(xì)化成：首先明確建立什么樣的圖弃舒，再考慮怎么建立這個(gè)圖。

2.3.1 建立什么樣的圖

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

2.3.2 怎么建造這個(gè)圖

簡(jiǎn)單粗暴的方法：
假設(shè)有一個(gè)單詞列表，這個(gè)列表中所有的單詞長(zhǎng)度都是4蛹稍。

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

但是這個(gè)方法的時(shí)間復(fù)雜度是O(n²)赵抢。假設(shè)有5110個(gè)單詞，n²比2600萬還大仗阅。

優(yōu)化這個(gè)方法：
上面的方法昌讲， 是每次來一個(gè)單詞，都與所有的單詞進(jìn)行比較减噪。比如來了pope，會(huì)和第一個(gè)字母不同的單詞（rope车吹，nope筹裕，hope），也會(huì)和第二個(gè)字母不同的單詞（pipe窄驹，pape）進(jìn)行比較朝卒，然后再將有聯(lián)系的單詞連接起來。以此類推乐埠。這樣會(huì)比較冗余抗斤。

我們可以把同一個(gè)單詞類型，都放到一個(gè)桶里丈咐。
比如_ope瑞眼，就是只要第一個(gè)字母不同的單詞，都放到這個(gè)桶里去棵逊，不用再去和別的單詞進(jìn)行比較了伤疙。
對(duì)應(yīng)到上面的，就是，來一個(gè)pope徒像，我們放到_ope里去黍特，下一次來了rope，我們也放到_ope去锯蛀，這樣就避免了讓新來的單詞跟所有的單詞“見面”灭衷，只需要找到屬于自己的桶就行了。

這樣結(jié)束以后旁涤，我們可以認(rèn)為今布，在同一個(gè)_ope桶里的，都是第一個(gè)字母不一樣的拭抬，相互連接的單詞部默。
如下圖：

上述方法，用Python實(shí)現(xiàn)的話造虎，就是把桶的表示作為字典key傅蹂，把桶里的單詞作為value。
構(gòu)建圖的時(shí)候算凿，對(duì)一個(gè)桶的m個(gè)單詞份蝴，兩兩之間添加聯(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）解決這個(gè)圖問題

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

想像BFS的運(yùn)行原理：
BFS過程署鸡，就是建造一棵以頂點(diǎn) s 為根的樹的過程案糙，一次建造樹的一層，同時(shí)靴庆，BFS在增加k+1層次之前时捌，會(huì)保證將所有的k層的子頂點(diǎn)都添加在了樹中。

追蹤這個(gè)過程：

• 1炉抒、BFS 算法在搜索過程中奢讨，會(huì)給每一個(gè)頂點(diǎn)染色為白色、灰色或黑色焰薄。
• 2拿诸、每一個(gè)頂點(diǎn)在被構(gòu)建時(shí)都被初始化為白色，在這之后塞茅，白色代表的是尚未被發(fā)現(xiàn)的頂點(diǎn)亩码。
• 3、當(dāng)一個(gè)頂點(diǎn)被第一次發(fā)現(xiàn)后凡桥，它被染成灰色（下次別的點(diǎn)搜索到這個(gè)點(diǎn)時(shí)蟀伸，發(fā)現(xiàn)是灰色就說明已經(jīng)被發(fā)現(xiàn)了，就不會(huì)再進(jìn)行搜索了。）
• 4啊掏、當(dāng)廣度優(yōu)先搜索(BFS)完全探索完一個(gè)頂點(diǎn)后蠢络，它被染成黑色。
  這意味著一旦一個(gè)節(jié)點(diǎn)染成了黑色迟蜜，它就沒有鄰近的白色節(jié)點(diǎn)刹孔；而另一方面，如果一個(gè)頂點(diǎn)被標(biāo)識(shí)為了灰色娜睛，這就意味著其附近可能還存在著未探索的頂點(diǎn)等待被探索髓霞。

代碼實(shí)現(xiàn)：
廣度優(yōu)先搜索算法使用的是前文出現(xiàn)過的鄰接表來實(shí)現(xiàn)的圖。此外畦戒，它還使用了一個(gè)隊(duì)列來決定下一步應(yīng)該探索哪一個(gè)頂點(diǎn)方库。

隊(duì)列的作用：掃描到一個(gè)頂點(diǎn)，會(huì)把該頂點(diǎn)添加到隊(duì)尾障斋。由于隊(duì)列的后進(jìn)后出纵潦。只有當(dāng)把距離為k的頂點(diǎn)都從隊(duì)列中彈出完了以后，隊(duì)首才會(huì)是距離為k+1的頂點(diǎn)垃环，然后接著把距離為k+2的頂點(diǎn)掃到隊(duì)尾邀层。

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

• 1苗沧、 把這個(gè)新的未探索的節(jié)點(diǎn) nbr，標(biāo)記為灰色炭晒；

• 2待逞、 nbr 的父頂點(diǎn)被設(shè)置為當(dāng)前節(jié)點(diǎn) currentVert；
  比如网严，我是從a點(diǎn)向下搜索到了b點(diǎn)识樱，那么a就為b的父節(jié)點(diǎn)

• 3、 nbr 的距離被設(shè)置為當(dāng)前節(jié)點(diǎn)的距離加一；
  比如從頂點(diǎn)s到a的距離是sa怜庸，那么從頂點(diǎn)s到b的距離一定是sa+1.

• 4当犯、 nbr 被加入隊(duì)尾，直到在當(dāng)前頂點(diǎn)的鄰接列表中的所有頂點(diǎn)nbr被搜索完后割疾，才能夠進(jìn)行下一層次的探索操作嚎卫。

假設(shè)隊(duì)列的隊(duì)首頂點(diǎn)是a，a到頂點(diǎn)的距離是sa宏榕，那么拓诸，會(huì)在搜索完a的下一層的所有距離為sa+1的頂點(diǎn)。把a(bǔ)的顏色標(biāo)記為黑色麻昼。彈出a奠支。此時(shí)a后面的節(jié)點(diǎn)變?yōu)殛?duì)首。
若a2距離頂點(diǎn)的距離一樣等于sa抚芦，那么也會(huì)搜索完a2的下一層所有距離為sa+1的頂點(diǎn)倍谜。
這樣循環(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):
    #當(dāng)前點(diǎn)是隊(duì)首的點(diǎn)
    currentVert = vertQueue.dequeue()
    for nbr in currentVert.getConnections():#遍歷當(dāng)前點(diǎn)的所有nbr節(jié)點(diǎn)
      if (nbr.getColor() == 'white'):#如果是白色燕垃，就按照上述四步進(jìn)行操作枢劝。
        nbr.setColor('gray')
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        vertQueue.enqueue(nbr)
    #當(dāng)前節(jié)點(diǎn)的nbr節(jié)點(diǎn)被遍歷完，將當(dāng)前節(jié)點(diǎn)標(biāo)記為黑色卜壕。
    currentVert.setColor('black')

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

• 1侦副、頂點(diǎn)s到a的距離為sa侦锯，s到b的距離為sa+1。又因?yàn)锽FS只有在搜索當(dāng)前層節(jié)點(diǎn)以后秦驯，才會(huì)搜索下一層的節(jié)點(diǎn)尺碰。
• 2、說明在搜到a之前译隘，已經(jīng)搜索過b了亲桥，而且，之前那條路徑從頂點(diǎn)s到b的距離小于等于sa固耘。
• 3题篷、所以表明，此時(shí)從頂點(diǎn)s到b之間有一個(gè)更短的路徑厅目，于是可以放棄當(dāng)前的從s到a再到b的路徑番枚。

于是法严，由上面分析，可以知道葫笼，確實(shí)深啤，代碼構(gòu)建的樹實(shí)現(xiàn)了每次從節(jié)點(diǎn)s到b都是最短的路徑。

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

總結(jié)

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

• 1墓塌、構(gòu)建圖：用相鄰表構(gòu)建，用到了字典的知識(shí)
• 2奥额、BFS搜索苫幢，主要是理解兩點(diǎn)：一、搜索思想垫挨，搜索完第k層以后韩肝，才會(huì)搜索第k+1層。二九榔、追蹤節(jié)點(diǎn)哀峻，就是上面的發(fā)現(xiàn)節(jié)點(diǎn)以后的四小步：若是白節(jié)點(diǎn)b，變灰-->當(dāng)前節(jié)點(diǎn)a設(shè)置為節(jié)點(diǎn)b的父節(jié)點(diǎn)-->該節(jié)點(diǎn)距離設(shè)置為sa+1-->把b添加到隊(duì)尾哲泊。

理順了剩蟀，BFS也就理解了。

另外切威，BFS還能夠讓我們從樹的任一節(jié)點(diǎn)出發(fā)育特，沿著父節(jié)點(diǎn)返回到根節(jié)點(diǎn)，從而得到從這個(gè)節(jié)點(diǎn)的詞到根節(jié)點(diǎn)的詞的最短詞梯先朦。

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

盡管是兩個(gè)循環(huán)缰冤，while跟for，就相當(dāng)于喳魏，兩個(gè)for棉浸，第一個(gè)for的循環(huán)次數(shù)是1。第二個(gè)for的循環(huán)次數(shù)是該節(jié)點(diǎn)的相鄰點(diǎn)的個(gè)數(shù)刺彩。

由于每個(gè)節(jié)點(diǎn)僅被發(fā)現(xiàn)一次迷郑，因此每個(gè)節(jié)點(diǎn)入棧和出棧各一次，時(shí)間均為O(1),故所有V個(gè)節(jié)點(diǎn)入棧和出棿淳螅總時(shí)間為O(V)
由于需要對(duì)每個(gè)節(jié)點(diǎn)的鄰接表進(jìn)行掃描三热，時(shí)間為O(Adj[u]),總時(shí)間為O(E);

V代表節(jié)點(diǎn)總數(shù)，E代表圖的所有邊的總數(shù)三幻。一次while和for，只是遍歷了一次一個(gè)節(jié)點(diǎn)的所有nbr呐能。一個(gè)節(jié)點(diǎn)出入棧一次念搬，時(shí)間為1抑堡，遍歷這個(gè)節(jié)點(diǎn)nbr時(shí)間為adj[u]（也就是判斷這個(gè)節(jié)點(diǎn)具有幾個(gè)nbr），所以這次的while和for的時(shí)間復(fù)雜度是1+adj[u]朗徊。
那么V各節(jié)點(diǎn)首妖，找了E次，就是V+E爷恳。

注意有缆，這里不能認(rèn)為while同等于for遍歷V次。
首先因?yàn)閣hile循環(huán)的條件是棧不為空温亲，這個(gè)棧一共會(huì)出棧進(jìn)棧V個(gè)節(jié)點(diǎn)棚壁，所以while會(huì)循環(huán)V次。
Ｕ恍椤Ｐ渫狻！但是；晡瘛Ｂ椤！粘姜，每次循環(huán)時(shí)鬓照，for所查找的每個(gè)節(jié)點(diǎn)的相鄰點(diǎn)的個(gè)數(shù)是不一樣的！９陆簟豺裆！都是不確定的，所以不能單純的就是相乘坛芽。
比如第一次while循環(huán)時(shí)留储，for找到了當(dāng)前點(diǎn)有2個(gè)相鄰點(diǎn)，下次的vert咙轩，for可能只找到了一個(gè)获讳。

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

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

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

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

• 1煞烫、建立一個(gè)圖浑此。
  將棋盤上合法的走棋次序表示為一個(gè)圖。
• 2滞详、利用圖搜索算法找到答案凛俱。
  利用DFS算法搜索一個(gè)長(zhǎng)度為（行 x 列 -1）的路徑紊馏，此路徑上恰好包含每個(gè)頂點(diǎn)一次。

3.1 建立騎士周游圖

問題細(xì)化：

• 1蒲犬、將棋盤的每個(gè)格子用圖的頂點(diǎn)表示朱监。見左下
• 2、騎士從點(diǎn)a可以合法移動(dòng)到點(diǎn)b原叮，則在圖中赫编，a和b就用邊連接起來。

根據(jù)上面兩點(diǎn)奋隶，可以構(gòu)建圖：

• 1擂送、for每行，for每列达布，得到一個(gè)棋盤上的點(diǎn)的行列信息团甲。
• 2、用一個(gè)pos_to_nodeid函數(shù)將棋盤上點(diǎn)位置的行列信息轉(zhuǎn)換成一個(gè)線性頂點(diǎn)數(shù)黍聂。（如上左圖的表示方法）躺苦。
• 3、用gen_legal_Moves函數(shù)來創(chuàng)建當(dāng)前這個(gè)格子上騎士所有合法移動(dòng)的列表产还。
• 4匹厘、將得到列表中的每個(gè)點(diǎn)和當(dāng)前點(diǎn)用addEdge方法，用邊連接起來脐区。

于是得到一個(gè)圖愈诚。

3.2 用DFS算法解決問題

3.2.1 DFS算法的思想

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

3.3.2 DFS的遞歸函數(shù)

在DFS中，我們遞歸調(diào)用knightTour函數(shù)默伍，將節(jié)點(diǎn)傳入此函數(shù)欢嘿，這個(gè)函數(shù)能夠返回這個(gè)節(jié)點(diǎn)能夠走的最長(zhǎng)的path。

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

• n 也糊，當(dāng)前樹的深度炼蹦；
• path ，這個(gè)節(jié)點(diǎn)前所有已訪問的點(diǎn)的列表狸剃；
• u 掐隐，我們能夠探索的點(diǎn)；
• limit 钞馁，搜索總深度限制瑟枫。

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

該函數(shù)結(jié)束條件膝擂，path包含64個(gè)節(jié)點(diǎn)，或者當(dāng)前節(jié)點(diǎn)不能再走下去隙弛。

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

DFS使用棧：
在 BFS 里面我們用 queue（隊(duì)列）來跟蹤要訪問的節(jié)點(diǎn)叉寂，而在 DFS 里由于我們使用了遞歸，也即默認(rèn)使用了 Stack（棧）來實(shí)現(xiàn)我們的回溯機(jī)制总珠。

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

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

DFS總結(jié)

也是說的兩步走：

• 1榨崩、建立圖
• 2谴垫、用棧的思想，探索一個(gè)節(jié)點(diǎn)a母蛛，就標(biāo)記為灰色然后入棧翩剪，繼續(xù)探索下面的節(jié)點(diǎn)b，b的深度為sa+1彩郊，b入棧前弯，標(biāo)記為灰色。若是探索完b返回false秫逝，那么就將b彈出恕出，b變回白色。再探索a的另一個(gè)相鄰點(diǎn)b1违帆。
• 3浙巫、直到探索的點(diǎn)的深度達(dá)到要求。

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

當(dāng)前騎士周游算法是一個(gè)時(shí)間復(fù)雜度為O(k^N)的算法的畴，N是棋盤格的數(shù)目，k是一個(gè)小的常數(shù)惠险∶绺担可視化：

假設(shè)搜索到的節(jié)點(diǎn)下面有8個(gè)合法的位置，然后就要先把下面的每個(gè)位置往深了使勁找完以后再才能再回到當(dāng)前節(jié)點(diǎn)班巩。然后進(jìn)行新的節(jié)點(diǎn)的搜索渣慕。即使這個(gè)節(jié)點(diǎn)時(shí)錯(cuò)誤的，算法也會(huì)忠實(shí)的搜索完抱慌。

啟發(fā)式搜索：

直觀地說逊桦，就是下一步選擇有最少可能移動(dòng)位置的頂點(diǎn)。
比如：
不用啟發(fā)式：頂點(diǎn)a下面的點(diǎn)有b1抑进，b2强经，b3，b4.按理說寺渗，就是從a挨個(gè)向下探索匿情，a到b1，再到下下層的c1...
用啟發(fā)式：先判斷b1信殊，b2炬称，b3，b4下面有幾個(gè)相鄰節(jié)點(diǎn)涡拘，把具有相鄰節(jié)點(diǎn)數(shù)目最小的比如b3玲躯，排在第一位。下次a就會(huì)先從b3搜索。

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

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

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

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

上述的DFS只建立了一個(gè)深度最深的樹成畦。
在深度優(yōu)先搜索中建立不止一個(gè)樹距芬，也是有可能的。（為什么要建立不止一個(gè)樹循帐，比如下面的拓?fù)渑判蝾}框仔，想要知道不同的樹，以及不同樹需要的時(shí)間拄养，這就是通用DFS的用處了离斩。）

對(duì)于通用深度優(yōu)先搜索算法的理解參考教材，其中開頭標(biāo)題的注釋也講的比較明白了瘪匿。不過跛梗，此算法的應(yīng)用不是很理解，比如拓?fù)渑判蛴么怂惴ㄒ院箜旤c(diǎn)確實(shí)能成線性了棋弥，但還是不知道怎么制作香餅核偿。。

四顽染、BFS與DFS的不同

4.1漾岳、直觀上的不同

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

BFS是先搜索完一層的所有點(diǎn)尼荆，再搜索下一層。被搜索完第k層的節(jié)點(diǎn)仁锯，絕對(duì)不會(huì)再次被搜索到耀找，因?yàn)檫@些節(jié)點(diǎn)的所有可能已經(jīng)被搜索完了。
想想的話攀圈，就是阻课，既然目標(biāo)是找最短的路徑，那么我就干脆一層一層的找贾节，最短的路徑肯定是層數(shù)最少的狞悲，這種方法是可以的撮抓。

4.1.2、DFS==> 每搜一個(gè)節(jié)點(diǎn)摇锋，就是當(dāng)前節(jié)點(diǎn)的下一層

DFS是每次搜索一層的一個(gè)點(diǎn)丹拯，然后搜下一層的一個(gè)點(diǎn)。即荸恕，先從根節(jié)點(diǎn)s使勁往下探索乖酬，探索到最深處再回來探索另一條路徑。
想想的話融求，就是既然目標(biāo)是找最長(zhǎng)的路徑咬像，那最長(zhǎng)的路徑肯定是需要一路往下找的。所以每次就一個(gè)點(diǎn)一個(gè)點(diǎn)的往下搜索生宛。
理論上說县昂，如果我用BFS，每次搜索完一一層陷舅，以最長(zhǎng)的路徑目標(biāo)倒彰，也是可以的。

4.2莱睁、所用的數(shù)據(jù)結(jié)構(gòu)不同

4.2.1待讳、BFS ==> 隊(duì)列

BFS所用的是隊(duì)列，每次新搜索一個(gè)點(diǎn)缩赛，就添加到隊(duì)尾耙箍，按照上面所說，因?yàn)槭且粚铀淹瓴艜?huì)搜下一層酥馍。所以搜索完這個(gè)點(diǎn)辩昆，就不會(huì)再對(duì)這個(gè)點(diǎn)進(jìn)行搜索了。所以直接從隊(duì)列中刪掉就行旨袒。

4.2.2汁针、DFS ==> 棧

DFS用的是棧，按照上面所說砚尽，因?yàn)槭撬蚜薻層的點(diǎn)a施无，再搜k+1層的點(diǎn)b，再 搜k+2層的點(diǎn)c必孤。搜到c時(shí)猾骡，當(dāng)前點(diǎn)標(biāo)記為b瑞躺，搜完c若返回false，那么就會(huì)回來從b再向下別的方向進(jìn)行搜索兴想。也就是說幢哨，搜索了這個(gè)點(diǎn)，還可能回來再搜這個(gè)點(diǎn)向下的別的方向嫂便。
因?yàn)闀?huì)回溯捞镰，所以要用棧，將搜索的點(diǎn)壓入棧中毙替，若返回false就pop出這個(gè)點(diǎn)岸售，然后再搜索棧頂?shù)狞c(diǎn)的別的方向。

4.3厂画、對(duì)節(jié)點(diǎn)的追蹤方式不同（標(biāo)注顏色方式不同）

4.3.1凸丸、BFS ==> 三種顏色，白袱院，灰甲雅，黑

上面也已經(jīng)說過，BFS搜索完一個(gè)點(diǎn)坑填，這個(gè)點(diǎn)就不會(huì)被再次搜索了。

一個(gè)節(jié)點(diǎn)未被搜索前弛姜，是白色脐瑰。
已經(jīng)被搜索，標(biāo)記為灰色廷臼。（注意苍在，搜索的目標(biāo)--是--當(dāng)前節(jié)點(diǎn)的下一層的節(jié)點(diǎn)）。
這個(gè)節(jié)點(diǎn)的下一層節(jié)點(diǎn)搜索完了荠商，那么此時(shí)寂恬，當(dāng)前節(jié)點(diǎn)標(biāo)記為黑色表示不會(huì)再被搜索，當(dāng)前節(jié)點(diǎn)的下一層節(jié)點(diǎn)標(biāo)記為灰色莱没。

4.3.2初肉、DFS ==> 兩種顏色，白饰躲，灰

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

節(jié)點(diǎn)被搜索前嘹裂，是白色妄壶。
節(jié)點(diǎn)正在被搜索標(biāo)記為灰色。（注意寄狼，搜索的目標(biāo)--是--當(dāng)前節(jié)點(diǎn)的不斷往下層前進(jìn)的節(jié)點(diǎn)）
節(jié)點(diǎn)被搜索完以后丁寄，路徑是false ，節(jié)點(diǎn)從灰色再次標(biāo)記為白色。說明在新的路徑中伊磺，此節(jié)點(diǎn)未被搜索到盛正。