【算法】回溯算法精講：從深度優先搜索到剪枝優化詳情 - C語言,算法,遞歸,回溯,C,C++,後端開發,yyds乾貨盤點蒙奇D索隆博客

(回溯)

導讀

大家好，很高興又和大家見面啦！！！

在前面探討遞歸算法的基礎上，我們今天將進一步深入這一重要編程思想的應用領域。

遞歸通過函數自我調用將複雜問題分解，其核心思想與深度優先遍歷（DFS）“一路到底，再回溯而上”的策略天然契合。DFS作為遞歸在樹與圖等數據結構中的經典體現，為我們理解更復雜的算法範式奠定了堅實基礎。

接下來，我們將一同探索一種在DFS基礎上增強的、更為強大的算法思想——回溯算法。它將帶領我們系統性地遍歷問題的所有可能解，並學習如何通過有效的“剪枝”來優化搜索過程。

現在，讓我們直接進入正文，開啓這段探索之旅。

一、回溯

1.1 定義

回溯法是一種通過系統性地、深度優先地遍歷狀態空間樹來搜索問題所有可能解的算法範式。

適用範圍：回溯法適用於那些需要檢查大量可能組合的組合優化問題和決策問題。

1.2 核心要點

狀態空間樹：問題的解可以被表示為一棵樹，稱為狀態空間樹或解空間樹。

樹的每個節點代表問題求解過程中的一個部分解或一個狀態。
樹的邊代表一個決策步驟，即從父節點的狀態通過一個選擇轉移到子節點的狀態。
樹的根節點代表初始狀態（空解）。
樹的葉子節點代表終結狀態，可能是一個完整解，也可能是一個無效的解。

flowchart TB
	subgraph Tree[空間狀態樹]
		direction TB
		begin[開始]
		a[狀態1]
		b[狀態2]
		c[狀態3]
		begin--->a
		begin--->b
		begin--->c
		d[...]
		e[...]
		f[...]
		a--->d
		b--->e
		c--->f
		g[最終狀態]
		h[最終狀態]
		i[最終狀態]
		d--->g
		e--->h
		f--->i
	end

深度優先搜索：回溯法以深度優先的順序遍歷這棵狀態空間樹。

它從根節點開始，沿着一條路徑一直向下擴展，直到達到一個葉子節點或確定當前分支無法產生有效解。

隱式圖搜索：回溯法並不需要事先在內存中構建整棵狀態空間樹（這通常是指數級大小的，不可能完成）。

樹是“隱式”存在的，算法在運行過程中只維護當前正在探索的路徑。

回退操作：這是回溯法的標誌性操作。當算法到達一個節點，確定從該節點出發無法找到有效解時（即該節點及其子樹不包含可行解），它會撤銷最近做出的選擇，回退到父節點，並嘗試父節點狀態下的下一個可選分支。

二、剪枝

2.1 定義

剪枝是一種用於優化搜索過程（如回溯法、分支限界法）的技術。

核心思想：在狀態空間樹的遍歷過程中，提前識別並跳過那些不可能產生最優解或可行解的分支，從而減少需要實際探索的節點數量。

2.2 核心要點

目標：顯著降低算法的時間複雜度。雖然最壞情況下的時間複雜度可能仍是指數級，但通過剪枝，平均情況下的運行時間會得到極大改善，使得解決規模較大的問題成為可能。

約束函數：這是實現剪枝的主要工具。它是一個判斷函數，在搜索過程中，當擴展一個節點（生成子節點）之前或之後，用約束函數來檢查該節點所代表的部分解。

如果約束函數返回“假”：意味着從當前部分解繼續擴展，不可能得到任何滿足問題約束條件的可行解。因此，算法可以立即停止探索以該節點為根的整個子樹。這個過程就是“剪枝”。

限界函數：在優化問題（如旅行商問題、0-1揹包問題）中，除了約束函數，還會使用限界函數進行剪枝。限界函數計算當前節點可能達到的最好結果（上界/下界）。

如果這個“可能的最好結果”已經比當前已知的某個完整解還要差，那麼繼續探索該分支就沒有意義，可以將其剪掉。這通常與分支限界法結合得更緊密，但思想相通。

剪枝不是一個獨立的算法，而是一種嵌入在搜索算法中的優化策略。

