算法设计与分析答案参考

解

在每条边的矩阵行中依次加入顶点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中的顶点相邻接且距离最短的路径。

步骤    V1                 V2        E1                          E2

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　 0   1   2   2

Ａ　　0   1   1   2   2           

最长公共子序列：｛ＢＣ｝

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}  

   算法： 

   procedure  KNAPSACK(P  W  M  X  n) 

    //P(1 n)和W(1 n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小 而x(1 n)是解向量// 

    real P(1 n) W(1 n) X(1 n) M cu

    integer i n 

    X←0  //将解向量初始化为零// 

    cu←M  //cu是背包剩余容量// 

    for i←1 to n do 

if W(i)>cu then exit endif

      X(i) ←1 

       cu←cu-W(i) 

    repeat     end GREEDY-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）第一步：15 29 135 18 32 1 27 25 5

       第二步：29 135 18 32 27 25 15 1 5

第三步：135 32 29 18 27 25 15 5 1

第四步：135 32 29 27 25 18 15 5 1

（2）输入：递减数组A[left:right]，待搜索元素v。

输出：v在A中的位置pos，或者不在A中的消息（-1）。

步骤：

int BinarySearch(int A[],int left,int right,int v)

{

    int mid;

if (left<=right)

    {

        mid=int((left+right)/2);

        if (v==A[mid]) return mid;

        else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);

        else return BinarySearch(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，使用回溯方法求解此背包问题。请写出状态空间搜索树。

（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。