| 摘要: |
| 分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施. |
| 关键词: 分枝界限,组合搜索,算法,计算复杂度. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到教育部博士点基金(No.9703825)资助. |
|
| Cubeheap and Branch-and-Bound Algorithms |
|
WU Ji-gang,CHEN Guo-liang,WU Ming
|
| Abstract: |
| Branch-and-Bound (B&B) algorithm is one of the fundamental methods for combinatorial optimization problems. The running time is dominated by the data structure used to implement B&B algorithm for the given problem and the related branching strategy. In this paper, the data structure called Cubeheap and the related algorithms (INSERT and DELETE) are discussed. The lower bound Ω(m+hlogh) of the running time for general B&B algorithm is proposed by constructing the mapping between the B&B procedure and the sorting procedure, where m is the number of the evaluated nodes and h is the number of the expanded nodes. According to the lower bound, Cubeheap is the near-optimal data structure to implement the general B&B algorithm. The experimental results for a concrete combinatorial optimization problem, Job-assignment, are obtained by running the B&B algorithm with the Cubeheap. The method to improve the balance of the Cubeheap is also proposed. |
| Key words: Branch-and-Bound, combinatorial search, algorithm, computational complexity. |
