搜索 总结

### 搜索的内容 一个搜索分为两部分，状态评估和状态转移。 状态评估是对某一（当前或未来）状态的状况判断，如是否合法、是否有解、是否已访问过、优越性如何；状态转移是从当前状态转移到另一个状态继续搜索。 状态评估和状态转移是交叉进行的，互相辅助，状态评估时要为状态转移提供依据，状态转移时要维护状态评估的信息。 ### 搜索的加速 要为搜索加速，就要对状态评估进行分类。状态的评估可以分为可行性评估和最优性评估两类，例如判断状态是否合法属于可行性评估，而判断状态的优越性属于最优性评估。 利用状态评估给搜索加速主要分为两类。 一是根据状态评估的结果停止状态转移，即回溯，这种方法我们一般称为剪枝。 二是根据状态评估的结果调整状态转移的顺序。我们可以让乐观估计更优的状态优先转移，从而让最优解尽早地被搜到；如果我们需要搜索的是一个顺序，那么可以让更容易失败的先枚举，如小木棍一题中按从大到小的顺序选择木棍。还要注意避免搜索状态的重复，例如愤怒的小鸟一题中强制抛物线经过当前剩下的编号最小的猪，可以避免同一个状态被多次枚举。