徐连诚《计算机算法设计与分析》第六章 分支限界法.docx

徐连诚计算机算法设计与分析第六章 分支限界法 徐连诚计算机算法设计与分析第六章 分支限界法 算法设计与分析山东师范高校信息科学与工程学院软件工程讨论所 徐连诚 E-Mail:lchxu 2021年12月4日 徐连诚计算机算法设计与分析第六章 分支限界法 第六章 分支限界法 学近平要点 理解分支限界法的剪枝搜索策略。 把握分支限界法的算法框架1. 队列式(FIFO)分支限界法 2. 优先队列式分支限界法 通过应用范例学近平分支限界法的设计策略。1. 单源最短路径问题 2. 装载问题； 3. 布线问题 4. 0-1背包问题； 5. 最大团问题； 6. 旅行售货员问题 7. 电路板排列问题 8. 批处理作业调度问题2 徐连诚计算机算法设计与分析第六章 分支限界法 引言 分支限界法类似于回溯法，也是一种在问题 的解空间树T中搜索问题解的算法。 分支限界法与回溯法的求解目标不同： 回溯法是找出满足约束条件的全部解 分支限界宣誓找出