《算法设计与分析》实验指导书课程编号：09110112课程名称：算法设计与分析英文名称：Algorithms Design and Analysis适应专业：计算机科学与技术执笔人：沙莎实验指导书名称：计算机算法基础实验一分治法1、基本要求1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。

那末，对于这类问题分治法是十分有效的。

2）掌握分治法的一般控制流程DanC(p,q)global n，A[1:n]; integer m,p,q; // 1≤p≤q≤nif Small(p,q) then return G(p,q);else m=Divide(p,q); // p≤m<qreturn Combine(DanC(p,m),DanC(m+1,q));endifend DanC3）实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

2、实验内容1）编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。

2）输入10组相同的数据，验证排序结果和完成排序的比较次数。

3）与复杂性函数所计算的比较次数比较。

4）用表格列出比较结果。

5）给出文字分析。

3、归并排序算法和快速排序算法归并排序算法procedure MERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//integer low，high；if low<high；then mid←， //求这个集合的分割点//call MERGESORT(low，mid) //将一个子集合排序//call MERGESORT(mid+1，high) //将另一个子集合排序call MERGE(low，mid，high) //归并两个已排序的子集合// endifend MERGESORT归并两个已排序的集合procedure MERGE(low，mid，high)//A(low：high)是一个全程数组////辅助数组B(low；high)//integer h，i，j，k；h←low；i←low；j←mid+1；while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h)；h←h+1else B(i) ←A(j)；j←j+1endifi←i+1repeatif h>mid thenfor k←j to high do //处理剩余的元素//B(i) ←A(k)；i←i+1repeatelse for k←h to mid doB(i) ←A(k)；i←i+1repeatendif将已归并的集合复制到Aend MERGE快速排序算法QuickSort(p,q)//将数组A[1:n]中的元素A[p], A[p+1], , A[q]按不降次序排列，并假定A[n+1]是一个确定的、且大于A[1:n]中所有的数。

//int p,q; global n, A[1:n];if p<q thenj=Partition(p, q+1); // 划分后j成为划分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifend QuickSortprocedure PARTITION(m，p)//退出过程时，p带着划分元素所在的下标位置。

//integer m，p，i；global A(m：p-1)v←A(m)；i←m //A(m)是划分元素//looploop i←i+1 until A(i)≥v repeat //i由左向右移//loop p←p-1 until A(p)≤v repeat //p由右向左移//if i<pthen call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位//else exitendifrepeatA(m) ←A(p)；A(p) ←v //划分元素在位置p//End PARTITION实验二贪心法1、基本要求1）优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。

可行解一般来说是不唯一的。

那些使目标函数取极值(极大或极小)的可行解，称为最优解。

2）贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。

决策一旦作出，就不可再更改。

作出贪心决策的依据称为贪心准则（greedy criterion）。

2）一般方法①根据题意，选取一种量度标准。

②按这种量度标准对这n个输入排序③依次选择输入量加入部分解中。

如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

procedure GREEDY(A，n) /*贪心法一般控制流程*///A(1：n)包含n个输入//solutions←φ //将解向量solution初始化为空／for i←1 to n dox←SELECT(A)if FEASIBLE(solution，x)then solutions←UNION(solution，x)endifrepeatreturn(solution)end GREEDY3）实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。

2、实验内容1）编程实现背包问题贪心算法和最小生成树prim算法。

通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。

2）输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。

3）将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。

3、背包问题贪心算法和prim算法背包问题的贪心算法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 doif W(i)>cu then exit endifX(i) ←1cu←cu-W(i)repeatif i≤n then X(i) ←cu/ W(i)endifend GREEDY-KNAPSACKprocedure prim(G,)status←“unseen” // T为空status[1]←“tree node” // 将1放入Tfor each edge(1,w) dostatus[w]←“fringe” // 找到T的邻接点dad[w] ←1; //w通过1与T建立联系dist[w] ←weight(1,w) //w 到T 的距离repeatwhile status[t]≠ “tree node ” dopick a fringe u with min dist[w] // 选取到T 最近的节点status[u]←“tree node ”for each edge(u,w) do修改w 和T 的关系repeatrepeat实验三 动态规划1、 基本要求1） 理解最优子结构的问题。

有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。

这类问题的解决是多阶段的决策过程。

在50年代，贝尔曼（Richard Bellman ）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。

对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。

最优子结构性质：原问题的最优解包含了其子问题的最优解。

子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。

2） 理解分段决策Bellman 方程。

每一点最优都是上一点最优加上这段长度。

即当前最优只与上一步有关。

u s 初始值，u j 第j 段的最优值。

3） 一般方法① 找出最优解的性质，并刻画其结构特征；② 递归地定义最优值（写出动态规划方程）；③ 以自底向上的方式计算出最优值；④ 根据计算最优值时得到的信息，构造一个最优解。

步骤1-3是动态规划算法的基本步骤。

在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

2、 实验内容1） 编程实现多段图的最短路经问题的动态规划算法。

2） 图的数据结构采用邻接表。

⎪⎩⎪⎨⎧+==≠}.{min ,0ij i j i j s w u u u3）要求用文件装入5个多段图数据，编写从文件到邻接表的函数。

4）验证算法的时间复杂性。

3、多段图算法procedure FGRAPH(E，k，n，P)//输入是按段的顺序给结点编号的，有n个结点的k段图。

E是边集，c(i，j)是边<i,j>的成本。

P(1：k)是最小成本路径。

//real COST(n)，integerD(n一1)，P(k)，r，j，k，nCOST(n)← 0for j←n-1to 1by－1do //计算COST(j)//设r是一个这样的结点，(j，r) E且使c(j，r)+COST(r)取最小值COST(j)←c(j，r)+COST(r)D(j)←rrepeat //向前对j-1进行决策//P(1)←1；P(k)←n；for j←2 to k-1 do //找路径上的第j个节点//P(j)←D ( P(j-1) )repeatend FGRAPH实验四深度优先搜索1、基本要求1）理解深度优先搜索策略是尽可能“深”地搜索图。

在深度优先搜索中，对于最新发现的顶点v，如果边（v，w）是还未探测的边，则沿（v，w）继续搜索下去。

当所有的边（v，w）都己被探寻过，搜索将回溯到发现结点v的顶点。

这一过程一直进行到回到源点为止。

如果还存在未被发现的顶点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。