【人工智能/算法】搜尋求解（Solving Problems by Searching）

文章目錄

• 一、求解與搜尋
• 二、盲目式搜尋
• • 1. 深度優先搜尋（Depth First Search, DFS）
  • • 回溯搜尋（Backtracking Search）
  • 2. 廣度優先搜尋（Breadth First Search, BFS）
  • • 一緻代價搜尋（Uniform-Cost Search）
• 三、啟發式搜尋
• • 1. 爬山搜尋
  • 啟發函數（Heuristic Function） h ( n ) h(n) h(n)
  • 評價函數（Evaluation Function） f ( n ) f(n) f(n)
  • 2. 貪婪搜尋（Greedy Search）
  • 3. A算法（A Search Algorithm）
  • 4. A\*算法（A\* Search Algorithm）

人工智能問題通常是在某個可能的解答空間中尋找一個解的求解過程。

一、求解與搜尋

搜尋：根據問題實際情況,不斷尋找可利用的知識(或條件)，構造一條代價最小的推理路線，尋求問題解決的過程

搜尋技術的關鍵：2W

• What：搜尋什麼——搜尋目标
• Where：在哪裡搜尋——搜尋空間

搜尋兩個方面:

• 找到從初始事實到問題最終笞案的一條推理路徑
• 找到的這條路徑在時間和空間上複雜度最小

許多搜尋問題都可以轉化為圖搜尋問題

搜尋類型：

• 按問題表示方法分類：

• 按是否使用啟發式資訊分類：

存在問題：深度問題、死循環問題

解決方法：對搜尋深度加以限制、記錄從初始狀态到目前狀态的路徑

搜尋算法的通常類型

圖搜尋包括窮舉搜尋和啟發式搜尋

狀态空間法：利用狀态變量和操作符号表示系統或問題的有關知識的符号體系

狀态空間用四元組表示： ( S , O , S 0 , G ) (S,O,S_0,G) (S,O,S0​,G)（分别為狀态集合、操作算子集合、初始狀态集合、目标狀态集合）（ S 0 ⊂ S S_0\subset S S0​⊂S， G ⊂ S G\subset S G⊂S）

狀态空間圖：狀态=節點，邊=狀态之間的關系（操作算子）

圖搜尋政策：初始節點出發、按照問題的限制條件尋找到達目标點（狀态）路徑的方法

路徑：一個狀态序列（初始狀态→目标狀态）

一般是邊搜尋邊生産圖，而不是一開始直接把圖建構出來。

搜尋問題的描述：

• 狀态
• 動作
• 狀态轉移
• 路徑
• 代價（通過每條路徑的時間）
• 目标測試（評估目前狀态是否為所解的目标狀态）

搜尋樹：

• 根節點：初始狀态
• 目标節點：目标狀态
• 父節點
• 子節點
• 兄弟節點
• 擴充：從父節點産生子節點

搜尋空間：一系列狀态的彙集

搜尋算法的評價名額：

• 完備性：求解能力，可以確定一個解決方案
• 最優性：求解品質，提供最佳解決方案
• 時間複雜度：是花費的時間度量
• 空間複雜度：所需的最大存儲空間

時間/空間複雜度的确定：

• 分支因子 b b b：搜尋樹中每個節點最大的分支數目
• 目标節點所在的最淺深度 d d d：搜尋樹中最早出現的目标所在層數
• 狀态空間中任何路徑的最大長度 m m m：字面意思
• 狀态空間的大小 n n n：狀态空間中狀态的數目

二、盲目式搜尋

特點：沒有利用任何與問題有關的知識或資訊

1. 深度優先搜尋（Depth First Search, DFS）

基本思想：優先擴充深度最深的節點

從根節點開始，在回溯之前沿每個分支搜尋至深度界限

回溯搜尋（Backtracking Search）

是深度優先搜尋的一種，核心思想是：發現原先選擇并不優或達不到目标，就退回一步重新選擇，“走不通就退回再走”

深度優先搜尋和回溯法的主要差別是：