三、個人理解

回溯算法 可以簡單的理解為：在 深度優先搜索 的過程中，從一個節點回退到其父節點的操作；

剪枝則可以理解為：在搜索算法的過程中，若當前滿足某一條件，則跳過當前的搜索對象的操作；

為了方便大家進一步理解這兩個概念，下面我們以獲取 1/2/3 這三個數的全部排列為例來進行説明：

當我們要獲取三位數的全排列時，我們可以將問題分成3部分：

第一位數：從三個數中選擇一個
第二位數：從剩下的兩個數中選擇一個
第三位數：從剩下的一個數中選擇一個

如果我們將這一過程以樹的形式進行展示的話，我們就會得到這麼一棵樹：

flowchart TB
begin[開始]
	subgraph A[第一位數]
		direction TB
		a[1]
		b[2]
		c[3]
	end
begin--->a
begin--->b
begin--->c
	subgraph B[第二位數]
		direction TB
		subgraph B1[情況1]
			d1[1]
			e1[2]
			f1[3]
		end
		subgraph B2[情況2]
			d2[1]
			e2[2]
			f2[3]
		end
		subgraph B3[情況3]
			d3[1]
			e3[2]
			f3[3]
		end
	end
	subgraph C[第三位數]
		direction TB
		subgraph C1[情況1]
			g1[1]
			h1[2]
			i1[3]
		end
		subgraph C2[情況2]
			g2[1]
			h2[2]
			i2[3]
		end
		subgraph C3[情況3]
			g3[1]
			h3[2]
			i3[3]
		end
		subgraph C4[情況4]
			g4[1]
			h4[2]
			i4[3]
		end
		subgraph C5[情況5]
			g5[1]
			h5[2]
			i5[3]
		end
		subgraph C6[情況6]
			g6[1]
			h6[2]
			i6[3]
		end
	end
	a --->e1
	a--->f1
	b--->d2
	b--->f2
	c--->d3
	c--->e3
	e1--->i1
	f1 ---> h2
	d2 --->i3
	f2 --->g4
	d3 ---> h5
	e3 ---> g6

若我們不做任何處理的情況下，這三位數在進行選擇時，每一位上的數都會存在3種選擇，這裏我們以獲取第一種排列：123 為例：

flowchart TB
	subgraph A[第一位數]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位數]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	subgraph C[第三位數]
		direction TB
		g1[1]
		h1[2]
		i1[3]
	end
	A--->B--->C

第一位數我們選擇 1 ，那麼在選擇第二位數時，我們在不做任何處理的情況下，我們同樣會選擇 1：

flowchart TB
	subgraph A[第一位數]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位數]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	a ---> d1

但是 1 已經在第一位數中被選擇，因此我們在選擇第二位數時，就無法選擇 1 這時的搜索過程我們就無需向下繼續搜索，按照 深度優先搜索 的搜索過程，這時我們會從該節點返回到其父節點；

在這個過程中，就同時涉及回溯與剪枝：

從第二位數 1 這個節點返回到第一位數 1 這個父節點的過程就是回溯

flowchart BT
	subgraph A[第一位數]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位數]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	d1 --->|回溯|a

我們捨棄掉第二位數 1 這條路徑的過程就是剪枝

flowchart TB
	subgraph A[第一位數]
		direction TB
		a[1]
		b[2]
		c[3]
	end
	subgraph B[第二位數]
		direction TB
		d1[1]
		e1[2]
		f1[3]		
	end
	a --->|剪枝<br>捨棄該路徑<br>|d1

從樹的角度來看，樹中的每一條路徑都是樹的一根枝葉，而我們捨棄路徑的行為就類似於修剪樹的枝葉，因此將該過程稱為剪枝還是十分形象的。

四、代碼解釋

這裏我們就以【LeetCode】專欄中的一道題：【LeetCode】組合問題——1863.找出所有子集的異或總和再求和（回溯）中的代碼為例進行説明，完整代碼如下所示：

void Subset(int* nums, int numsSize, int* ans, int* mid, int start) {
	*ans += *mid;
	for (int i = start; i < numsSize; i++) {
		*mid ^= nums[i];
		Subset(nums, numsSize, ans, mid, i + 1);
		*mid ^= nums[i];
	}
}

