算法设计与分析答案参考.docx
《算法设计与分析答案参考.docx》由会员分享，可在线阅读，更多相关《算法设计与分析答案参考.docx（9页珍藏版）》请在冰点文库上搜索。
算法设计与分析答案参考
1、用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i,j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。
解
在每条边的矩阵行中依次加入顶点1,2,3，判断有无最短路径
2、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：
①每个选手必须与其他n-1名选手比赛各一次；
②每个选手一天至多只能赛一次；
③循环赛要在最短时间内完成。
（1）如果n=2k，循环赛最少需要进行几天；
（2）当n=23=8时，请画出循环赛日程表。
解：
（1）至少要进行n天
（2）如右图：
3、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
解：
用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。
步骤V1V2E1E2
1.{a}{b}{}{ab}
2.{a,b}{d}{ab}{bd}
3.{a,b,d}{c,f}{ab,bd}{dc,df}
4.{a,b,d,c}{f}{ab,bd}{df}
5.{a,b,c,d,f}{e}{ab,bd,dc,df}{fe}
6.{a,b,c,d,e,f}{g}{ab,bd,dc,df,fe}{eg}
7.{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}{gh}
8.{a,b,c,d,e,f,g,h}{}{ab,bd,de,df,fe,eg,gh}{}
结果：
从a到h的最短路径为
，权值为18。
求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。
补充例题：
求A到各个顶点的最短路径：
解：
4、用动态规划策略求解最长公共子序列问题：
（1）给出计算最优值的递归方程。
（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
解：
（1）
（2）
Ｙ Ａ Ｂ Ｃ Ｂ
Ｘ 0 0 0 0
Ｂ 0 0 1 1 1
Ｃ 0 0 1 2 2
Ｄ 0 0122
Ａ 01122
最长公共子序列：
｛ＢＣ｝
5、对下图所示的连通网络G，用克鲁斯卡尔（Kruskal）算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。
说明该算法的贪心策略和算法的基本思想，并简要分析算法的
时间复杂度。
答：
TE={（3,4）,（2,3）,（1,5）,（4,6）（4,5）}
贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。
基本思想：
首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。
时间复杂度为：
O（eloge）
6、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。
A=（65,70,75,80,85,55,50,2）
解：
第一个分割元素为65
7、对于下图，写出图着色算法得出一种着色方案的过程。
解：
K←1
X[1]←1,返回true
X[2]←1,返回false;X[2]←X[2]+1=2,返回true
X[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回true
X[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true
找到一个解（1，2，3，3）
8、有n个物品，已知n=7,利润为P=（10,5,15,7,6,18,3），重量W=（2,3,5,7,1,4,1），背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。
解：
定义结构体数组G将物品编号、利润、重量作为一个结构体
例如G[k]={1,10,2}
求最优解按利润/重量的递减序有：
{5,6,1,6}、{1,10,2,5}{6,18,4,9/2}、{3,15,5,3}、{7,3,1,3}、{2,5,3,5/3}、{4,7,7,1}
算法：
procedureKNAPSACK（PWMXn）
//P（1n）和W（1n）分别含有按P（i）/W（i）≥P（i+1）/W（i+1）排序的n件物品的效益值和重量。
M是背包的容量大小而x（1n）是解向量//
realP（1n）W（1n）X（1n）Mcu
integerin
X←0//将解向量初始化为零//
cu←M//cu是背包剩余容量//
fori←1tondo
ifW（i）>cuthenexitendif
X（i）←1
cu←cu-W（i）
repeat
endGREEDY-KNAPSACK
根据算法得出的解：
X=1,1,1,1,1,0,0获利润52
而解1,1,1,1,0,1,0可获利润54，因此贪心法不一定获得最优解。
9、排序和查找是经常遇到的问题。
按照要求完成以下各题：
（1）对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
（2）给出上述算法的递归算法。
（3）使用上述算法对
（1）所得到的结果搜索如下元素，并给出搜索过程：
18，31，135。
解：
（1）第一步：
15291351832127255
第二步：
29135183227251515
第三步：
13532291827251551
第四步：
13532292725181551
（2）输入：
递减数组A[left:
right]，待搜索元素v。
输出：
v在A中的位置pos，或者不在A中的消息（-1）。
步骤：
intBinarySearch（intA[],intleft,intright,intv）
{
intmid;
if（left<=right）
{
mid=int（（left+right）/2）;
if（v==A[mid]）returnmid;
elseif（v>A[mid]）returnBinarySearch（A,left,mid-1,v）;
elsereturnBinarySearch（A,mid+1,right,v）;
}
else
return-1;
}
（3）搜索18：
首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。
搜索31：
首先与27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。
搜索135：
首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。
10、假设有7个物品，它们的重量和价值如下表所示。
若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。
请写出状态空间搜索树。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
解：
（1）求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。
（2）按照单位效益从大到小依次排列这7个物品为：
FBGDECA。
将它们的序号分别记为1～7。
则可生产如下的状态空间搜索树。
其中各个节点处的限界函数值通过如下方式求得：
a．
b.
c．
d.
e.
f.
g.
h.
i.
j.
在Q1处获得该问题的最优解为
，背包效益为170。
即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。
升级会员 