為定義搜索范圍,應明確以下幾個方面:
1. 問題解的形式:表示成一個n元組的形式`(x[0],x[1],...,x[n-1])`
2. 顯約束:對分量`x[i]`的取值范圍限定。
3. 隱約束:為滿足問題的解而對不同分量之間施加的約束。
4. 解空間:對于問題的一個實例,解向量滿足顯約束的所有n元組構成了該實例的一個解空間。
----
在搜索的過程中,應了解幾個名詞:
1. 擴展結點:一個正在生成孩子的結點。
2. 活結點:一個自身已生成但其孩子還沒有全部生成的結點。
3. 死結點:一個所有孩子已生成的結點。
----
求解過程:
1. 定義問題的解空間。
2. 確定空間的組織結構。
3. 搜索解空間:
- 確定約束條件
- 確定限界條件
- 搜索過程
----
算法描述:
> (1)遞歸形式
```c++
// t為擴展節點在樹中所處的層次
void Backtrack(int t){
if(t > n){
//搜索層次大于解空間的樹的深度,說明找到了葉子結點,即找到了問題的一個解
output(x);
} else {
for (int i = s(n, t); i <= e(n, t); i++){
x[t] = d(i);
if(constraint(t) && bound(t)){
Backtrack(t + 1);
}
}
}
}
```
> (2)非遞歸形式
```c++
void NBacktrack(){
int t = 1;
while(t > 0){
if(s(n,t) <= e(n, t)){
for(int i = s(n, t); i <= e(n,t); i++){
x[t] = d(i);
if(constraint(t) && bound(t)){
if(t > n){
output(x);
} else {
t++;
}
}
}
} else {
t--;
}
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記