• 回溯法在求解過程中不報虧完整的樹結構，而深度優先搜尋則記錄下完整的搜尋樹
• 為了減少存儲空間，在深度優先搜尋中，用标志的方法記錄通路過的狀态，這種處理方法使得深度優先搜尋法與回溯法沒什麼差別了
• 回溯法花費時間較長，是以對于沒有明确的動态規劃（DP）和遞歸解法的或問題要求滿足某種性質（限制條件）的所有解或最優解時，才考慮使用回溯法

深度優先搜尋的特點：

• 具有通用性
• 每次選擇一個深度最深的節點進行擴充
• 一般不能保證找到最優解，可能遇到“死循環”，是不完備搜尋
• 可以加入深度限制——到達某深度強制進行回溯，但限制過深則影響效率，限制過淺則可能找不到解
• 占用大量的時間和空間
• 存在搜尋與回溯交替出現的現象

2. 廣度優先搜尋（Breadth First Search, BFS）

基本思想：優先擴充同級直接相連的節點

以接近起始節點的程度依次擴充節點、逐層搜尋：從根節點開始，在移動到下一個深度級别的節點之前，探索目前深度的所有鄰居節點

廣度優先搜尋的特點：

• 優先搜尋深度淺的節點
• 具有通用性
• 當問題有解時一定能找到解，是完備的搜尋
• 若找到目标節點，一定是最淺的目标節點
• 如果路徑是非遞減函數，廣度優先搜尋是最優的

深度優先搜尋與廣度優先搜尋比較：

算法	深度優先搜尋（DFS）	廣度優先搜尋（BFS）
完備性	不一定（若解不在某個分支，而這個分支又是無窮分支，那就永遠出不來了）	完備（在分支因子 b b b優有限的情況下）
最優性	不具備	最優（如果路徑代價是節點深度的非遞減函數） 不一定最優（通常情況下）
時間複雜度	O ( b min ⁡ ( m , l ) ) O(b^{\min(m,l)}) O(bmin(m,l))	O ( b d ) O(b^d) O(bd)
空間複雜度	O ( b min ⁡ ( m , l ) ) O(b^{\min(m,l)}) O(bmin(m,l))	O ( b d ) O(b^d) O(bd)

注解：

1. b , d , m , l b,d,m,l b,d,m,l分别為分支因子、解的深度、搜尋樹最大深度、深度限制。解的深度是解所在的深度，而搜尋樹的最大深度是DFS過程中探到的最大深度。
2. 如果 m > d m>d m>d則DFS的時間複雜度會很高，但如果解決方案密集，可能比BFS快很多
3. BFS最優的情況是路徑代價是節點深度的非遞增函數，因為BFS一定搜尋到的是深度最淺的目标節點，非遞減函數在深度最淺的時候值也最小
4. BFS占用空間很大，DFS則是一條路走到黑

一緻代價搜尋（Uniform-Cost Search）

政策：總是擴充路徑消耗最小的節點 N N N， N N N點的路徑消耗等于前一點的路徑消耗+前一點到 N N N節點的路徑消耗

一緻代價搜尋是BFS的擴充，使用優先隊列而不是普通隊列儲存邊緣中的狀态；如果每一步的代價全部相等，則與BFS相同

一緻代價搜尋與Dijkstra算法的對比：

• 相同點：
  • 求解初始節點到目标節點最短路徑的時間複雜度相同，代碼結構相同，每次擴充的節點相同，邏輯相同
• 不同點：
  • 一緻代價搜尋在搜尋到目标節點後就停止了，而Dijkstra需要求出圖中所有節點的最短路徑
  • Dijkstra需要事先明确所有節點，需要在記憶體中存儲整張圖；而一緻代價搜尋不需要

三、啟發式搜尋

啟發：應用特定的經驗法則或從經驗衍生出來的論據，提高解決複雜問題的效率

