当前位置:牛骨文开发手册数据结构与算法小五的算法学习之路 》 树搜索策略

1. 深度优先

维护栈

将根节点放入栈

循环弹出栈顶元素,然后将栈顶元素的子节点放入栈中

当栈顶元素满足约束条件,对其进行处理。

当栈空时,搜索结束

2. 广度优先

维护队列

将根节点放入队列

循环弹出队首元素,然后将队首的子节点放入队列中

当队首元素满足约束条件,对其进行处理。

当队空时,搜索结束

3. 爬山法

深度优先+贪心

将栈首的子节点,采用贪心策略放入栈顶

4. Best First

深度优先+广度优先

维护堆

将跟节点放入堆

将兄弟节点与孩子节点中的最优节点放入堆中

若堆首节点满足条件,对其进行处理。

堆空,搜索结束

5. 分支限界法

剪枝函数+广度优先

广度优先跑一次,找出可行解代价

对接下来的顶点,判断其代价是否优于可行解,若是,继续,否则孩子节点不予处理

6. A*算法

Best First + 代价函数