组合优化问题简约与算法推演

• 作者: 凌海风 薛锦云 郑宇军
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 组合优化问题 问题简约 算法推演 PAR(partition-and-recur) 正确性证明
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 1985-1993
• 分类号: TP301
• 字数: 7421字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03948

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	薛锦云	中国科学院软件研究所计算机科学国家重点实验室	77	745	15.0	23.0
5	凌海风	南京大学管理工程学院	5	73	4.0	5.0
6	郑宇军	中国科学院软件研究所计算机科学国家重点实验室	13	51	4.0	6.0