ACM课件-动态规划专用课件.pptVIP

动态规划(1) （Dynamic programming） 先热身一下—— 海盗分金问题 5名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。 这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下一名最厉害的海盗又重复上述过程。 所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。 所有的海盗都是聪明绝顶的，而且知道其他的海盗也是聪明绝顶的。 此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。 这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。 最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？ 我们按照这些海盗的威望值来给他们编号。最怯懦的海盗为1，最厉害的海盗编号为5。编号为5的海盗会提出什么分配方案呢？ 如果从游戏的开头出发进行分析，那是走不了多远的。 其原因在于，所有的战略决策都是要确定：“如果我这样做，那么下一个人会怎样做？” 因此在你以下海盗所做的决定对你来说是重要的，而在你之前的海盗所做的决定并不重要，因为你反正对这些决定也无能为力了。 最厉害的5号海盗需要知道其他4名海盗是怎么想的.......好难猜！ 对4号海盗来说，如果5号海盗被扔进海里喂鲨鱼了，他只需要猜透其余3名海盗的算盘。 对3号海盗而言，他只须猜透1号和2号海盗 对2号海盗而言，他只须猜透1号海盗 那我们就倒过来，由易到难 我们的出发点应当是游戏进行到只剩两名海盗——即1号和2号——的时候。 这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。 3号海盗的分配方案：3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。 4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。 5号海盗的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1号。 总结 分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。 10.1 什么是动态规划 1、最短路径问题 2、数塔问题 如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。 除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。 很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短。 故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解决这个问题呢？ 决策过程： （1）由目标状态E向前推，可以分成四个阶段，即四个子问题。 D?E C?E B?E A?E （2）策略：每个阶段到E的最省费用为本阶段的决策路径。 （3）D1，D2是第一次输入的结点。他们到E都只有一种费用： f(D1)=5 f(D2)=2 （4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。 f(C1) =min{C1D1+ f(D1) ，C1D2+ f(D2)}。 计算结果是f(C1)= C1D1+ f(D1)=8 （D1) 同理C2的决策路径计算结果是C2+D2+ E , f(C2)=7 。同理C3的决策路径计算结果是C3+D2+E，f(C3)=10。 （5）第三次输入结点为B1，B2，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2的决策路径为如下情况。Bl: B1C1 费用 f(B1)=5+8=13， B2:B2C1 费用 f(B2)= 6+8=14， （6）第四次输入结点为A，决策输出结点可能为B1，B2。 同理可得决策路径为A：AB2，费用5+14=19 此时才正式确定每个子问