北航计算机研究生课程算法设计与分析

1、一、 解：设第k月的需求量为Nk(k=1,2,3,4)状态变量Xk:第k月初的库存量，X1=X5=0 0<Xkw Nk+N4决策变量 Uk：第 k 月的生产量，max0, Nk-Xk < Uk< min6 , Nk+N4 - Xk状态转移方程：兀+1 = Uk + Xk - Nk第 k 月的成本 Vk = *(Xk - Nk)Uk=03 + Uk + *(Uk + Xk - Nk) Uk工 0设Fk(Xk)是由第k月初的库存量Xk开始到第4月份结束这段时间的最优成本则 Fk(Xk) = minVk + F k+i(X k+i)1< k< 4=mi n 3 + Uk

2、 + *(Uk + Xk - Nk) + Fk+1(Uk + Xk - Nk) Uk 工 0mi n *(Xk - Nk) + Fk+1(Xk - Nk) Uk=0F5(X5)=0四个月内的最优成本为R(X1)=F1(0)详细计算步骤如下：(1) k=4 时0W X4W 4, max0, 4 - X4 w U4W min6 , 4-X4X4U4X5V4F5(X5)V4 + F5(X5)0407°7=%0)130606=%1)220505=R(2)310404=F4(3)400000=F1 即对于状态X4的每个取值，都有唯一确定的决策变量 U4使得F4（X4）最优(2) k=3 时0w

3、X3<6, max0, 2 - X3 w U3<min6 , 6-X3X3U3X4V3Fg)V3 + F4(X4)0205712316428513536411011= Fa(0)110471121A3275124345410°10=Fa(1)200077=F3 11622651133444909301A二3)1255102343488402156=%4）1342471 075034=F3（5）1466604302=Fa（6）（3） k=2 时0<X2W9, max0, 3 - X2 < U2<min6 , 9-X2X2U2X3V2F3（X3）V2 + F

4、 3（X3）030611174110529716=F2（0）6317120511163110428715=F2（1）53166411617210411152110327714=F2 （2）43155410616651730001111= F2（3）111022671333144496155516661221440110=F2（4）125713231334861445155611213502178=F2(5)131224761335144610p126038=F2(6)1466122513369211704268=F2(7)15122682108058=B(8)167A9906325=F2(9)

5、(4) k=1 时X1=0, max0, 2 < U1< min6 , 11X1U1X2V1F2(X2)V1 + F2(X2)0205213115428142253M1=F1(0)6411由以上计算可得，4个月的总最优成本为Fi(0)=(千元)从k=1回溯，可得最优结果中各阶段的状态变量 Xk和决策变量Uk如下表:月份k产量Uk月初库存量Xk需求量Nk每月成本Vk15022033036021140440二、解：1、变量设定阶段k :已遍历过k个结点，k=1,26,7。K=1表示刚从V1出发，k=7表示已回到起点V1状态变量Xk=（i , Sk）:已遍历k个结点，当前位于i结点，还未

6、遍历的结点集 合为 Sk。则 X仁（1, 2,3,4,5,6）, X6=（i，）,X7=（1,）决策变量Uk=（i , j）：已遍历k个结点，当前位于i结点，下一个结点选择j。 状态转移方程：X+i = T（Xk , Uk） = （j , Sk-j）第k阶段的指标函数Vk = Di,j。最优指标函数Fk（Xk） = Fk（i , Sk）:已遍历k个结点，当前从i结点出发，访 问Sk中的结点一次且仅一次，最后返回起点V1的最短距离。则 Fk（i , Sk） = min Di,j + F k+i（j , Sk-j） 1< k< 6F 7（X7） = F 7（1，）=02、分析:(1)

7、k=6 时，F6(i，)=minDi,1 + F7(X7) = Di,1i=2,3,4,5,6X6=(i，)U6=(i , j)X7=(1,)V6=Di,jF7(1，)V6 + F 7(X7)（2，）(2 , 1)（1，）1201 12=F6(2,)（3，）(3 , 1)（1，）23023=F6(3,)（4，）(4 , 1)（1，）34034=F6(4,)（5，）(5 , 1)（1，）45045=F6(5,)1（6，）(6 , 1)（1，）56056=F6(6,)即k=6时，对于每一种状态X6,都有唯一一的决策U6,(2) k=5 时,F5(i , S5)=minDi,j + F6(j，)i=

