算法 动态规划

Oudasheng 2019-12-27

1. 多段图的最短路径问题

算法 动态规划

什么是多段图?

  • 多段图是一个有向、无环、带权 图。
  • 有且仅有一个起始结点(原点source) 和 一个终止结点(汇点target)。
  • 它有n个阶段,每个阶段由特定的几个结点构成。
  • 每个结点的所有结点都只能指向下一个相邻的阶段,阶段之间不能越界。

算法 动态规划

对其使用动态规划法:

阶段:将图中的顶点划分5个阶段,k

状态:每个阶段有几种供选择的点s

决策:当前状态应在前一个状态的基础上获得。决策需要满足规划方程

规划方程:f(k)表示状态k到终点状态的最短距离。

初始条件:f(k)=0;

方程:f(k-1)=min{f(k)+W(k-1,k)}其中W(k-1,k)表示状态k-1到状态k的距离【向前处理】

相关推荐