写在前面
我们先提出与"回路"有关的几个问题.
problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.
problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.
对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答.
problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.
problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.
对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答.