试题详情
- 简答题简述分支限界法及其算法思想。
-
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法,分枝定界法在搜索解空间时,也经常使用树形结构来组织解空间。然而与回溯法不同的是,回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此,可以很容易比较回溯法与分枝定界法的异同。相对而言,分枝定界算法的解空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。
算法思想:分枝限界(branch and bound)是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时,则生成从该节点移动一步即可到达的所有新节点。在生成的节点中,抛弃那些不可能导出(最优)可行解的节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充,直到找到解或活动表为空,扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点(虽然也可能存在其他的方法):
1)先进先出(FIFO)即从活节点表中取出节点的顺序与加入节点的顺序相同,因此活
节点表的性质与队列相同。
2)(优先队列)最小耗费或最大收益法在这种模式中,每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解,则活节点表可用最小堆来建立,下一个E-节点就是具有最小耗费的活节点;如果希望搜索一个具有最大收益的解,则可用最大堆来构造活节点表,下一个E-节点是具有最大收益的活节点。 关注下方微信公众号,在线模考后查看
热门试题
- 简述舍伍德算法的特点。
- 穷举法缺点是:运算量较大只适合于“有几种
- 汉诺塔的算法是递归算法解决的,所谓递归即
- 以下关于二维数组的描述中,正确的有:()
- 数据结构与算法里,二叉排序树的查找方式和
- 小明用10元钱正好买了20分和50分的邮
- 已知非齐次递归方程:,其中,b、c是常数
- 动态规划算法的基本要素是()和()。
- 数据结构与算法中,快速排序的特性描述正确
- Hanoi塔问题如下图所示。现要求将塔座
- 数据结构与算法里,完数N的因子一定包括1
- 简述分治法的基本步骤。
- 设有n个顾客同时等待一项服务,顾客i需要
- 在最接近点对问题中,用一条垂直线L:x=
- 数据结构与算法里,鸡兔同笼也是算法的一种
- 一个人有一捆草,一只羊,一头老虎。他想把
- break语句可以用于下列那些语法中()
- 下图是由14个“+&rdqu
- 关于冒泡排序的比较次数和排序趟数描述正确
- 数据结构与算法里,装填因子的计算方法为(