基于最大半环的DP问题函数式建模与验证

The Functional Modeling and Verification of Dynamic Programming Problems Based on Max_Semiring

针对在DP问题算法的设计和推导中缺乏对DP问题函数式建模算法与验证的细致研究,该文首先通过深入分析最大半环与DP类问题递推关系式的对应关系,找到满足最大半环性质的一类DP问题,使用最大半环对该类DP问题进行函数式建模;然后将实现的基于最大半环的函数式建模算法与Wimmer定义的递归函数结果进行等价性验证,从而保证了函数式建模算法的正确性;最后通过对lcs问题案例分析,验证了该方法的可行性和有效性.

Functional modeling algorithms and verification frameworks for DP issues are not thoroughly studied in the literature,which mostly concentrates on the design and derivation of algorithms for DP problems.Firstly,the relationship between the maximum half-loop and the recursive equation of DP issues is examined,a class of DP problems that have the maximal half-loop property are identified,and then this class of DP problems using the maximal half-loop are functionally described.Secondly,in order to confirm that the functional modeling algorithm used in this study is valid,the output of Wimmer′s recursive function with the maximum half-loop-based functional mode-ling technique are made equivalence checking.Finally,case examples of lcs difficulties illustrate the method′s viability and efficacy.