啟發式搜尋（Heuristic Search）：利用啟發方式獲得的領域知識，通過限定搜尋深度或者限定搜尋寬度來縮小問題空間，避開沒有結果的搜尋路徑，也稱有資訊搜尋

• 引導搜尋忽略最沒有希望的路徑，沿着一條最可能的路徑到達解
• 不是嚴格按照DFS、 BFS預先确定方式或方法，“憑經驗”或“試錯”來确定要下一步擴充的節點（不是一次性生産所有的後續節點）

1. 爬山搜尋

模拟爬山過程，随機選擇一個位置（節點）爬山，每次朝着更高的方向移動，直至山頂，即每次都在臨近的空間中選擇最優解作為目前解，直到局部最優解

從目前的節點開始，與周圍的鄰居節點的值進行比較

如果目前節點是最大的，那麼傳回目前節點，作為最大值（即山峰最高點）；反之就用最高的鄰居節點來替換目前節點，實作向山峰的高處攀爬的目的，直到達到最高點

爬山搜尋的特點：

• 局部最優方法，不是全面搜尋，結果可能不是最佳
• 一般存在以下問題：
  1. 局部最大：某個節點比周圍任何一個鄰居都高，卻不是整個問題的最高點；
  2. 高地(平頂)：搜尋一旦到達高地，就無法确定搜尋最佳方向，會産生随機走動，使得搜尋效率降低；
  3. 山脊：搜尋可能會在山脊的兩面來回震蕩，前進步伐很小
• 算法會陷入局部最優解，能否得到全局最優解取決于初始點的位置

啟發函數（Heuristic Function） h ( n ) h(n) h(n)

啟發函數：一個關于節點的函數 h ( n ) h(n) h(n)，用于評估目前狀态與目标狀态接近的程度（例如用曼哈頓距離、歐幾裡得距離等）

h ( n ) ≥ 0 h(n)\ge 0 h(n)≥0

h ( n ) h(n) h(n)越小，表示目前狀态 n n n越接近目标狀态

h ( n ) = 0 h(n)=0 h(n)=0表示已達到目标

啟發搜尋利用啟發函數的值将問題狀态的描述轉化為問題解決程度的描述

評價函數（Evaluation Function） f ( n ) f(n) f(n)

評價函數：用于評價節點重要程度的函數，其主要任務是确定節點的優先級程度

評價函數 f ( n ) f(n) f(n)的一般形式： f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)

其中 g ( n ) g(n) g(n)是從初始狀态到目前狀态已經付出的代價， h ( n ) h(n) h(n)是啟發函數（從目前狀态到目标狀态的代價的評估）

f ( n ) = g ( n ) f(n)=g(n) f(n)=g(n)：一緻代價搜尋，按照已付出的代價進行搜尋（如廣度優先搜尋），具有完備性

f ( n ) = h ( n ) f(n)=h(n) f(n)=h(n)：按照啟發函數向最靠近目标的狀态（節點）搜尋（如貪婪搜尋），不具有完備性

2. 貪婪搜尋（Greedy Search）

貪婪最佳優先搜尋：試圖擴充離目标最近的節點以便盡快找到問題的解

評價函數 f ( n ) f(n) f(n)僅使用啟發式資訊： f ( n ) = h ( n ) f(n)=h(n) f(n)=h(n)，僅依賴從目前狀态到目标狀态間的剩餘距離

局部擇優選取，其自的不是為了找到全部解，而隻是找出一種可行解（目前條件下的最優）含當然找不出全局最優解，但具有高效性

大部分的貪婪算法都是基于圖的方式尋找最優路徑

核心：每一步試圖找離目标最近的節點

貪婪最佳優先搜尋的特點：

• 不是最優搜尋
• 對錯誤的起點比較敏感（可能有死循環）
• 是不完備搜尋
• 最壞情況下的時間、空間複雜度： O ( b m ) O(b^m) O(bm)，其中 b b b為節點的分支因子數目， m m m為搜尋空間的最大深度
• 貪婪算法總是做出目前最好的選擇
  • 貪婪選擇的依據是目前的狀态，而不是問題的目标
  • 貪婪選擇是不計後果的
  • 貪婪算法通常以自頂向下的方法簡化子問題
