软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2011年
9期
1985-1993
,共9页
组合优化问题%问题简约%算法推演%PAR(partition-and-recur)%正确性证明
組閤優化問題%問題簡約%算法推縯%PAR(partition-and-recur)%正確性證明
조합우화문제%문제간약%산법추연%PAR(partition-and-recur)%정학성증명
针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.
針對組閤優化類問題定義瞭代數結構模型,從問題的形式規約齣髮,通過一階謂詞和量詞縯算將問題逐步簡約為搜索空間更小、複雜度更低的子問題,根據問題的簡約關繫推導齣求解算法,併在構造算法的同時也證明瞭算法的正確性.開髮瞭原型繫統以支持上述形式化的開髮過程.這種算法推縯技術能夠顯著提高算法程序設計的自動化水平,而問題簡約的思想也更有利于對算法本質特徵的理解.
침대조합우화류문제정의료대수결구모형,종문제적형식규약출발,통과일계위사화량사연산장문제축보간약위수색공간경소、복잡도경저적자문제,근거문제적간약관계추도출구해산법,병재구조산법적동시야증명료산법적정학성.개발료원형계통이지지상술형식화적개발과정.저충산법추연기술능구현저제고산법정서설계적자동화수평,이문제간약적사상야경유리우대산법본질특정적리해.
