摘要：不撞南墻不回頭深度優(yōu)先搜索基礎(chǔ)部分對(duì)于深度優(yōu)先搜索和廣度優(yōu)先搜索，我很難形象的去表達(dá)它的定義。這就是深度優(yōu)先搜索了，當(dāng)然，這個(gè)題目我們還有別的解法，這就到了我們說(shuō)的廣度優(yōu)先搜索。

基礎(chǔ)部分

對(duì)于深度優(yōu)先搜索和廣度優(yōu)先搜索，我很難形象的去表達(dá)它的定義。我們從一個(gè)例子來(lái)切入。

輸入一個(gè)數(shù)字n，輸出1~n的全排列。即n=3時(shí)，輸出123，132，213，231，312，321

把問(wèn)題形象化，假如有1，2，3三張撲克牌和編號(hào)為1，2，3的三個(gè)箱子，把三張撲克牌分別放到三個(gè)箱子里有幾種方法？

我們用深度優(yōu)先遍歷搜索的思想來(lái)考慮這個(gè)問(wèn)題。

到1號(hào)箱子面前時(shí)，我們手里有1，2，3三種牌，我們把1放進(jìn)去，然后走到2號(hào)箱子面簽，手里有2，3兩張牌， 然后我們把2放進(jìn)去，再走到3號(hào)箱子前，手里之后3這張牌，所以把3放進(jìn)去，然后再往前走到我們想象出來(lái)的一個(gè)4號(hào)箱子前，我們手里沒牌了，所以，前面三個(gè)箱子中放牌的組合就是要輸出的一種組合方式。（123）

然后我們后退到3號(hào)箱子，把3這張拍取出來(lái)，因?yàn)檫@時(shí)我們手里只有一張牌，所以再往里放的話還是原來(lái)那種情況，所以我們還要再往后推，推到2號(hào)箱子前，把2從箱子中取出來(lái)，這時(shí)候我們手里有2，3兩張牌，這時(shí)我們可以把3放進(jìn)2號(hào)箱子，然后走到3號(hào)箱子中把2放進(jìn)去，這又是一種要輸出的組合方式.（132）

就找這個(gè)思路繼續(xù)下去再次回退的時(shí)候，我們就要退到1號(hào)箱，取出1，然后分別放2和3進(jìn)去，然后產(chǎn)生其余的組合方式。

有點(diǎn)啰嗦，但是基本是這么一個(gè)思路。

我們來(lái)看一下實(shí)現(xiàn)的代碼

    def sortNumber(self, n):
        flag = [False for i in range(n)]
        a = [0 for i in range(n)]
        l = []
        
        def dfs(step):
            if step == n:
                l.append(a[:])
                return
            for i in range(n):
                if flag[i] is False:
                    flag[i] = True
                    a[step] = i
                    dfs(step + 1)
                    flag[i] = False
        dfs(0)
        return l

輸出是

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

我們創(chuàng)建的a這個(gè)list相當(dāng)于上面說(shuō)到的箱子，flag這個(gè)list呢，來(lái)標(biāo)識(shí)某一個(gè)數(shù)字是否已經(jīng)被用過(guò)了。

其實(shí)主要的思想就這dfs方法里面的這個(gè)for循環(huán)中，在依次的排序中，我們默認(rèn)優(yōu)先使用最小的那個(gè)數(shù)字，這個(gè)for循環(huán)其實(shí)就代表了一個(gè)位置上有機(jī)會(huì)放所有的這些數(shù)字，這個(gè)flag標(biāo)識(shí)就避免了在一個(gè)位置重復(fù)使用數(shù)字的問(wèn)題。

如果if 成立，說(shuō)明當(dāng)前位置可以使用這個(gè)數(shù)字，所以把這個(gè)數(shù)字放到a這個(gè)數(shù)組中，然后flag相同為的標(biāo)識(shí)改為True，也就是說(shuō)明這個(gè)數(shù)已經(jīng)被占用了，然后在調(diào)用方法本身，進(jìn)行下一步。

flag[i] = False這句代碼是很重要的，在上面的dfs（也就是下一步）結(jié)束之后，返回到當(dāng)前這個(gè)階段，我們必須模擬收回這個(gè)數(shù)字，也就是把flag置位False，表示這個(gè)數(shù)字又可以用了。

思路大概就是這樣子的，這就是深度優(yōu)先搜索的一個(gè)簡(jiǎn)單的場(chǎng)景。用debug跟一下，一步一步的來(lái)看代碼就更清晰的了。

迷宮問(wèn)題

上面我們已經(jīng)簡(jiǎn)單的了解了深度優(yōu)先搜索，下面我們通過(guò)一個(gè)迷宮的問(wèn)題來(lái)進(jìn)一步數(shù)字這個(gè)算法，然后同時(shí)引出我們的廣度優(yōu)先搜索。