8、2,3,4,5,6X5=(i,S5)U5=(i,j)X6=(j,)V5=Di,jF6(j,)V5 + F6(X6)(2,6(2,6)（6，）2156r 77=F5(2,6) 1(2,5(2,5)（5，）254570=F5(2,5)(2,4(2,4)（4，）303464=F5(2,4)(2,3(2,3)（3，）1823仁 F5(2,3) 1(3,6)(3,6)（6，）15567仁 F5(3,6)(3,5)(3,5)（5，）104555=F5(3,5)(3,4)(3,4)（4，）53439=F5(3,4):(3,2)(3,2)（2，）19123仁 F5(3,2)(4,6)(4,6)（6，）16 :

9、56r 72=F5(4,6)(4,5)(4,5)（5，）84553=F5(4,5)(4,3)(4,3)（3，）42327=F5(4,3)(4,2)(4,2)（2，）32:12p 44=F5(4,2)(5,6)(5,6)（6，）185674=F5(5,6)(5,4)(5,4)（4，）103444=F5(5,4)(5,3)(5,3)（3，）112334=F5(5,3):(5,2)(5,2)（2，）271239=F5(5,2)(6,5)(6,5)（5，）124557=F5(6,5)(6,4)(6,4)（4，）2034:54=F5(6,4)(6,3)(6,3)（3，）162339=F5(6,3)(6,

10、2)(6,2)（2，）221234=F5(6,2)即k=时，对于每一种状态X5,都有唯一决策U5(3) k=4 时，F4(i,S4) = min(Di,j + F5(j,S5) )i=2,3,4,5,6X4=(i,S4)U4=(i,j)X5=(j,S5)V4=Di,jF5(j,S5)V4 + F5(j,S5)(2,3,4)(2,3)(3,4)183957=F4(2,3,4):(2,4)(4,3)302757=F4(2,3,4)(2,4,5)(2,4)(4,5)305383(2,5)(5,4)254469=F4(2,4,5):(2,5,6)(2,5)(5,6)257499(2,6)(6,5)21

11、5778=F4(2,5,6)(2,3,5)(2,3)(3,5)185573(2,5)(5,3)253459=F4(2,3,5)(2,3,6)(2,3)(3,6)187189(2,6)(6,3)213960=F4(2,3,6):(2,4,6)(2,4)(4,6)3072102(2,6)(6,4)215475=F4(2,4,6)(3,2,4)(3,2)(2,4)196483(3,4)(4,2)54449=F4(3,2,4)(3,2,5)(3,2)(2,5)197089(3,5)(5,2)10 3949=F4(3,2,5) 1(3,2,6)(3,2)(2,6)197796(3,6)(6,2)1534

12、49=F4(3,2,6)(3,4,5)(3,4)(4,5)5:5358(3,5)(5,4)104454=F4(3,4,5)(3,4,6)(3,4)(4,6)57277(3,6)(6,4)15:5469=F4(3,4,6)(3,5,6)(3,5)(5,6)107484(3,6)(6,5)155772=F4(3,5,6)(4,2,3)(4,2)(2,3)32:4173(4,3)(3,2)43134=F4(4,2,3)(4,2,5)(4,2)(2,5)3270102(4,5)(5,2)83947=F4(4,2,5)(4,2,6)(4,2)(2,6)3277109(4,6)(6,2)163450=F4

13、(4,2,6)(4,3,5)(4,3)(3,5)4：5559(4,5)(5,3)83442=F4(4,3,5)(4,3,6)(4,3)(3,6)47175(4,6)(6,3)163955=F4(4,3,6)(4,5,6)(4,5)(5,6)87482(4,6)(6,5)165773=F4(4,5,6)(5,2,3)(5,2)(2,3)274168(5,3)(3,2)113142=F4(5,2,3):(5,2,4)(5,2)(2,4)276491(5,4)(4,2)104454=F4(5,2,4)(5,2,6)(5,2)(2,6)2777104(5,6)(6,2)183452=F4(5,2,6)

14、(5,3,4)(5,3)(3,4)113950(5,4)(4,3)102737=F4(5,3,4):(5,3,6)(5,3)(3,6)117182(5,6)(6,3)183957=F4(5,3,6)(5,4,6)(5,4)(4,6)107282(5,6)(6,4)185472=F4(5,4,6)(6,2,3)(6,2)(2,3)224163(6,3)(3,2)163147=F4(6,2,3):(6,2,4)(6,2)(2,4)226486(6,4)(4,2)204464=F4(6,2,4)(6,2,5)(6,2)(2,5)227092(6,5)(5,2)12395仁 F4(6,2,5)(6,3

15、,4)(6,3)(3,4)163955(6,4)(4,3)202747=F4(6,3,4):(6,3,5)(6,3)(3,5)165571(6,5)(5,3)123446=F4(6,3,5)(6,4,5)(6,4)(4,5)205373(6,5)(5,4)124456=F4(6,4,5)(4) k=3 时，F3(i,S3) = minDi,j + F4(j,S4)i=2,3,4,5,6X3=(i,S3)U3=(i,j)X4=(j,S4)V3=Di,jF4(j,S4)V3 + F4(j,S4)(2,3,4,5)(2,3)f(3,4,5)185472(2,4)(4,3,5)304272(2,5)(

16、5,3,4)253762=F3(2,3,4,5)(2,3,4,6)(2,3)f(3,4,6)186987(2,4)(4,3,6)305585(2,6)(6,3,4)214768=F3(2,3,4,6)(2,3,5,6)(2,3)(3,5,6)187290:(2,5)P(5,3,6)255782(2,6)(6,3,5)214667=F3(2,3,5,6)(2,4,5,6)(2,4)(4,5,6)3073103(2,5)P(5,4,6)257297(2,6)(6,4,5)215677=F3(2,4,5,6)(3,2,4,5)(3,2)(2,4,5)196988(3,4)f(4,2,5)54752=

17、F3(3,2,4,5):(3,5)(5,2,4)105464(3,2,4,6)(3,2)(2,4,6)197594(3,4)f(4,2,6)55055=F3(3,2,4,6):(3,6)(6,2,4)156479(3,2,5,6)(3,2)(2,5,6)197897(3,5)f(5,2,6)105262=F3(3,2,5,6):(3,6)(6,2,5)155166(3,4,5,6)(3,4)(4,5,6)57378(3,5)f(5,4,6)107282 :(3,6)f(6,4,5)15567仁F3(3,4,5,6) 丁(4,2,3,5)(4,2)(2,3,5)325991(4,3)f(3,2,

18、5)44953(4,5)(5,2,3)84250=F3(4,2,3,5)(4,2,3,6)(4,2)(2,3,6)326092(4,3)；(3,2,6)44953=F3(4,2,3,6)(4,6)f(6,2,3)164763(4,2,5,6)(4,2)(2,5,6)3278110(4,5)：(5,2,6)85260=F3(4,2,5,6):(4,6)：(6,2,5)165167(4,3,5,6)(4,3)(3,5,6)47276(4,5)：(5,3,6)85765(4,6)f(6,3,5)164662=F3(4,3,5,6) H(5,2,3,4)(5,2)(2,3,4)275784(5,3)F

19、(3,2,4)114960 :(5,4)(4,2,3)103444=F3(5,2,3,4):(5,2,3,6)(5,2)(2,3,6)276087(5,3)F(3,2,6)114960=F3(5,2,3,6):(5,6)P(6,2,3)184765(5,2,4,6)(5,2)(2,4,6)2775102(5,4)(4,2,6)105060=F3(5,2,4,6)(5,6)F(6,2,4)186482(5,3,4,6)(5,3)(3,4,6)116980(5,4)(4,3,6)105565=F3(5,3,4,6)(5,6)P(6,3,4)184765=F3(5,3,4,6)(6,2,3,4)(6

20、,2)(2,3,4)225779(6,3)(3,2,4)164965(6,4)(4,2,3)203454=F3(6,2,3,4)(6,2,3,5)(6,2)(2,3,5)225981(6,3)(3,2,5)164965(6,5)(5,2,3)124254=F3(6,2,3,5)(6,2,4,5)(6,2)(2,4,5)226991(6,4)(4,2,5)204767(6,5)(5,2,4)125466=F3(6,2,4,5):(6,3,4,5)(6,3)(3,4,5)165470(6,4)(4,3,5)204262(6,5)(5,3,4)123749=F3(6,3,4,5)(5) k=2 时，

21、F2(i,S2) = minDi,j + F3(j,S3)i=2,3,4,5,6X2=(i,S2)U2=(i,j)X3=(j,S3)V2=Di,jF3(j,S3)V2 + F3(j,S3)(2,3,4,5,6)(2,3)(3,4,5,6)18：7189(2,4)(4,3,5,6)306292(2,5)(5,3,4,6)256590(2,6)(6,3,4,5)21：4970=F2(2,3,4,5,6)(3,2,4,5,6)(3,2)(2,4,5,6)197796(3,4)(4,2,5,6)56065=F2(3,2,4,5,6)(3,5)(5,2,4,6)10：6070(3,6)(6,2,4,5)

22、156681(4,2,3,5,6)(4,2)(2,3,5,6)326799(4,3)(3,2,5,6)4：6266=F2(4,2,3,5,6)(4,5)(5,2,3,6)86068(4,6)(6,2,3,5)165470(5,2,3,4,6)(5,2)(2,3,4,6)276895(5,3)(3,2,4,6)115566(5,4)(4,2,3,6)105363=F2(5,2,3,4,6)(5,6)(6,2,3,4)185472(6,2,3,4,5)(6,2)(2,3,4,5)226284(6,3)(3,2,4,5)165268(6,4)(4,2,3,5)20；5070(6,5)(5,2,3,4

23、)124456=F2(6,2,3,4,5)(6) k=1 时，F1(1,S1) = minD1,j + F2(j,S2)X仁(1,S1)U1=(1,j)X2=(j,S2)V1= D1,jF2(j,S2)V1 + F2(j,S2)(1,2,3,4,5,6)(1,2)(2,3,4,5,6)10,080=F1(1,2,3,4,5,6)(1,3)(3,2,4,5,6)206585(1,4)(4,2,3,5,6)306696(1,5)(5,2,3,4,6)40：63103(1,6)(6,2,3,4,5)50561063、伪代码和时间复杂度为方便计算，结点编号改为0到5.(1)用一张二维表格F表示F(i,Sk)，行数是n，列数是2n-1(2) 行号表示当前所在的结点 i 。列号对应的五位二进制表示表示 V5,V