《大连理工大学算法分析与设计》由会员分享，可在线阅读，更多相关《大连理工大学算法分析与设计（13页珍藏版）》请在金锄头文库上搜索。
1、5、 已知一有向图G=(V,E),其每条边(u,v)E均对应有一个实数值r(u,v),表示从顶点u到顶点v之间的通信线路的可靠性，取值范围为0r(u,v)1,定义r(u,v)为从u到v的线路不中断的概率，并假定这些概率是相互独立的。写出一个有效算法，来找出两个指定顶点间的最可靠的线路。 解答： 运用Dijkstra算法的思想，将原来的加法计算改为乘法即可。 例如下图： 解答过程如下： 每一行的意义：从A出发，经过所用可能路径， 到达各点的最可靠效率 第一次找到B之后，就不用再找了， 因为再乘以任何r(u,v)（0-1） 会使得A到B的可靠性减小,6、 Floyd算法求出任意两点间的最短距离。
2、例：有向图中有四个点，点之间的距离如下所示： 解答： for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) A i，j = min A i，j ，A i，k + A k，j 算法思想： 从图的带权邻接矩阵A=a(i,j) nn开始， 递归地进行n次更新，即由矩阵D(0)=A， 按一个公式，构造出矩阵D(1)； 又用同样地公式由D(1)构造出D(2)； 最后又用同样的公式由D(n-1)构造出矩阵D(n)。 矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,9、对于矩阵乘法： 第1个乘号 第(n-1)个乘号 A1 A2 An d0 d1 d1 d2
3、 dn-1 dn 给出每个乘法运算的执行顺序，使得进行整个矩阵乘法运算过程中进行的数值乘法次数最少。,解答： 定义函数cost(low, high)，表示计算矩阵A(low)A(high)所需的最少数值乘法次数，root(low, high)表示相应于上述cost(low, high)的进行的最后一次乘法的位置。 则状态转移方程为： 当low = high时，cost(low, high) = 0，root(low, high) = -1 当low high 时， cost(low, high) = mincost(low, k) + cost(k+1, high) + d(low-1)dkd
4、(high) | low=k=high-1 式(1) root(low, high) = k (式(1)中的k),伪代码实现：,定义两个二维数组cost1.n1n和root1n1n / 初始化数组的对角线元素 for( i=1; i=1; low- ) for( high=low+1; high=n; high+) costlowhigh = maxNum; /maxNum表示无穷大 for (k=low; khigh; k+)/计算选取不同乘号进行最后一次乘法运算的代价 if (costlowk + costk+1high + dlow-1dkdhigh costlowhigh) costl
5、owhigh= costlowk + costkhigh + dlow-1dkdhigh; rootlowhith = k; 最终，cost1n即为进行该矩阵乘法所需的最少代价。,对root数组进行如下的后序遍历，即可得到代价最少的乘法次序，乘法进行的次序存储在数组multOrder中 int multOrderNext; extractOrderWrap(int n, int root, multOrder) multOrderNext = 1; extractOrder(1, n, multOrder); extractOrder(int low, int high, int root,
6、int multOrder) Int k; If (low high) k = rootlowhigh; extractOrder(low, k, multOrder); extractOrder(k+1, high, multOrder); multOrdermultOrderNext = k; multOrderNext+; ,举例：,A1 A2 A3 A4 301 140 4010 1025 d0d1 d1d2 d2 d3 d3 d4 注：以下costij用Cij表示，rootij用Rij表示 C11 = C22 = C33 = C44 = 0 C12 = C11 + C22 + 301
7、40 = 1200 R12 = 1 C23 = C22 + C33 + 14010 = 400 R23 = 2 C34 = C33 + C44 + 401025 = 10000 R34 = 3,C13 = C11 + C23 + 30110 = 700 ok C12 + C33 + 304010 = 13200 R13 = 1 C24 = C22 + C34 + 14025 = 11000 C23 + C44 + 11025 = 650 ok R24 = 3 C14 = C11 + C24 + 30125 = 1400 ok C12 + C34 + 304025 1400 C13 + C44
8、+ 301025 1400 R14 = 1 所以最小代价C14 = 1400,10、给定长度为n的有序元素序列K1， K2， ，Kn，其各个元素被查找的概率（或频率）分别为p1，p2， ， pn。描述构造最优二分树的算法,解答： 定义函数cost(low, high)，表示用K(low)K(high)构造得到的最优二分树的总代价，root(low, high)表示相应二分树的树根位置。 则状态转移方程为： 当 lowhigh (low = high-1)时， 令cost(low, high = 0) root(low, high) = -1 当low = high 时， cost(low, h
9、igh) = p(low)+p(high) + mincost(low, k-1) + cost(k+1, high) | low=k=high 式(1) root(low, high) = k ( 式(1)中对应cost(low, high)的k ),伪代码实现： 定义两个二维数组cost1.n+10n和root1n+10n / 初始化数组的对角线元素，即(t+1, t) for( i=1; i=1; low- ) for( high=low; high=n; high+) costlowhigh = maxNum;/maxNum表示无穷大 for (k=low; k=high; k+)/选
10、取不同的元素作为当前树的树根 currentCost = lowhigh的概率和 + cost(low, k-1) + cost(k+1, high) if (currentCost costlowhigh) costlowhigh = currentCost; rootlowhigh = k; 最终，cost1n即为最优二分树的代价。 对root数组进行先序遍历，即可得到最优二分树。,举例：,注：以下costij用Cij表示，rootij用Rij表示,C10 = C21 = C32 = C43 = C54 = C65 = C76 = 0 R10 = R11 = R22 = R33 = R44
11、 = C65 = C76 = -1 C66 = C65 + C76 + 2 = 2 OK R66 = 6 C55 = C54+ C65 + 1 = 1 OK R55 = 5 C56 = C54 + C66 + 3 = 5 C55 + C76 + 3 = 4 OK R56 = 6,C44 = C43 + C54 + 7 = 7 OK R44 = 4 C45 = C43 + C55 + 8 = 9 OK R45 = 4 C44 + C65 + 8 = 15 C46 = C43 + C56 + 10 = 14 OK R46 = 4 C44 + C66 + 10 = 19 C45 + C76 + 10 = 19 以下省略. C16 = C10 + C26 + 25 = 63 C11 + C36 + 25 = 52 OK R16 = 2,最优二分树的建立 root16 = 2，所以2为树根，左子树有1，右子树有3-6； root36 = 4，所以4为树根，左子树有3，右子树有5-6； root56 = 6，所以6为树根，左子树有5，右子树为空 最后构成的最优二分树如图：,Over Thank you,