迷宮是由m行n列的單元格組成，每個(gè)單元格要不是空地，要不就是障礙物，我們的任務(wù)是找到一條從起點(diǎn)到終點(diǎn)的最短路徑。

我們抽象成模型來(lái)看一下

start代表起點(diǎn)，end代表終點(diǎn)，x代表障礙物也就是不能通過(guò)的點(diǎn)。

首先我們來(lái)分析一下，從start（0，0）這個(gè)點(diǎn)，甚至說(shuō)是每一個(gè)點(diǎn)出發(fā)，都有四個(gè)方向可以走，上下左右，僅對(duì)于（0，0）這個(gè)點(diǎn)來(lái)說(shuō)，只能往右和下走，因?yàn)橥蠛蜕暇偷搅藛卧裢饷媪?，我們可以稱之為越界了。

我們用深度優(yōu)先的思想來(lái)考慮的話，我們可以從出發(fā)點(diǎn)開始，全部都先往一個(gè)方向走，然后走到遇到障礙物或者到了邊界的情況下，在改變另一個(gè)方向，然后再走到底，這樣一直走下去。

拿到我們這個(gè)題目中，我們可以這樣來(lái)思考，在走的時(shí)候，我們規(guī)定一個(gè)右下左上這樣的順序，也就是先往右走，走到不能往右走的時(shí)候在變換方向。比如我們從(0,0)走到（0，1）這個(gè)點(diǎn)，在（0，1）這個(gè)點(diǎn)也是先往右走，但是我們發(fā)現(xiàn)（0，2）是障礙物，所以我們就改變?yōu)橥伦撸叩剑?，1），然后在（1，1）開始也是先向右走，這樣一直走下去，直到找到我們的目標(biāo)點(diǎn)。

其中我們要注意一點(diǎn)，在右下左上這四個(gè)方向中有一個(gè)方向是我們來(lái)時(shí)候的方向，在當(dāng)前這個(gè)點(diǎn)，四個(gè)方向沒有走完之前我們不要后退到上一個(gè)點(diǎn)，所以我們也需要一個(gè)像前面排數(shù)字代碼里面的flag數(shù)組來(lái)記錄當(dāng)前位置時(shí)候被占用。我們必須是四個(gè)方向都走完了才能往后退到上一個(gè)換方向。

下面我貼一下代碼

    def depthFirstSearch(self):
        m = 5
        n = 4

        # 5行 4 列
        flag = [[False for i in range(n)] for j in range(m)]
        # 存儲(chǔ)不能同行的位置
        a = [[False for i in range(n)] for j in range(m)]
        a[0][2] = True
        a[2][2] = True
        a[3][1] = True
        a[4][3] = True

        global min_step
        min_step = 99999

        director_l = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        def dfs(x, y, step):

            # 什么情況下停止 (找到目標(biāo)坐標(biāo))
            if x == 3 and y == 2:
                global min_step
                if step < min_step:
                    min_step = step
                return

            # 右下左上
            for i in range(4):
                # 下一個(gè)點(diǎn)
                nextX = x + director_l[i][0]
                nextY = y + director_l[i][1]

                # 是否越界
                if nextX < 0 or nextX >= m or nextY < 0 or nextY >= n:
                    continue

                # 不是障礙  and 改點(diǎn)還沒有走過(guò)
                if a[x][y] is False and flag[x][y] is False:
                    flag[x][y] = True
                    dfs(nextX, nextY, step+1)
                    flag[x][y] = False #回收

        dfs(0, 0, 0)
        return min_step

首先f(wàn)lag這個(gè)算是二位數(shù)組吧，來(lái)記錄我們位置是否占用了，然后a這個(gè)數(shù)組，是來(lái)記錄整個(gè)單元格的，也就是標(biāo)識(shí)那些障礙物的位置坐標(biāo)。同樣的，重點(diǎn)是這個(gè)dfs方法，他的參數(shù)x,y是指當(dāng)前的坐標(biāo)，step是步數(shù)。

這個(gè)大家可以看到一個(gè)director_l的數(shù)組，他是來(lái)輔助我們根據(jù)當(dāng)前左邊和不同方向計(jì)算下一個(gè)位置的坐標(biāo)的。

dfs中我們已經(jīng)注明了搜索停止的判斷方式，也就是找到（3，2）這個(gè)點(diǎn)，然后下面的for循環(huán)，則代表四個(gè)不同的方向，每一個(gè)方向我們都會(huì)先求出他的位置，然后判斷是否越界，如果沒有越界在判斷是否是障礙或者是否已經(jīng)走過(guò)了，滿足了所有的判斷條件，我們?cè)诶^續(xù)往下一個(gè)點(diǎn)，直到找到目標(biāo)，比較路徑的步數(shù)。

這就是深度優(yōu)先搜索了，當(dāng)然，這個(gè)題目我們還有別的解法，這就到了我們說(shuō)的廣度優(yōu)先搜索。

