| 组合优化问题简约与算法推演 |
| |
| 引用本文： | 郑宇军,薛锦云,凌海风.组合优化问题简约与算法推演[J].软件学报,2011,22(9):1985-1993. |
| |
| 作者姓名： | 郑宇军 薛锦云 凌海风 |
| |
| 作者单位： | 1. 中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190;江西师范大学 江西省高性能计算重点实验室,江西 南昌 330027
2. 南京大学 管理工程学院,江苏 南京,210093 |
| |
| 基金项目： | 国家自然科学基金(61105073,60773054); 科技部国际科学技术合作项目(2008DFA11940) |
| |
| 摘 要： | 针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也...
|
| 关 键 词： | 组合优化问题 问题简约 算法推演 PAR(partition-and-recur) 正确性证明 |
| 收稿时间： | 2009/9/25 0:00:00 |
| 修稿时间： | 9/6/2010 12:00:00 AM |
Combinatorial Optimization Problem Reduction and Algorithm Derivation |
| |
| ZHENG Yu-Jun,XUE Jin-Yun and LING Hai-Feng.Combinatorial Optimization Problem Reduction and Algorithm Derivation[J].Journal of Software,2011,22(9):1985-1993. |
| |
| Authors: | ZHENG Yu-Jun XUE Jin-Yun and LING Hai-Feng |
| |
| Affiliation: | ZHENG Yu-Jun1,2,XUE Jin-Yun1,LING Hai-Feng3 1(The State Key Laboratory of Computer Science,Institute of Software,The Chinese Academy of Sciences,Beijing 100190,China) 2(Provincial Key Laboratory of High Performance Computing,Jiangxi Normal University,Nanchang 330027,China) 3(School of Management and Engineering,Nanjing University,Nanjing 210093,China) |
| |
| 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 ... |
| |
| Keywords: | combinatorial optimization problem problem reduction algorithm derivation PAR(partition-and-recur) correctness proof |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
