组合优化问题简约与算法推演
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61105073, 60773054); 科技部国际科学技术合作项目(2008DFA11940)


Combinatorial Optimization Problem Reduction and Algorithm Derivation
Author:
Affiliation:

Fund Project:

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

    针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.

    Abstract:

    A unified algebraic model is used to represent optimization problems, which uses a transformational approach that starts from an initial problem specification and reduces it into sub-problems with less complexity. The model then constructs the problem reduction graph (PRG) describing the recurrence relations between the problem, and derives an algorithm with its correctness proof hand-in-hand. A prototype system that implements the formal algorithm development process mechanically is also designed. This approach significantly improves the automation of algorithmic program design and helps to understand inherent characteristics of the algorithms.

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

郑宇军,薛锦云,凌海风.组合优化问题简约与算法推演.软件学报,2011,22(9):1985-1993

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

京公网安备 11040202500063号