noip动态规划1.ppt
《noip动态规划1.ppt》由会员分享,可在线阅读,更多相关《noip动态规划1.ppt(39页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、noip动态规划1 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望动态规划动态规划与递归程序相类,将对问题求解分解为对子问与递归程序相类,将对问题求解分解为对子问题求解;不同之处在于把子问题的解存起来,题求解;不同之处在于把子问题的解存起来,用空间换时间。用空间换时间。例:例:Fibonacci数数uF(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);u递归递归:F(n-1)和和F(n-2)分别求到底一次分别求到底一次u动态规划:用数组将前动态规划:
2、用数组将前n-1个数存起来,每次只用个数存起来,每次只用一个加法一个加法Fn=Fn-1+Fn-2即可。即可。例最短路径问题。下图中给出一个地图,地图中每个顶点代表例最短路径问题。下图中给出一个地图,地图中每个顶点代表一个城市,两个城市之间的连线表示道路,连线上的数值代表道路一个城市,两个城市之间的连线表示道路,连线上的数值代表道路的长度。现在,想从城市的长度。现在,想从城市A到城市到城市E,怎样走路程最短,最短路程,怎样走路程最短,最短路程的长度是多少?的长度是多少?现在,我们想从城市现在,我们想从城市A到达城市到达城市E。怎样走才能使得路径最短,最。怎样走才能使得路径最短,最短路径的长度是多
3、少?短路径的长度是多少?设:设:Disx为城市为城市x到城市到城市E的最短路径长度(的最短路径长度(x表示任意一个城市)表示任意一个城市);Mapi,j表示表示i,j两个城市间的距离,若两个城市间的距离,若mapi,j=0,则两个城市不通。,则两个城市不通。我们可以使用回溯来计算我们可以使用回溯来计算Disx:vars:未访问的城市聚合;未访问的城市聚合;functionsearch(who):integer;求城市求城市Who与城市与城市E的最短距离的最短距离Vari,j,min:integer;beginifwho=Ethensearch:=0elsebeginmin:=maxint;fo
4、ri取遍所有城市取遍所有城市doif(mapwho,i0)and(iins)thenbegins:=s-i;城市城市i已访问已访问j:=mapwho,i+search(i);计算城市计算城市E至城市至城市Who的路径长度的路径长度s:=s+i;恢复城市恢复城市i未访问状态未访问状态ifjminthenmin:=j;若城市若城市E至城市至城市Who的路径长度为目前最短,则记下的路径长度为目前最短,则记下end;search:=min;返回城市返回城市E至城市的最短路径长度至城市的最短路径长度end;begins:=所有城市;所有城市;disa:=search(a);计算城市计算城市A城市城市E的
5、最短路径长度的最短路径长度writeln(dista);end.这个程序的效率如何呢?我们可以看到,每次除了已经访问过的城市外,这个程序的效率如何呢?我们可以看到,每次除了已经访问过的城市外,其他城市都要,所以时间复杂度为其他城市都要,所以时间复杂度为W(n!),这是一个,这是一个“指数级指数级”的算法。的算法。那么还有没有效率更高的解题方法呢?那么还有没有效率更高的解题方法呢?首先,我们来观察上述算法。在求首先,我们来观察上述算法。在求B1到到E的最短路径的时候,先求出从的最短路径的时候,先求出从C2到到E的最短路径;而在求的最短路径;而在求B2到到E的最短路径的时候,又求了一遍从的最短路径
6、的时候,又求了一遍从C2到到E的最短路径。也就是说,从的最短路径。也就是说,从C2到到E的最短路径求了两遍。两样可以发现,的最短路径求了两遍。两样可以发现,在求从在求从C1、C2到到E的最短路径的过程中,从的最短路径的过程中,从D1到到E的最短路径也被求了两的最短路径也被求了两遍。而在整个过程中,从遍。而在整个过程中,从D1到到E的最短路径被求了四遍,这是多么大的一的最短路径被求了四遍,这是多么大的一个浪费啊!如果在求解的过程中,同时将求得的最短路径的距离个浪费啊!如果在求解的过程中,同时将求得的最短路径的距离“记录在记录在案案”,以便将来随时调用,则可以避免这种重复计算。至此,一个新的思,以
7、便将来随时调用,则可以避免这种重复计算。至此,一个新的思路产生了,即由后往前依次推出每个路产生了,即由后往前依次推出每个Dis值,直到推出值,直到推出DisA为止为止。阶段的划分具有如下性质:阶段的划分具有如下性质:阶段阶段i的取值只与阶段的取值只与阶段i+1有关,阶段有关,阶段i+1的取值只对阶段的取值只对阶段i的取值的取值产生影响;产生影响;每个阶段的顺序是确定的,不可以调换任两个阶段的顺序。每个阶段的顺序是确定的,不可以调换任两个阶段的顺序。ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0我们从阶段我们从阶段4的城市的城市E出发,按照阶段的顺序倒推至阶段出发,按照阶段的顺序倒
8、推至阶段0的城市的城市a。在求解的各个阶段,利用了在求解的各个阶段,利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系diskx=dis4E=0k=4k=4,3 3,0 0,其中,其中disdiskkxx指指k k阶段的城市阶段的城市x x。ED3D1D2C1C3C2AB3B2B15426346561222332340ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0我们从阶段我们从阶段4的城市的城市E出发,按照阶段的顺序倒推至阶段出发,按照阶段的顺序倒推至阶段0的城市的城市a。在求解的各个阶段,利用了在求解的各个阶段,利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间
9、的如下关系diskx=dis4E=0k=4k=4,3 3,0 0,其中,其中disdiskkxx指指k k阶段的城市阶段的城市x x。ED3D1D2C1C3C2AB3B2B15426346561222332340234ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0我们从阶段我们从阶段4的城市的城市E出发,按照阶段的顺序倒推至阶段出发,按照阶段的顺序倒推至阶段0的城市的城市a。在求解的各个阶段,利用了在求解的各个阶段,利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系diskx=dis4E=0k=4k=4,3 3,0 0,其中,其中disdiskkxx指指k k阶段的城
10、市阶段的城市x x。23ED3D1D2C1C3C2AB3B2B154263465612223323403446ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0我们从阶段我们从阶段4的城市的城市E出发,按照阶段的顺序倒推至阶段出发,按照阶段的顺序倒推至阶段0的城市的城市a。在求解的各个阶段,利用了在求解的各个阶段,利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系diskx=dis4E=0k=4k=4,3 3,0 0,其中,其中disdiskkxx指指k k阶段的城市阶段的城市x x。ED3D1D2C1C3C2AB3B2B1542634656122233234023434
11、6778ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0我们从阶段我们从阶段4的城市的城市E出发,按照阶段的顺序倒推至阶段出发,按照阶段的顺序倒推至阶段0的城市的城市a。在求解的各个阶段,利用了在求解的各个阶段,利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系diskx=dis4E=0k=4k=4,3 3,0 0,其中,其中disdiskkxx指指k k阶段的城市阶段的城市x x。ED3D1D2C1C3C2AB3B2B1542634656122233234023434677810ABCDE阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0由此得出程序由此得出程序:di
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- noip 动态 规划
限制150内