算法设计与分析 清华大学出版社 (第二版)PPT课件
9.1.1解空间树的动态搜索(2) 分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up]。然后,按照广度优先策略遍历问题的解空间树,在分支结点上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值,如果某孩子结点的目标函数可能取得的值超出目标函数的界,则将其丢弃,因为从这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表(以下简称表PT)中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。
Page 4
第9章分支限界法
2014-6-16

第9章 分支限界法 9.1 概述 9.2 图问题中的分支限界法 9.3 组合问题中的分支限界法 9.1 概述 9.1.1 解空间树的动态搜索(2) 9.1.2 分支限界法的...
第9章 分支限界法 9.1 概述 9.2 图问题中的分支限界法 9.3 组合问题中的分支限界法 9.4 实验项目——电路布线问题 9.1 概述 9.1.1 解空间树的动态...
第9章 分支限界法_数学_自然科学_专业资料。清华大学出版社 算法设计与分析 第9章 分支限界法 9.1 概述 9.2 图问题中的分支限界法 9.3 组合问题中的分支...
第9章 分支限界法 ? 学习要点: ? 理解分支限界法的剪枝搜索策略 ? 掌握分支限界法的算法框架 ? ? 队列式(FIFO)分支限界法优先队列式分支限界法 ? 通过应用...
第9章 分支限界法 9.1 概述 9.2 图问题中的分支限界法 9.3 组合问题中的分支限界法 9.1 概述 9.1.1 解空间树的动态搜索(2) 9.1.2 分支限界法的...
第9章 分支限界法_工学_高等教育_教育专区。第九章 1 2 3 4 分支限界法 概述图问题中的分支限界法 组合问题中的分支限界法 小结 分支限界法—概述 ?分支...
第9章 分支限界法(完) 暂无评价 57页 免费 分支限界法 23页 1下载券 第...(2)求解目标: 回溯法的求解目标是找出解空间树中满足约束条件的所有解或最优 ...
分支限界法 23页 2财富值 分支限界法 78页 免费 分支限界法 114页 5财富值 第9章 分支限界法 57页 免费 第6章 分支限界法 69页 免费 第六章分支限界法...
分支限界法中有两个要点: (1)评价函数的构造; 评价函数的构造; 评价函数的构造 (2)搜索路径的构造。 搜索路径的构造。 搜索路径的构造 9 Algorithm Design & ...
热门文档