====== 搜索 ======

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

===== 搜索树 =====

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

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

===== 深度优先搜索 =====

TODO

==== 简单递归枚举 ====

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

=== 1. 指数型 ===

TODO

=== 2. 排列型 ===

TODO

=== 3. 组合型 ===

TODO

==== 剪枝 ====

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

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

=== 剪枝例题 ===


---- struct table ----
schema: problems
cols: %title%, 来源, 题目编号, 难易程度
filter: 算法分类 = 剪枝_例题
rownumbers:1
csv:0
----

==== 迭代加深 ====

===== 广度优先搜索 =====