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

摘要：

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

关键词：组合优化问题、问题简约、算法推演、PAR(partition-and-recur)、正确性证明

所属期刊栏目：22

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2012-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1985-1993