• 貪婪算法求解的問題具備以下性質：
  • 貪婪選擇性質：問題的最優解可以通過貪婪選擇實作
  • 最優子結構性質：問題的最優解包含子問題的最優解
• 貪婪選擇性質的證明（數學歸納法）
  • 證明問題的最優解可以由貪婪選擇開始（即第一步可貪心）
  • 證明貪心選擇後得到的子問題滿足最優子結構（即步步可貪心）

例 （洛谷P3817 小A的糖果） 小A有 n n n個糖果盒，第 i i i盒有 a i a_i ai​個糖果。小 A A A每次可以從其中一盒糖果中吃掉一顆，他想知道，要讓任意兩個相鄰的盒子中糖的個數之和都不大于 x x x，至少得吃掉幾顆糖。

分析 假設從第 i i i盒吃 c i c_i ci​個，求 min ⁡ y = ∑ i = 1 n c i s . t .   ( a i − c i ) + ( a i + 1 − c i + 1 ) ≤ x ,   1 ≤ i ≤ n − 1 0 ≤ c i ≤ a i ,   1 ≤ i ≤ n \min y=\sum\limits_{i=1}^n c_i\\s.t.\ (a_i-c_i)+(a_{i+1}-c_{i+1})\le x,\ 1\le i\le n-1\\ 0\le c_i\le a_i,\ 1\le i\le n miny=i=1∑n​ci​s.t. (ai​−ci​)+(ai+1​−ci+1​)≤x, 1≤i≤n−10≤ci​≤ai​, 1≤i≤n這個問題中，每個狀态即為目前各盒的糖果數，目标狀态滿足相鄰兩盒糖果數之和小于等于 x x x，初始狀态為 s 0 = ( a 1 , a 2 , ⋯   , a n ) s_0=(a_1,a_2,\cdots,a_n) s0​=(a1​,a2​,⋯,an​)，狀态轉移為從某盒吃掉一個糖果。

設目前狀态為 s s s， s s s狀态下第 i i i盒剩餘的糖果數為 b i ( s ) b_i^{(s)} bi(s)​， b i ( s 0 ) = a i b_i^{(s_0)}=a_i bi(s0​)​=ai​。定義啟發函數 h ( s ) = ∑ i = 1 n − 1 max ⁡ ( 0 , b i ( s ) + b i + 1 ( s ) − x ) h(s)=\sum\limits_{i=1}^{n-1}\max\left(0,b_i^{(s)}+b_{i+1}^{(s)}-x\right) h(s)=i=1∑n−1​max(0,bi(s)​+bi+1(s)​−x)，目标狀态 t t t的啟發函數值 h ( t ) = 0 h(t)=0 h(t)=0。對于任何目前狀态 s s s，設下一狀态為 u u u，如果吃兩端（第 1 1 1盒或第 n n n盒）最多隻能使 h ( u ) ≥ h ( s ) − 1 h(u)\ge h(s)-1 h(u)≥h(s)−1，而吃中間的（第 2 , 3 , ⋯   , n − 1 2,3,\cdots,n-1 2,3,⋯,n−1盒）至多使 h ( u ) ≥ h ( s ) − 2 h(u)\ge h(s)-2 h(u)≥h(s)−2，是以吃任何中間的都是最優的。同時，如果 a i − 1 + a i > x a_{i-1}+a_i>x ai−1​+ai​>x且 a i + a i + 1 > x a_{i}+a_{i+1}>x ai​+ai+1​>x，那麼吃第 i i i盒能使 h ( u ) = h ( s ) − 2 h(u)=h(s)-2 h(u)=h(s)−2，最劃算。綜上，對于 a i ( 2 ≤ i ≤ n ) a_i(2\le i\le n) ai​(2≤i≤n)，若 b i − 1 + a i > x b_{i-1}+a_i>x bi−1​+ai​>x，則令 c i = a i + 1 + a i − x c_i=a_{i+1}+a_i-x ci​=ai+1​+ai​−x，使得 b i = a i − c i − 1 b_i=a_i-c_{i-1} bi​=ai​−ci−1​。（即 c i = max ⁡ ( 0 , b i − 1 + a i − x ) c_i=\max(0,b_{i-1}+a_i-x) ci​=max(0,bi−1​+ai​−x)。）代碼如下：

