試探算法也稱為回溯算法，它實際上是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑?；厮莘ㄊ且环N選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。許多復雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。

1. 試探算法基礎

        用回溯算法解決問題的一般步驟：

        1、 針對所給問題，定義問題的解空間，它至少包含問題的一個（最優(yōu)）解。

        2 、確定易于搜索的解空間結構,使得能用回溯法方便地搜索整個解空間 。

        3 、以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索。

        確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。

        基本思想總結起來就是：從一條路往前走，能進則進，不能進則退回來，換一條路再試，直到走出為止。

2. 八皇后問題

        問題描述：

        在8*8的國際象棋上，擺放八個皇后，使其不能相互攻擊，即任意兩個皇后不能在同一行，同一列，同意斜線上，問有多少種擺法？

        求解代碼：

 n = int(input())
x = []#一個解
X = []#一組解
#檢測沖突：判斷x[k]是否與之前的x[0]~x[k-1]沖突
def conflict(k):
    global x
    for i in range(k):#遍歷前面的x[0]~x[k-1]
        if x[i] == x[k] or abs(x[i]-x[k]) == abs(i-k):
            return True
    return False
#用子集樹模板
def queens(k):
    global n
    global X,x
    if k >= n:
        X.append(x[:])#超出最低行時保存一個解
    else:
        for i in range(n):#遍歷n~n-1列
            x.append(i)#皇后置于第i列,入棧
            if not conflict(k):#剪枝
                queens(k+1)
            x.pop()#出棧
#可視化解(X代表皇后)
def show(x):
    global n
    for i in range(n):
        print('. '*(x[i])+'Q '+'. '*(n-x[i]-1))
#測試
queens(0)
print(X[-1],'\n')
print(len(X))#解的個數
show(X[-1])

        這個問題的求解首先經過一次沖突檢測，判斷是否行內沖突，然后用子集數模板，在行的序數為最大值時保存當前解，不滿足時遍歷n~n-1列，最后通過Q代表皇后來實現(xiàn)可視化，最后輸出一組數據來查看。

3. 迷宮問題

        問題描述：

        已知一個迷宮的出口，需要找到一個出口，如果存在這一的出路，輸出它的路徑。

        走迷宮的過程中呈九宮格方式，可以從上、下、左、右、左上、左下、右上和右下八個方向移動。

        代碼如下：

 import pprint, copy=
# 迷宮（1是墻，0是通路）
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 0, 1, 1, 1, 1, 0, 1],
        [1, 1, 0, 1, 0, 1, 1, 0, 1, 1],
        [1, 0, 1, 1, 1, 0, 0, 1, 1, 1],
        [1, 1, 1, 0, 0, 1, 1, 0, 1, 1],
        [1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1]]
m, n = 8, 10  # 8行，10列
entry = (1, 0)  # 迷宮入口
path = [entry]  # 一個解（路徑）
paths = []  # 一組解
# 移動的方向（順時針8個：N, EN, E, ES, S, WS, W, WN）
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
# 沖突檢測
def conflict(nx, ny):
    global m, n, maze
    # 是否在迷宮中，以及是否可通行
    if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0:   #不越界，可以通行
        return False
    return True
# 套用子集樹模板
def walk(x, y):  # 到達(x,y)格子
    global entry, m, n, maze, path, paths, directions
    if (x, y) != entry and (x % (m - 1) == 0 or y % (n - 1) == 0):  # 出口
        # print(path)
        paths.append(path[:])  # 直接保存，未做最優(yōu)化
    else:
        for d in directions:  # 遍歷8個方向(亦即8個狀態(tài))
            nx, ny = x + d[0], y + d[1]
            path.append((nx, ny))  # 保存，新坐標入棧
            if not conflict(nx, ny):  # 剪枝
                maze[nx][ny] = 2  # 標記，已訪問
                walk(nx, ny)
                maze[nx][ny] = 0  # 回溯，恢復
            path.pop()  # 回溯，出棧
# 解的可視化（根據一個解x，復原迷宮路徑，'2'表示通路）
def show(path):
    global maze
    maze2 = copy.deepcopy(maze)
    for p in path:
        maze2[p[0]][p[1]] = 2  # 通路
    pprint.pprint(maze)  # 原迷宮
    print()
    pprint.pprint(maze2)  # 帶通路的迷宮
# 測試
walk(1, 0)
print(paths[-1], '\n')  # 看看最后一條路徑
show(paths[-1])

        這個題的解題方式和上一題類似，首先進行一個沖突檢測，判斷當前路徑是否處在迷宮當中，如果不越界就可以通行，然后套用子集數模板，定義函數來進行試探迷宮，如果當前坐標是出口，就保存下來，如果不是出口，遍歷八個方向（八個狀態(tài)），如果發(fā)生沒有發(fā)生沖突檢測就去除掉次坐標，然后出站，通過一次次試探最終找到出口，最后輸出一個可視化的解來測試程序的正確性。

4. 總結

        上面是試探算法中較為經典的兩個例題，當然還有很多問題可以通過試探算法進行求解，求解的過程中可能涉及到深度優(yōu)先搜索和廣度優(yōu)先搜索，算法中的內容還有很多很多，數據結構能夠幫助我們了解更深層次的內容，有興趣的可以去學習一下數據結構相關知識，本章內容就到講這里。