主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
郑宇军,薛锦云,凌海风.组合优化问题简约与算法推演.软件学报,2011,22(9):1985-1993
组合优化问题简约与算法推演
Combinatorial Optimization Problem Reduction and Algorithm Derivation
投稿时间:2009-09-25  修订日期:2010-09-06
DOI:10.3724/SP.J.1001.2011.03948
中文关键词:  组合优化问题  问题简约  算法推演  PAR(partition-and-recur)  正确性证明
英文关键词:combinatorial optimization problem  problem reduction  algorithm derivation  PAR (partition-andrecur)  correctness proof
基金项目:国家自然科学基金(61105073, 60773054); 科技部国际科学技术合作项目(2008DFA11940)
作者单位E-mail
郑宇军 中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190
江西师范大学 江西省高性能计算重点实验室,江西 南昌 330027 
yujun.zheng@computer.org 
薛锦云 中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190
江西师范大学 江西省高性能计算重点实验室,江西 南昌 330027 
 
凌海风 南京大学 管理工程学院,江苏 南京 210093  
摘要点击次数: 4600
全文下载次数: 6676
中文摘要:
      针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利