当前位置:文档之家› 动态规划求构造最优二叉查找树和最短路径

动态规划求构造最优二叉查找树和最短路径


x3
x1
x5
x n-2
xn
……
x n-3
x4
x2
a)原问题
x5
x n-1 x n-2
x3
x1
……
x n-3
x4
x2
b)子问题
x5
x n-1 x n-2
x3
x1Leabharlann ……x n-3x4
x2
c )子问题
图 1 原问题与子问题 b)当 xyk 的横坐标小于 xyk-1 的横坐标,那么就是如下情况 yk=n-2;yk-1=n-1。即为在 图 1 中的 b)情况中,不是由 xn-1 连到点 xn 上,而是由 xn-1 连到 xn-2 上,再有 xn-2 连 到 xn 上。我们同样可以用反证法来证明 x1, xy1, xy2, xy3, …, xyk-1 是子问题 x1, x2, x3, …, xyk-1 的最优解。 (3) 说明子问题的重叠性:就举 4 个点的例子来说明重叠性问题(如图 2 所示)。
xyk, xn 包含子问题 x1, x2, x3, …, xyk 的最优解 x1, xy1, xy2, xy3, …, xyk; b) 若 xyk 的横坐标小于 xyk-1 的横坐标; 则原问题的最优解为子问题 x1, x2, x3, …, xyk-1 的最优解再加上点 xyk 形成,即 x1, xy1, xy2, xy3, …, xyk-1 是子问题 x1, x2, x3, …, xyk-1 的最优解。 证明:a)当 yk=n-1 时,即点 xyk 为点 xn-1,则在最优解中,在 xyk 之前不会有比 xyk 横坐标还要大的点,即最优解包含的前缀 x1, xy1, xy2, xy3, …, xyk 所含有的顶点,全部 在子问题 x1, x2, x3, …, xn-2, xn-1 中,并且该前缀中横坐标最大的点与子问题的最后一 个点是同一个点,所以首先该前缀是子问题 x1, x2, x3, …, xn-2, xn-1 的一个解;再运用 反证法来证明该前缀是该子问题的最优解。如果如果 x1, xy1, xy2, xy3, …, xyk 不是子问 题 x1, x2, x3, …, xyk 的最优解,则一定存在另一个序列 x1, xz1, xz2, xz3, …, xyk 是子问题 x1, x2, x3, …, xyk 的最优解,即其形成的路径最短,那么该最优解再加上 cyk,n 即为问 题 x1, x2, x3, …, xn-1, xn 的一个解,并且其路径要比 x1, xy1, xy2, xy3, …, xyk, xn 要短,这就 与 x1, xy1, xy2, xy3, …, xyk, xn 是最优解相矛盾了,既而得证。同理,在 yk=n-2 时,在 最优解序列中若 xyk 的横坐标大于 xyk-1 的横坐标, 则在最优解的前缀 x1, xy1, xy2, xy3, …, xyk 中 xyk 的横坐标最大,该前缀均来自子问题 x1, x2, x3, …, xn-3, xn-2 中,并且 xyk 即为 xn-2,所以该前缀也是该子问题的一个解,我们同样可以运用反证法来证明该前缀 也是该子问题的一个最优解。xyk 只能取 xn-1、xn-2 这两种情况,因为只有这两点与 点 xn 直接相连。其实该结论说的是由图 1 所示的两种子问题的最后一个点与点 xn 搭一条边形成最终最优解的情况。
11S103001 郝亚峰 2 班 第七次算法作业
1、 根据构造二叉搜索树的最优解的信息来构造优化解。 在求解二叉查找树的最优解的过程中,我们用 Root[i, j]来记录节点序列<i, i+1, …, j>的根节 点,下面,我们就是要通过 Root 数组来构造优化解。我们用(i, j, k)来表示父节点与子节点 关系:i 表示父节点,j 表示左子节点,k 表示右子节点。当某一节点 m 没有子节点时(这里 所说的子节点是指给定节点序列中的某一点),则若没有左子节点,则我们用 dm-1 来时表 示,若没有右子节点,我们用 dm 来表示。算法如下: Print_Optimal_Result(i, j) { if(i<=j) { m=Root[i, j]; print ‘(’; print m; print ‘,’; if(m-1<i) print dm-1; else print Root[i, m-1]; print ‘,’; if(m+1>j) print dm; else print Root[m+1,j]; print ‘)’; Print_Optimal_Result(i, m-1); Print_Optimal_Result(m+1, j); } } 2、 利用动态规划求解最短路径。 问题定义:给定平面上 n 个点,没有任何两点具有相同的 x 坐标值,点按 x 坐标递增排序 为 x1,x2,…,xn。 任何一点只与 x 坐标比它小的和大的最邻近的分别 2 个点有边, 如 x5 与 x3, x4,x6,x7 有边相连,故任何一点最多关联 4 条边(边界点 x1,xn 关联两条边,点 x2, xn-1 关联三条边,其余点关联 4 条边)且如果边为 xixj 时,边的代价为 cij (cij>0)。试用动 态规划方法求出从 x1 到 xn 的代价和最短的一条路径。 解:我们按照这些步骤来解此题:分析最优解的结构—>找问题的优化子结构—>说明子问 题的重叠性—>递归地定义最优解的代价—>递归地划分子问题,直至问题不可再分—>自 底向上的求解子问题(计算优化解的代价并保存、 保存构造最优解的信息)—>根据构造最优 解的信息求解优化解。 (1) 分析最优解的结构:我们用点的序列来表示 x1 到 xn 的最短路径,如下所示: x1, xy1, xy2, xy3, …, xyk, xn 其中,yk∈{n-1, n-2}。 (2) 找问题的优化子结构:如果序列 x1, xy1, xy2, xy3, …, xyk, xn 表示由 x1, x2, x3, …, xn-1, xn 这些点所形成的图中由 x1 到 xn 的最短路径,则有如下结论: a) 若 xyk 的横坐标大于 xyk-1 的横坐标,即最优解序列的倒数第二点的横坐标大于 倒数第三个点的横坐标, 那么问题 x1, x2, x3, …, xn-1, xn 的最优解 x1, xy1, xy2, xy3, …,
0 , if i j d[i, j ] min{d [i, j 1] c j 1, j , d [i, j 2] c j 2, j , d[i, j 1] c j 1, j 2 c j 2, j } , if i j
(5) 递归地分解问题,直到问题不可再分:要求 d[1, n],则需求 d[1, n-1]和 d[1,n-2]; 要求 d[1, n-1], 则需求 d[1, n-2]和 d[1,n-3]; 要求 d[1, n-2]则需求 d[1, n-3]和 d[1, n-4] 等等,一直划分到 d[1, 1]=0。 (6) 自底向上求解:记录最优解和最优解信息,这两项工作我们都由 d[i, j]来完成。算 法如下: a) 求最短路径: Mix_Route() { b[1,1]=0; b[1,2]=b[1,1]+c[1,2];//c[i, j]存放点 xi 与 xj 的边的代价 FOR j=3 TO n DO d[1,j]=min{d[1,j-1]+c[j-1, j], d[1,j-2]+c[j-2, j], d[1,j-1]+c[j-1, j-2]+c[j-2, j]}; return d[1,n]; b) } 求解优化解: Print_Result(int i, int j) { if(j-1>=i&&d[i, j]== d[i,j-1]+c[j-1, j]) { Print_Result(i, j-1); print xj-1; } else if(j-2>=i&&d[i, j]== d[i,j-2]+c[j-2, j]) { Print_Result(i,,j-2); print xj-2; } else if(j-1>=i&&d[i,j]==d[i,j-1]+c[j-1, j-2]+c[j-2, j]) {
x1
x3
x2
x4
图 2 说明子问题重叠性 在图 2 中求 x1 到 x4 的最短路径, 要考虑这么 4 种情况: x1—>x2—>x4; x1—>x3—>x4; x1—>x3—>x2—>x4; x1—>x2—>x3—>x4;我们可以看到第一种情况与第四种情况存在 x1—>x2 的重叠性;第二种情况与第三种情况存在 x1—>x3 的重叠性。 (4) 递归地定义最优解的代价:我们用 d[i, j]来表示由 xi, xi+1, xi+2, …, xj 形成的图中由 xi 到 xj 的最短路径的代价/长度;则根据(2)中的分析得出如下结论:
Print_Result(i,j-1); print xj-1, xj-2; } } 经过以上递归,输出的最优解不包含最后一个点 xn,所以在这个程序之后我 们再加一条语句,输出 xn 即可。 (7) 复杂度分析: a) 空间复杂度:需要二维数组 c[n][n]来存放边的代价,但是每一点最多与其他 的 4 个点有边,所以不需要 O(n2),最多为 4n,所以需要 O(n),我们用 d[i][j] 来记录代价,但是 i 从来就没有改变过,所以其实只需要一个一维数组 d[n] 就可以了,其空间开销也为 O(n);综上,空间复杂度为 O(n)。 b) 时间复杂度: 在求最短路径的程序中, 只有一个循环, 其时间复杂度为 O(n); 在求优化解的程序中,其中有三个递归,但是每次只能执行一个,我们取最 坏的可能,每次执行的都是 Print_Result(i, j-1);而不是 Print_Result(i, j-2);则有 T(n)=T(n-1)+1;其复杂度也为 O(n)。所以时间复杂度为 O(n)。 (8) 题外话:解决本题另外一条思路:逐点扩张(应该是一种贪心)。大体阐述一下这思 路:对于图 1 中的 b)图,我们只要在此图加入点 xn 便形成了原问题,只要求出在 b)图中,x1 到 xn-1 和 xn-2 的最短距离,比较这两个最短距离分别加上相应的边代价 cn-1,n 和 cn-2,n 的大小即可。所以求 d[i,j]只需要求出在 xi, xi+1, …, xj-1 图中的 d[i,j-1]和 d[i,j-2],再分别加上 cn-1,n 和 cn-2,n,比较大小即可。注意,此处的 d[i,j]与上面动态 规划中的含义略有不同, 上面 d[i,j-2]表示 xi, xi+1, …, xj-2 图中由 xi 到 xj-2 的最短距离, 而此处可以表示在 xi, xi+1, …, xj-1 图中由 xi 到 xj-2 的最短距离。但是在图 xi, xi+1, …, xj-1 中加入 xj 后,形成了新图。在这个新图中 d[i,j-1]和 d[i,j-2]需要更新,否则会影响下 一步加入点 xj+1 后计算 d[i,j]的计算。 关键是怎么更新?只需要 d[i,j-1]加上新加入的 两条边之后与 d[i,j-2]比较,如果比 d[i,j-2]小则替换之;同理,d[i,j-2]加上新加入的 两条边之后与 d[i,j-1]比较,如果比 d[i,j-1]小则替换之。所以,我们从起始点每次顺 序加入一个点,通过前两个点计算新加入点的最短路径,在对前两个点的最短路 径进行更新,不断的这样迭代,直到最后一点,这样可求出最短路径。
相关主题