我們先大體說(shuō)一下廣度優(yōu)先搜索的思路，深度優(yōu)先是先窮盡一個(gè)方向，而廣度優(yōu)先呢，則是基于一個(gè)位置，先拿到他所有能到達(dá)的位置，然后分別基于這些新位置，拿到他們能到達(dá)的所有位置，一次這樣層層的遞進(jìn)，直到找到我們的終點(diǎn)。

從（0，0）出發(fā)，可以到達(dá)（0，1）和（1,0），然后再?gòu)模?，1)出發(fā)到達(dá)（1，1），從（1，0）出發(fā)，到達(dá)（2，0）和（1，1），以此類推。

所以我們我們維護(hù)一個(gè)隊(duì)列來(lái)儲(chǔ)存每一層遍歷到達(dá)的點(diǎn)，當(dāng)然了，不要重復(fù)儲(chǔ)存同一個(gè)點(diǎn)。我們用一個(gè)指針head來(lái)標(biāo)識(shí)當(dāng)前的基準(zhǔn)位置，也就是說(shuō)最開始指向（0，0），當(dāng)儲(chǔ)存完畢所有（0，0）能抵達(dá)的位置時(shí)，我們就應(yīng)該改變我們的基準(zhǔn)位置了，這時(shí)候head++，就到了（0，1）這個(gè)位置，然后儲(chǔ)存完他能到的所有位置，head++，就到了（1，0），然后繼續(xù)。

    def breadthFirstSearch(self):

        class Node:
            def __init__(self):
                x = 0
                y = 0
                step = 0

        m, n = 5, 4
        # 記錄
        flag = [[False for i in range(n)] for j in range(m)]

        # 儲(chǔ)存地圖信息
        a = [[False for i in range(n)] for j in range(m)]
        a[0][2] = True
        a[2][2] = True
        a[3][1] = True
        a[4][3] = True
        # 隊(duì)列
        l = []
        startX, startY, step = 0, 0, 0
        head = 0
        index = 0

        node = Node()
        node.x = startX
        node.y = startY
        node.step = step
        index += 1
        l.append(node)
        flag[0][0] = True

        director_l = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        while head < index:

            last_node = l[head]
            # 處理四個(gè)方向
            for i in range(4):

                # 當(dāng)前位置
                currentX = last_node.x + director_l[i][0]
                currentY = last_node.y + director_l[i][1]

                # 找到目標(biāo)
                if currentX == 4 and currentY == 2:
                    print("step = " + str(last_node.step + 1))
                    return

                #是否越界
                if currentX < 0 or currentY < 0 or currentX >= m or currentY >= n:
                    continue

                if a[currentX][currentY] is False and flag[currentX][currentY] is False:


                    #不是目標(biāo)
                    flag[currentX][currentY] = True

                    node_new = Node()
                    node_new.x = currentX
                    node_new.y = currentY
                    node_new.step = last_node.step+1
                    l.append(node_new)
                    index += 1



            head += 1

首先我們定義了一個(gè)節(jié)點(diǎn)Node的類，來(lái)封裝節(jié)點(diǎn)位置和當(dāng)前的步數(shù)，flag，a，director_l這兩個(gè)數(shù)組作用跟深度優(yōu)先搜索相同，l是我們維護(hù)的隊(duì)列，head指針指向當(dāng)前基準(zhǔn)的那個(gè)位置的，index指針指向隊(duì)列尾。首先我們先把第一個(gè)Node（也就是起點(diǎn)）存進(jìn)隊(duì)列，廣度優(yōu)先搜索不需要遞歸，只要加一個(gè)循環(huán)就行。

每次走到符合要求的位置，我們便把他封裝成Node來(lái)存進(jìn)對(duì)列中，每存一個(gè)index都要+1.

head指針必須在一個(gè)節(jié)點(diǎn)四個(gè)方向都處理完了之后才可以+1，變換下一個(gè)基準(zhǔn)節(jié)點(diǎn)。

簡(jiǎn)單的介紹了深度優(yōu)先搜索和廣度優(yōu)先搜索，深度優(yōu)先有一種先窮盡一個(gè)方向然后結(jié)合使用回溯來(lái)找到解，廣度呢，可能就是每做一次操作就涵蓋了所有的可能結(jié)果，然后一步步往后推出去，找到最后的解。這算我個(gè)人的理解吧，不準(zhǔn)確也不官方，思想也只能算是稍有體會(huì)，還得繼續(xù)努力。

礙于自己的算法基礎(chǔ)太差，最近一直在做算法題，我是先刷了一段時(shí)間的題目，發(fā)現(xiàn)吃力了，才開始看的書。感覺有點(diǎn)本末倒置。其實(shí)應(yīng)該是先看看書，把算法的一些常用大類搞清楚了，形成一個(gè)知識(shí)框架，這樣在遇到問(wèn)題的時(shí)候可以知道往那些方向上面思考，可能會(huì)好一些吧。