#include <iostream>

using namespace std;

const int MAXN = 1e5 + 5;
int n, x, a[MAXN], b[MAXN];

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    long long y = 0;
    b[1] = a[1];
    for(int i = 2; i <= n; ++i)
    {
        if(b[i - 1] + a[i] > x)
        {
            int c = b[i - 1] + a[i] - x;
            y += c;
            b[i] = a[i] - c;
        }
        else
        {
            b[i] = a[i];
        }
    }
    cout << y << endl;
    return 0;
}
           

算法的最優性證明如下：若該政策不是最優，假設有比我們的答案 y y y更小的 y ′ y' y′，不妨設 y ′ = y − 1 y'=y-1 y′=y−1，則必 ∃ j ( 2 ≤ j ≤ n ) \exists j(2\le j\le n) ∃j(2≤j≤n)使得 c i ′ = c i − 1 c_i'=c_i-1 ci′​=ci​−1。我們知道， c i = max ⁡ ( 0 , b i − 1 + a i − x ) ( 2 ≤ i ≤ n ) c_i=\max(0,b_{i-1}+a_i-x)(2\le i\le n) ci​=max(0,bi−1​+ai​−x)(2≤i≤n)，當 b i − 1 + a i − x > 0 b_{i-1}+a_i-x>0 bi−1​+ai​−x>0時， b i − 1 + b i = x b_{i-1}+b_{i}=x bi−1​+bi​=x。但 c i ′ = c i − 1 c_i'=c_i-1 ci′​=ci​−1，使得 b i ′ = b i + 1 b_i'=b_i+1 bi′​=bi​+1，此時 b i − 1 + b i = x + 1 > x b_{i-1}+b_i=x+1>x bi−1​+bi​=x+1>x，是以條件不滿足，沖突。是以我們的政策是最優政策。

3. A算法（A Search Algorithm）

A算法的評價函數 f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)，其中：

• g ( n ) g(n) g(n)為從初始狀态到目前狀态的實際路徑代價（并不一定最優，例如可以是目前狀态在搜尋樹中的深度，但不一定是最小深度）
• h ( n ) h(n) h(n)是啟發函數，代表從目前狀态到目标狀态估計的最低代價路徑的代價
• f ( n ) f(n) f(n)是從初始狀态經過節點 n n n到目标狀态的最低代價路徑的估計總代價值

優先擴充 f ( n ) f(n) f(n)最小的節點進行擴充

4. A*算法（A* Search Algorithm）

A*搜尋：最小化總的解決方案代價估計值的最佳優先搜尋

A算法對評價函數中的啟發函數未做任何規定，不能評價搜尋結果的優劣

A*算法的評估函數 f ∗ ( n ) = g ∗ ( n ) + h ∗ ( n ) f^*(n)=g^*(n)+h^*(n) f∗(n)=g∗(n)+h∗(n)，其中：

• g ∗ ( n ) g^*(n) g∗(n)：從起始點到節點 n n n的路徑最低代價
• h ∗ ( n ) h^*(n) h∗(n)：從節點 n n n到目标節點的最低代價路徑的代價
• f ∗ ( n ) f^*(n) f∗(n)：從起始點出發、經過節點 n n n、到達目标節點的最佳路徑的估計總代價

與A算法相比（參考Stackexchange）：