int subsetXORSum(int* nums, int numsSize) {
	int ans = 0, mid = 0;
	Subset(nums, numsSize, &ans, &mid, 0);
	return ans;
}

這裏的 Subset 函數就是通過遞歸實現的查找子集並獲取子集的異或和的總和。

4.1 回溯

代碼中有兩次 *mid ^= nums[i] ：

第一次是獲取子集的異或和
第二次是藉助異或的規則：a ^ b ^ b = a 來進行回溯

簡單的來説，對於數組 [1,2,3] 其子集按照起始元素可以分為三類：

[1]、[1, 2]、[1, 3]、[1, 2, 3]
[2]、[2, 3]
[3]

對於子集 [1, 2] 和 [1, 3] 而言，他們的起始元素均為 1 。當我們通過路徑：1--->2--->3 完成子集的異或以及求取 [1]、[1, 2]、[1, 2, 3] 這三個子集的異或和的總和之後，函數會開始迴歸；

當函數從節點 3 迴歸到父節點 2 時，mid 進行了一次異或操作，由原先的 *mid = 0 ^ 1 ^ 2 ^ 3 再一次異或了一個 3 於是就得到了 mid = 0 ^ 1 ^ 2 ^ 3 ^ 3 = 0 ^ 1 ^ 2，即，當函數迴歸到節點 2 時，此時的 mid 中存放的值為：*mid = 0 ^ 1 ^ 2 ；

也就是説，當我們探索相同父節點的不同分支對應的子集時，我們需要將 mid 中存儲的值從子集的異或值回溯到其父節點的異或值，在上面的實現中，就是通過第二次的異或操作實現回溯這一過程；

4.2 剪枝

在該函數實現中，我們是通過循環來找到同一父節點的不同分支，而循環的結束條件 i < numsSize 作為 界限函數 進行了一次剪枝操作，將不符合該範圍的枝葉全部剪掉；

循環的對象 i = start 以及父節點的傳參中 i + 1 作為 約束函數 同樣也執行了一次剪枝操作，該 約束函數 將下標 i 左側以及它本身的所有元素對應的枝葉全部剪掉；

通過這兩次剪枝操作，使得 Subset 函數能夠更加高效的查找子集並獲取子集的異或和以及所有子集的異或和的總和；

結語

通過本篇的探討，我們系統性地解析了回溯算法的核心思想與實現機制。回溯法作為一種通過深度優先策略遍歷狀態空間樹的算法框架，其本質在於“試探與回退”的智能搜索過程。

✨ 核心要點回顧

回溯與剪枝的協同是提升算法效率的關鍵。
- 回溯負責在路徑無效時撤銷選擇並回退
- 剪枝則通過約束函數和界限函數提前排除不可能產生解的分支
- 二者結合能顯著減少不必要的計算。
從全排列問題的實例推演，到子集異或和計算的代碼剖析，我們看到回溯算法通過“選擇-遞歸-撤銷”的通用模式解決各類組合優化問題。
理解回溯與深度優先搜索（DFS）的關係至關重要：回溯算法是對深度優先搜索的增強，通過引入狀態回退和剪枝邏輯，使其能夠高效處理組合爆炸問題。

回溯算法不僅是一種強大的編程工具，其核心的“試錯-回退-剪枝”思想，也為我們提供了一種解決複雜問題的系統性方法論：勇於嘗試，善於調整，懂得取捨。

在接下來的內容中，我們將通過一系列 LeetCode習題，繼續深入探討回溯算法在更復雜場景下的應用與實踐。大家記得關注哦！

互動話題：在學習回溯算法的過程中，你是否也聯想到了生活中哪些“試探、調整與優化”的經歷呢？歡迎在評論區分享你的故事！

互動與分享

點贊👍 - 您的認可是我持續創作的最大動力
收藏⭐ - 方便隨時回顧這些重要的基礎概念
轉發↗️ - 分享給更多可能需要的朋友
評論💬 - 歡迎留下您的寶貴意見或想討論的話題

感謝您的耐心閲讀！關注博主，不錯過更多技術乾貨。我們下一篇再見！

蒙奇D索隆博客

蒙奇D索隆博客

博客 / 詳情