动态规划的阶段:什么意思
为能应用动态规划方法,首先必须根据实际问题所处的时间空间或其他条件,把所研究的问题恰当地划分成若干个相互联系的阶段,以便能按一定的次序去求解。常用字母 K 表示阶段变量。
例1-1 设某企业要把一批货物从 A 点运到 E 点出售,交通网络如图1-1所示,两点之间连线上的数字表示两点间的距离,问应选择什么路线,可使总距离最短?
如在例1-1中,从 A 到 E 可以划分为4个阶段,用 K =1,2,3,4来表示。第一阶段从 A 到 B 1 、 B 2 ,有2条交通线( A , B 1 )和( A , B 2 );第二阶段从 B 1 、 B 2 到 C 1 、 C 2 、 C 3 ,有6条交通线( B 1 , C 1 )( B 2 , C 2 ) ( B 3 , C 3 )和( B 2 , C 1 ) ( B 2 , C 2 ) ( B 2 , C 3 ),以此类推。