摘要
为了基于动态规划法设计求约束最优化问题(COPs)最优解的迭代算法,在避免使用"标记函数"和递归算法的前提下提出了两种求解模式,给出了设计求COPs最优解的迭代算法一般方法,并利用两个典型优化问题-最长公共子序列问题和矩阵链乘法问题,阐明了如何利用两种求解模式设计求COPs最优解的简捷迭代算法.
In order to design iterative algorithm for solving optimal solutions of optimization problems based on dynamic programming, we analyses two cases for structuring the optimal solution without ＂marking function＂ and recursive algorithm, and give a general method to directly design iterative algorithm for every case. According to the method, we give a variety of iterative algorithms for solving optimal solutions of the LCS problem and MCM problem respectively.
出处
《数学的实践与认识》
北大核心
2016年第6期173-180,共8页
Mathematics in Practice and Theory
基金
国家自然科学基金(11471097)
河北省高等学校科研基金(Z2013110)
关键词
动态规划
最优性原理
最长公共子序列问题
矩阵链乘法问题
dynamic programming
principle of optimality
longest common subsequence problem
matrix chain multiplication problem
