剪枝
避免访问那些已经不可能成功的后继状态
最优性剪枝
若当前价值加估价已经大于目前最优解,则剪掉,估价越高效果越好
引入随机
解空间非常大的时候,可以引入随机来减少解空间
预处理
预处理一些数据,方便之后剪枝dfs与bfs结合
折半搜索
把数据范围分成2分,时间复杂度从$O(M^n)$降低到$O(M^{\frac{n}{2 }} )$
双向搜索
起点和终点开始,同时开始搜索
迭代加深
对于深度很浅,但是搜索树爆炸式增长,迭代加深可以有效的搜索出来,比二分更快,因为不需要访问过多的节点。
A*思想(dijkstra算法)
带权宽搜,权值是估价函数