《noip动态规划》ppt课件

《《noip动态规划》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态程序设计动态规划与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。例：Fibonacci数F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);递归:F(n-1)和F(n-2)分别求到底一次动态规划：用数组将前n-1个数存起来，每次只用一个加法F[n]=F[n-1]+F[n-2]即可。例１　最短路径问题。下图中给出一个地图，地图中每个顶点代表一个城市，两个城市之间的连线表示道路，连线上的数值代表道路的长度。现在，想从城市A到城市E，怎样走路程最短，

2、最短路程的长度是多少？现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设：Dis[x]为城市x到城市E的最短路径长度（x表示任意一个城市）;Map[i,j]表示i，j两个城市间的距离，若map[i,j]=0，则两个城市不通。我们可以使用回溯来计算Dis[x]:vars:未访问的城市聚合；functionsearch(who):integer;{求城市Who与城市E的最短距离}Vari,j,min:integer;beginifwho=Ethensearch:=0elsebegi

3、nmin:=maxint;fori取遍所有城市doif(map[who,i]>0)and(iins)thenbegins:=s-[i];{城市i已访问}j:=map[who,i]+search(i);{计算城市E至城市Who的路径长度}s:=s+[i];{恢复城市i未访问状态}ifj

4、A城市E的最短路径长度}writeln(dist[a]);end.这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要，所以时间复杂度为W(n!)，这是一个“指数级”的算法。那么还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求B2到E的最短路径的时候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径求了两遍。两样可以发现，在求从C1、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍。而在

5、整个过程中，从D1到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Dis[A]为止。阶段的划分具有如下性质：⑴阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响；⑵每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。ABCDE阶段1阶段2阶段3阶段4阶段0我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在

6、求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis[k][x]=dis[4][E]=0k=4，3…，0，其中dis[k][x]指k阶段的城市x。ED3D1D2C1C3C2AB3B2B15426346561222332340ABCDE阶段1阶段2阶段3阶段4阶段0我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis[k][x]=dis[4][E]=0k=4，3…，0，其中dis[k][x]指k阶段的城市x。ED3D1D2C1C3

7、C2AB3B2B15426346561222332340234ABCDE阶段1阶段2阶段3阶段4阶段0我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis[k][x]=dis[4][E]=0k=4，3…，0，其中dis[k][x]指k阶段的城市x。23ED3D1D2C1C3C2AB3B2B154263465612223323403446ABCDE阶段1阶段2阶段3阶段4阶段0我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。

8、在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis[k][x]=dis[4][E]=0k=4，3…，0，其中dis[k][x]指k阶段的城市x。ED3D1D2C1C3C2AB3B2B15426346561222332340234346778ABCDE阶段1阶段2阶段3阶段4阶段0我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis