搜索算法（Search Algorithm）指的是在某个问题的解空间中寻找目标解的一种算法。解空间是指问题的解的集合，解空间中的每一个解都代表着问题的一个可能的解决方案。搜索算法是能在解空间中寻找目标解的算法策略。

搜索
在某个解空间S中，给定某个约束C，求出所有符合约束的解。

搜索算法根据解空间的性质主要可以分成两种：

  1. 抽象解空间：例如数值问题；
  2. 具有具体结构的解空间：例如在图中进行搜索；

抽象解空间

抽象解空间问题中，通常只关注问题的状态，而不考虑状态之间的关系，求解关键是抓住状态转移关系。

具有子结构的解空间

具有子结构的解空间中存在多个子问题，每个子问题都和原问题具有相同的结构，只是规模不同，求解的关键是抽象出子问题——通过将问题分解成子问题进行求解，并利用子问题的解来求解原问题的解。在这种情况下，搜索算法通常利用子问题之间的递归或归纳关系，将原问题分解成多个规模更小的子问题，对每个子问题进行求解，最后将子问题的解组合成原问题的解。主要包括回溯算法、贪心算法和动态规划算法。

抽象解空间和子结构解空间的关系

  1. 二者都是在一定的解空间中寻找目标解；
  2. 二者的求解过程都可以用树/图来表示；
  3. 通常二者可以相互转换：具有子结构的解空间可以通过将子问题抽象成状态来表示，而抽象解空间可以通过将状态之间的转移关系表示成子问题来进行拓展。

经典问题列举

经典问题 抽象解空间 搜索算法 具有子结构的解空间 搜索算法
八皇后 以每个格子为节点的状态空间 DFS 以每行为节点的子问题 DFS
数独游戏 以每个格子填数值为节点的状态空间 DFS 以每个未填格子为节点的子问题 DFS
迷宫 以每个格子为节点的图 BFS 以每个可行路径为节点的子问题 DFS/BFS
单词接龙 以每个单词为节点的图 BFS 以每个单词为前缀的子问题及其相邻单词为节点的图 BFS
01背包问题 以物品状态为节点 DFS/DP/分支定界 以物品个数或剩余容量为节点的子问题 DFS/DP
图的着色 以每个节点为节点的图 DFS/分支定界 以每个节点颜色为状态的子问题及其相邻节点为节点的图 DFS
TSP问题 以每个城市状态为节点的图 DP/分支定界 以城市集合为状态的子问题 DP/分支定界

注：DFS为深度优先搜索，BFS为广度优先搜索，DP为动态规划算法，分支定界为剪枝算法的一种。