1 动态规划的基本方法
1.1 多阶段决策过程及实例
- definition of multi stage decision
- example of multi stage decision problem
- shortest path problem
- machine's work load
high level, output, the condition of a machine.
the decision variable is the number of the machine with two different work load with the goal of achieving biggest output.
1.2 the concept of dynamic program and basic formulations
- the concept of dynamic program
take shortest path as example
the former decision affects later decision, but later decision does not affect former decisions.
adopt the concept of multi stage decisions, the shortest problem can be stated as 在各个阶段选取一个
恰当的决策, 使由这些决策组成的一个决策序列所决定的一条路线, 其总路程最短。(at each stage, we made a decision, and for all stages, we get a decision sequence, the sequence make the shortest path) - how to solve this problem?
we can use the algorithm/method of dynamic program.
1.2.1 . the basic concept of dynamic program
- stage
a time/spatial period - status (input variable)
statistic parameters at the beginning or end of a stage.
these parameters called status variables.
the decisions made only based on the adjust up flow parameters. 这个性质称为无后效性( 即马尔科夫性)。
如果状态的某种规定方式可能导致不满足无后效性, 应适当地改变状态的规定方法, 达到能使它满足无后效性的要求。 - decisions (output variable)
make decisions and come into next stage
the decisions called decision variables
they are the functions of status variables
the decision variables have a feasible set. - strategy
decision sequence
the kth sub-process: the following stages start from kth stage
the kth sub-decision sequence
the feasible decision sequence set and optimal decision sequence - stage moving function
an action/movement.
the function determine the K+1th status
the input of the function is the Kth status variables and Kth decision variables - objective function
the objective function is separable and 满足递推关系
Condition of objective function in dynamic program
1.2.2 the basic thoughts and functions
- take shortest path searching as example.
- dynamic programming start searching from end to head.
- 写出基本的递推关系式和恰当的边界条件( 简言之为基本方程)。
- 要做到这一点, 必须先将问题的过程分成几个相互联系的阶段, 恰当地选取状态变量和决策变量及定义最优值函数, 从而把一个大问题化成一族同类型的子问题, 然后逐个求解。
- 即从边界条件开始, 逐段递推寻优,** 在每一个子问题的求解中, 均利用了它前面的子问题的最优化结果**, 依次进行, 最后一个子问题所得的最优解, 就是整个问题的最优解。
- 每段决策的选取是从全局来考虑的, 与该段的最优选择答案一般是不同
1.2.3 动态规划的最优性原理和最优性定理
how to use dynamic program to solve shortest path problem?
the dynamic approach solves general problems, like shortest path, TSP, and so on. In this sense, it is an algorithm.
the problems do not have to be time-dependent.
