搜索(又称:完整搜索、Complete search)是一种将问题的 状态 依次枚举完全的方法统称。该方法的核心思路为枚举一个问题的所有情况,将所有情况罗列出后对所求的目标就行统计与分析。对于问题状态的枚举有多种方法,一般分为深度优先搜索、广度优先搜索、启发式搜索等。前两种的搜索思路的差别在搜索树中可以体现出来。
搜索树又称解答树,是对问题 状态 的表现形式,一个问题的状态可由多个缩小规模的状态得出,可由树型结构描绘出状态之间的关系。例如问题全排列中,问题最原始的状态为:“n位任意空位,没有强制要求填任何数”的情况。该状态可由“n-1位任意空位,要求第一位填写1”、“n-1为任意空位,要求第一位填写2”…等状态组成。可由下图表示:
┌───────────┐ │(*,*,*...*)│ └────┬──────┘ │ ┌─────────────────┼───────────────────┐ │ │ │ ┌─────┴─────┐ ┌────┴──────┐ ┌─────┴─────┐ │(1,*,*...*)│ │(2,*,*...*)│ │(3,*,*...*)│ ...... └─────┬─────┘ └───────────┘ └───────────┘ │ ┌──────────┴─────────┐ │ │ ┌─────┴─────┐ ┌──────┴────┐ │(1,2,*...*)│ │(1,3,*...*)│ ...... └───────────┘ └───────────┘
TODO
简单枚举指使用递归与回溯能完成的DFS,在这类问题中使用递归来完成状态的枚举。在递归过程中设计不同的回溯方式,传递不同的参数,即可解答不同种的问题,例如接下来提到的3种方式。
TODO
TODO
TODO
在搜索过程中会有大量重复或者无效的状态会被枚举到,剪枝即将无用的部分在搜索过程中减去。