文摘
英文文摘
图表目录
第一章绪论
§1.1研究背景与发展现状
§1.1.1串行分枝界限算法
§1.1.2并行分枝界限算法
§1.1.3优先队列及算法
§1.2研究内容与全文概要
§1.3本章小结
第二章基本概念与算法
§2.1并行计算基本概念
§2.1.1并行计算模型
§2.1.2并行算法的复杂度
§2.1.3并行算法的性能评价
§2.2基本组合算法
§2.2.1 回溯法
§2.2.2分枝界限法
§2.2.3动态规划
§2.3本章小结
第三章立体堆与分枝界限算法
§3.1立体堆及算法
§3.2分枝界限算法及复杂度下界
§3.3 体堆在分枝界限算法中的应用
§3.4实验结果
§3.5本章小结
第四章一种混合分枝界限算法及其性能分析
§4.1数据结构
§4.2混合策略与算法
§4.3并行混合算法
§4.4实验结果
§4.5本章小结
第五章几乎最快的并行分枝界限算法
§5.1预备算法
§5.2第一类并行算法
§5.2.1算法设计
§5.2.2算法分析
§5.3第二类并行算法
§5.3.1算法设计
§5.3.2算法分析
§5.4实验结果
§5.5本章小结
第六章渐近最优的并行分枝界限算法
§6.1优先队列的PRAM-EREW算法
§6.1.1最小路径堆-MH
§6.1.2并行插入
§6.1.3并行删除
§6.1.4并行建堆
§6.2并行分枝界限算法
§6.2.1数据结构
§6.2.2并行算法设计
§6.3运行时间理论分析
§6.4实验结果
§6.5本章小结
第七章分布式存贮的一般并行分枝界限算法
§7.1 计算复杂度下界
§7.2一般并行分枝界限算法
§7.2.1选择子问题
§7.2.2扩展前p个结点
§7.2.3 算法
§7.3并行算法复杂度分析
§7.3.1通讯复杂度
§7.3.2 计算复杂度
§7.4实验结果
§7.5本章小结
第八章0-r背包问题的分枝界限算法
§8.1引言
§8.2归约方法与算法结构
§8.3寻找中断解
§8.4分枝界限算法
§8.5扩展所需的核
§8.5.1排序
§8.6启发解与主算法
§8.7实验结果
§8.8本章小结
第九章收缩背包问题的并行分枝界限算法
§9.1引言
§9.2问题的分解
§9.3求解子问题的分枝界限算法
§9.3.1寻找中断项和中断解
§9.3.2分枝界限搜索
§9.4求解CKP的主算法
§9.5并行分枝界限算法
§9.6实验结果
§9.7本章小结
第十章总结与展望
参考文献
在读博士期间发表和已录用的论文
致谢