搜索ex

剪枝

避免访问那些已经不可能成功的后继状态

最优性剪枝

若当前价值加估价已经大于目前最优解,则剪掉,估价越高效果越好

引入随机

解空间非常大的时候,可以引入随机来减少解空间

预处理

预处理一些数据,方便之后剪枝dfs与bfs结合

折半搜索

把数据范围分成2分,时间复杂度从$O(M^n)$降低到$O(M^{\frac{n}{2 }} )$

双向搜索

起点和终点开始,同时开始搜索

迭代加深

对于深度很浅,但是搜索树爆炸式增长,迭代加深可以有效的搜索出来,比二分更快,因为不需要访问过多的节点。

A*思想(dijkstra算法)

带权宽搜,权值是估价函数