优化路问题的代数方法——论动态规划(Ⅱ)

An Algebraic Method for Optimum Path Problems -On Dynamic Programming (II)

本文用同一思路求解多阶段有向图中三种优化路问题:最优路、N阶最优路及多指标Pareto优化路问题,它们都服从嘉量原理,都用同一个代数公式表达它们的嘉量,并可在同一种表格中进行计算,只是所在半域不同,以本文的方法讨论动态规划中一些离散决定型典型应用问题,其提法、建模思路以及求解过程都有可观的扩大与改善。

This paper gives an identical idea for solving some optimization problems in multistage digraphs including ordinary optimum path,optimum path of the N-th order and multi-objective Pareto optimum path. They all obey the jar-metric principle. The jar-metrics of these problems can be expressed by the same algebraic formula and calculated in an identical tableau form. The only difference lies on different semi-fields. Applying the idea cited to various well-known typical applications of discrete dynamic programming, the formulation, the idea for model building and the process for computation are improved and enlarged considerably.