DYNAMIC-PROGRAMMING IS OPTIMAL FOR NON-SERIAL OPTIMIZATION PROBLEMS

作     者：ROSENTHAL, A 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1982年第11卷第1期

页      面：47-59页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：nonserial dynamic programming optimal algorithms lower bound exponential time comparision algorithms perfect elimination graph decomposition complexity dynamic programming 

摘      要：We consider discrete optimization problems in which the only exploitable feature of the objective function is a limited form of decomposability. “Nonoverlapping comparison algorithms are defined as a model of procedures which decompose the problem and apply Bellman’s principle of optimality. Nonserial dynamic programming (DP), a simple elimination procedure, is shown to be optimal among all nonoverlapping comparison algorithms, including nondeterministic algorithms. These results can give an exponential lower bound on the shortest admissible proof that a solution is optimal. Furthermore, if part of the search space is ruled out, a subset of the comparisons made by DP optimally searches the remainder. We suggest that the running time of DP is a useful measure of the “interaction complexity of a problem, and that because of its simplicity DP is of practical as well as theoretical interest.