动态规划

步骤

• 阶段的确定：根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题
• 状态变量的确定：正确选择状态变量x{k}，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合X{k}
• 决策变量的确定：用u{k}(x{k})表示第k阶段处于状态x{k}时的决策变量，其包含可以作出的所有的下一阶段的状态
• 状态转移方程的确定：x{k+1}=T{k}(x{k},u{k}),k = 1,2,...,n
• 指标及指标函数的确定：是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用V{k,n}(x{k},u{k},x{k+1},...,x{n+1})表示，其中k=1,2,...,n
• 最优值函数和递归方程的确定：
  

最短路线问题

阶段的确定

每个节点为一个阶段，可以分为16个阶段

状态变量的确定

每个节点接下来可选择的下一个节点组成的集为该结点的状态变量

决策变量的确定

状态转移方程的确定

指标及指标函数的确定

最优值函数和递归方程的确定