本文主要是介绍数据结构算法-分支定界算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
引言
应该记得这一张图片,在A星算法里面说过 那么现在说的是换一种方式实现 如何实现?
之前不撞南墙不回头的方法-深度优先搜索 的方式
广度优先搜索方式
广度优先搜索:就是说按照顺序入队 并且搜索扩展节点 探测四面八方,如此循环直到箱子 如下图示
分支定界算法思路
将问题分成 一颗搜索树 采用广度优先搜索或者最小消耗法 来进行,
找出当前问题所有可能成为扩展问题节点
舍弃不可能产生问题节点 并且找出最优的扩展节点
将最优以及其他的计算出可能目前看来最合适的节点 放入到列表中
再从列表中选择下一个节点作为当前问题
如此循环直到找到问题 解 或者当前列表为空
选择不同的解决方式:
先进先出 的方式 :产生问题节点按照顺序加入到队列 并且由于 取扩展节点也会产生子扩展节点
等待执行顺序依次的结果
最少消耗/最大收益 的方式 :
加入的节点是最小的 按照最小的来进行处理 反而 将用最大收益处理
这篇关于数据结构算法-分支定界算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!