立体堆与分枝界限算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

本文研究得到教育部博士点基金(No.9703825)资助.


Cubeheap and Branch-and-Bound Algorithms
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.

    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.

    参考文献
    相似文献
    引证文献
引用本文

武继刚,陈国良,吴明.立体堆与分枝界限算法.软件学报,2000,11(7):984-989

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1999-04-01
  • 最后修改日期:1999-06-21
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号