搜索（又称：完整搜索、Complete search）是一种将问题的 状态 依次枚举完全的方法统称。该方法的核心思路为枚举一个问题的所有情况，将所有情况罗列出后对所求的目标就行统计与分析。对于问题状态的枚举有多种方法，一般分为深度优先搜索、广度优先搜索、启发式搜索等。前两种的搜索思路的差别在搜索树中可以体现出来。

搜索树又称解答树，是对问题 状态 的表现形式，一个问题的状态可由多个缩小规模的状态得出，可由树型结构描绘出状态之间的关系。例如问题全排列中，问题最原始的状态为：“n位任意空位，没有强制要求填任何数”的情况。该状态可由“n-1位任意空位，要求第一位填写1”、“n-1为任意空位，要求第一位填写2”…等状态组成。可由下图表示：

                              ┌───────────┐
                              │(*,*,*...*)│
                              └────┬──────┘
                                   │
                 ┌─────────────────┼───────────────────┐
                 │                 │                   │
           ┌─────┴─────┐      ┌────┴──────┐      ┌─────┴─────┐
           │(1,*,*...*)│      │(2,*,*...*)│      │(3,*,*...*)│    ......
           └─────┬─────┘      └───────────┘      └───────────┘
                 │
      ┌──────────┴─────────┐
      │                    │
┌─────┴─────┐       ┌──────┴────┐
│(1,2,*...*)│       │(1,3,*...*)│         ......
└───────────┘       └───────────┘

TODO

简单枚举指使用递归与回溯能完成的DFS，在这类问题中使用递归来完成状态的枚举。在递归过程中设计不同的回溯方式，传递不同的参数，即可解答不同种的问题，例如接下来提到的3种方式。

TODO

TODO

TODO

在搜索过程中会有大量重复或者无效的状态会被枚举到，剪枝即将无用的部分在搜索过程中减去。

1. 可行性剪枝：不符合题目条件的部分减去
2. 最优性剪枝：如果当前的代价或收益已经比最优的还要差，则该情况要被减去
3. 记忆化：将状态的结果进行记录，其他状态在使用该状态结果时不必重复计算该状态的结果。