Exhaustive Search - 窮竭搜索
- 遞歸函數
- 隊列
- 深度優先搜索(DFS, Depth-First Search),又常稱為回溯法
- 廣度優先搜索(BFS, Breadth-First Search)
1, 2, 3 往往在深搜或者廣搜中體現。
回溯法包含了多類問題,模板類似。
使用回溯法的一般步驟:
- 確定所給問題的解空間:首先應明確定義問題的解空間,解空間中至少包含問題的一個解。
- 以深度優先方式搜索解空間,並在搜索過程中用剪枝函數避免無效搜索。
Reference
- 《挑戰程序設計競賽》Chaper 2.1 p26 最基礎的「窮竭搜索」
- 全面解析回溯法:算法框架與問題求解 - 五嶽 - 博客園