• g ( n ) g(n) g(n)是從初始節點到目前節點的（在目前搜尋樹上的）路徑長度，而 g ∗ ( n ) g^*(n) g∗(n)是從初始節點到目前節點的最短路徑長度，故 g ( n ) ≥ g ∗ ( n ) > 0 g(n)\ge g^*(n)>0 g(n)≥g∗(n)>0
• h ( n ) h(n) h(n)是從目前節點到目标節點的估計的代價，而 h ∗ ( n ) h^*(n) h∗(n)是從目前節點到目标節點的真實的代價，一般 h ∗ ( n ) h^*(n) h∗(n)是無法計算的，用 h ( n ) h(n) h(n)代替； h ( n ) ≤ h ∗ ( n ) h(n)\le h^*(n) h(n)≤h∗(n)

保證A*搜尋最優化的條件：

A*搜尋使用到目前的路徑代價 g ( n ) g(n) g(n)+到目标的最低路徑代價 h ( n ) h(n) h(n)。若啟發函數 h ( n ) h(n) h(n)滿足下列條件，則A*算法既完備又最優：

• 采納性：啟發函數 h ( n ) h(n) h(n)是一個可接受的啟發，即不高估到目标的代價（ h ( n ) ≤ h ∗ ( n ) h(n)\le h^*(n) h(n)≤h∗(n)），則總代價 f ( n ) f(n) f(n)也不會高估節點 n n n的求解的代價
• 一緻性：啟發函數 h ( n ) h(n) h(n)是一緻的，即通過節點 n n n達到目标的代價不高于從節點 n n n經過其他節點 n ′ n' n′達到目标的代價（類似于三角不等式）

啟發式搜尋的特點：

• 優點：
  • 與盲目搜尋不同，利用搜尋過程中所得到的問題本身的一些特征資訊，可縮小搜尋範圍，減少盲自性，有效提高搜尋效率，更容易解決複雜的問題
• 關鍵：
  1. 具有啟發函數
  2. 具有評價函數
  3. 啟發資訊（利用額外資訊，例如利用曼哈頓距離、切比雪夫距離）
• 缺點：
  • 可能不會始終提供最佳解決方案，但肯定會在合理的時間内提供良好的解決方案
  • 在不同的啟發搜尋算法中，使用不同的啟發式方法

啟發式搜尋（以及一緻代價搜尋）總結：

算法	種類	估價函數	完備性	最優性	最壞情況下的時間、空間複雜度
一緻代價搜尋	盲目式搜尋	f ( n ) = g ( n ) f(n)=g(n) f(n)=g(n)	完備	最優（如果路徑代價是節點深度的非遞減函數） 不一定最優（通常情況下）	O ( b d ) O(b^d) O(bd)（ b b b為分支因子， d d d為解的深度）
爬山搜尋	啟發式搜尋	-	不完備	非最優（僅局部最優）	-
貪婪搜尋	啟發式搜尋	f ( n ) = h ( n ) f(n)=h(n) f(n)=h(n)	不完備	非最優	O ( b m ) O(b^m) O(bm)（ b b b為分支因子， m m m為搜尋空間最大深度）
A算法	啟發式搜尋	f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)	-	不一定	-
A*算法	啟發式搜尋	f ∗ ( n ) = g ∗ ( n ) + h ∗ ( n ) f^*(n)=g^*(n)+h^*(n) f∗(n)=g∗(n)+h∗(n)（可用 h ( n ) h(n) h(n)代替 h ∗ ( n ) h*(n) h∗(n)）	啟發函數滿足條件則完備	啟發函數滿足條件則最優	-

盲目搜尋與啟發式搜尋的對比：

• 盲目搜尋（非啟發式搜尋）：
  • 隻按照預定的控制政策進行搜尋，搜尋過程中獲得的資訊并不改變政策
  • 搜尋總按照預定路線進行，沒有考慮問題本身的特性，缺乏對問題求解的針對性
  • 需求全方位的搜尋，沒有選擇最優的搜尋途徑，具有盲目性，效率不高
• 啟發式搜尋（有資訊搜尋）：
  • 根據問題本身的特性或搜尋過程中産生的一些資訊改變或調整搜尋方向，向最有希望的方向搜尋，加速問題求解并找到最優解