摘要：不撞南墻不回頭深度優先搜索基礎部分對于深度優先搜索和廣度優先搜索，我很難形象的去表達它的定義。這就是深度優先搜索了，當然，這個題目我們還有別的解法，這就到了我們說的廣度優先搜索。

基礎部分

對于深度優先搜索和廣度優先搜索，我很難形象的去表達它的定義。我們從一個例子來切入。

輸入一個數字n，輸出1~n的全排列。即n=3時，輸出123，132，213，231，312，321

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

我們用深度優先遍歷搜索的思想來考慮這個問題。

到1號箱子面前時，我們手里有1，2，3三種牌，我們把1放進去，然后走到2號箱子面簽，手里有2，3兩張牌， 然后我們把2放進去，再走到3號箱子前，手里之后3這張牌，所以把3放進去，然后再往前走到我們想象出來的一個4號箱子前，我們手里沒牌了，所以，前面三個箱子中放牌的組合就是要輸出的一種組合方式。（123）

然后我們后退到3號箱子，把3這張拍取出來，因為這時我們手里只有一張牌，所以再往里放的話還是原來那種情況，所以我們還要再往后推，推到2號箱子前，把2從箱子中取出來，這時候我們手里有2，3兩張牌，這時我們可以把3放進2號箱子，然后走到3號箱子中把2放進去，這又是一種要輸出的組合方式.（132）

就找這個思路繼續下去再次回退的時候，我們就要退到1號箱，取出1，然后分別放2和3進去，然后產生其余的組合方式。

有點啰嗦，但是基本是這么一個思路。

我們來看一下實現的代碼

    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]]

我們創建的a這個list相當于上面說到的箱子，flag這個list呢，來標識某一個數字是否已經被用過了。

其實主要的思想就這dfs方法里面的這個for循環中，在依次的排序中，我們默認優先使用最小的那個數字，這個for循環其實就代表了一個位置上有機會放所有的這些數字，這個flag標識就避免了在一個位置重復使用數字的問題。

如果if 成立，說明當前位置可以使用這個數字，所以把這個數字放到a這個數組中，然后flag相同為的標識改為True，也就是說明這個數已經被占用了，然后在調用方法本身，進行下一步。

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

思路大概就是這樣子的，這就是深度優先搜索的一個簡單的場景。用debug跟一下，一步一步的來看代碼就更清晰的了。

迷宮問題

上面我們已經簡單的了解了深度優先搜索，下面我們通過一個迷宮的問題來進一步數字這個算法，然后同時引出我們的廣度優先搜索。

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

我們抽象成模型來看一下

start代表起點，end代表終點，x代表障礙物也就是不能通過的點。

首先我們來分析一下，從start（0，0）這個點，甚至說是每一個點出發，都有四個方向可以走，上下左右，僅對于（0，0）這個點來說，只能往右和下走，因為往左和上就到了單元格外面了，我們可以稱之為越界了。

我們用深度優先的思想來考慮的話，我們可以從出發點開始，全部都先往一個方向走，然后走到遇到障礙物或者到了邊界的情況下，在改變另一個方向，然后再走到底，這樣一直走下去。

拿到我們這個題目中，我們可以這樣來思考，在走的時候，我們規定一個右下左上這樣的順序，也就是先往右走，走到不能往右走的時候在變換方向。比如我們從(0,0)走到（0，1）這個點，在（0，1）這個點也是先往右走，但是我們發現（0，2）是障礙物，所以我們就改變為往下走，走到（1，1），然后在（1，1）開始也是先向右走，這樣一直走下去，直到找到我們的目標點。

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

下面我貼一下代碼

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

        # 5行 4 列
        flag = [[False for i in range(n)] for j in range(m)]
        # 存儲不能同行的位置
        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):

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

            # 右下左上
            for i in range(4):
                # 下一個點
                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 改點還沒有走過
                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

首先flag這個算是二位數組吧，來記錄我們位置是否占用了，然后a這個數組，是來記錄整個單元格的，也就是標識那些障礙物的位置坐標。同樣的，重點是這個dfs方法，他的參數x,y是指當前的坐標，step是步數。

這個大家可以看到一個director_l的數組，他是來輔助我們根據當前左邊和不同方向計算下一個位置的坐標的。

dfs中我們已經注明了搜索停止的判斷方式，也就是找到（3，2）這個點，然后下面的for循環，則代表四個不同的方向，每一個方向我們都會先求出他的位置，然后判斷是否越界，如果沒有越界在判斷是否是障礙或者是否已經走過了，滿足了所有的判斷條件，我們在繼續往下一個點，直到找到目標，比較路徑的步數。

這就是深度優先搜索了，當然，這個題目我們還有別的解法，這就到了我們說的廣度優先搜索。

我們先大體說一下廣度優先搜索的思路，深度優先是先窮盡一個方向，而廣度優先呢，則是基于一個位置，先拿到他所有能到達的位置，然后分別基于這些新位置，拿到他們能到達的所有位置，一次這樣層層的遞進，直到找到我們的終點。

從（0，0）出發，可以到達（0，1）和（1,0），然后再從（0，1)出發到達（1，1），從（1，0）出發，到達（2，0）和（1，1），以此類推。

所以我們我們維護一個隊列來儲存每一層遍歷到達的點，當然了，不要重復儲存同一個點。我們用一個指針head來標識當前的基準位置，也就是說最開始指向（0，0），當儲存完畢所有（0，0）能抵達的位置時，我們就應該改變我們的基準位置了，這時候head++，就到了（0，1）這個位置，然后儲存完他能到的所有位置，head++，就到了（1，0），然后繼續。

    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)]

        # 儲存地圖信息
        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
        # 隊列
        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]
            # 處理四個方向
            for i in range(4):

                # 當前位置
                currentX = last_node.x + director_l[i][0]
                currentY = last_node.y + director_l[i][1]

                # 找到目標
                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:


                    #不是目標
                    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

首先我們定義了一個節點Node的類，來封裝節點位置和當前的步數，flag，a，director_l這兩個數組作用跟深度優先搜索相同，l是我們維護的隊列，head指針指向當前基準的那個位置的，index指針指向隊列尾。首先我們先把第一個Node（也就是起點）存進隊列，廣度優先搜索不需要遞歸，只要加一個循環就行。

每次走到符合要求的位置，我們便把他封裝成Node來存進對列中，每存一個index都要+1.

head指針必須在一個節點四個方向都處理完了之后才可以+1，變換下一個基準節點。

簡單的介紹了深度優先搜索和廣度優先搜索，深度優先有一種先窮盡一個方向然后結合使用回溯來找到解，廣度呢，可能就是每做一次操作就涵蓋了所有的可能結果，然后一步步往后推出去，找到最后的解。這算我個人的理解吧，不準確也不官方，思想也只能算是稍有體會，還得繼續努力。

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