算法设计及分析实验指导书.doc

算法设计与分析实验指导书课程编号：09110112课程名称：算法设计与分析英文名称：Algorithms Design and Analysis适应专业：计算机科学与技术执 笔 人：沙莎实验指导书名称：计算机算法基础实验一 分治法1、 基本要求1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2）掌握分治法的一般控制流程DanC(p,q) global n，A1:n; integer m,p,q; / 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q); / pmq return 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+10个待排序的元素/ integer low，high； if lowmid then for kj to high do /处理剩余的元素/ B(i) A(k)；ii+1 repeat else for kh to mid do B(i) A(k)；ii+1 repeat endif 将已归并的集合复制到A end MERGE快速排序算法QuickSort(p,q) /将数组A1:n中的元素 Ap, Ap+1, , Aq按不降次序排列， 并假定An+1是一个确定的、且大于 A1:n中所有的数。/ int p,q; global n, A1:n; if pq then j=Partition(p, q+1); / 划分后j成为划分元素的位置 QuickSort(p,j-1); QuickSort(j+1,q); endif end QuickSortprocedure PARTITION(m，p) /退出过程时，p带着划分元素所在的下标位置。/ integer m，p，i；global A(m：p-1) vA(m)；im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat /i由左向右移/ loop pp-1 until A(p)v repeat /p由右向左移/ if icu then exit endif X(i) 1 cucu-W(i) repeat if in then X(i) cu/ W(i) endif end GREEDY-KNAPSACKprocedure prim(G,)status“unseen” / T为空 status1“tree node” / 将1放入Tfor each edge(1,w) do statusw“fringe” / 找到T的邻接点 dadw 1; /w通过1与T建立联系 distw weight(1,w) /w到T的距离 repeatwhile statust “tree node” do pick a fringe u with min distw / 选取到T最近的节点 statusu“tree node” for each edge(u,w) do 修改w和T的关系 repeatrepeat实验三 动态规划1、 基本要求1） 理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2） 理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。us 初始值，uj第j段的最优值。3） 一般方法 找出最优解的性质，并刻画其结构特征； 递归地定义最优值（写出动态规划方程）； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。2、 实验内容1） 编程实现多段图的最短路经问题的动态规划算法。2） 图的数据结构采用邻接表。3） 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4） 验证算法的时间复杂性。3、 多段图算法procedure FGRAPH(E，k，n，P) /输入是按段的顺序给结点编号的，有n个结点 的k段图。E是边集，c(i，j)是边的成本。 P(1：k)是最小成本路径。/ real COST(n)，integerD(n一1)，P(k)，r，j，k，n COST(n) 0 for jn-1to 1by1do /计算COST(j)/ 设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最小值 COST(j)c(j，r)+COST(r) D(j)r repeat /向前对j-1进行决策/ P(1)1；P(k)n； for j2 to k-1 do /找路径上的第j个节点/ P(j)D ( P(j-1) ) repeat end FGRAPH实验四 深度优先搜索1、 基本要求1） 理解深度优先搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点v，如果边（v，w）是还未探测的边，则沿（v，w）继续搜索下去。当所有的边（v，w）都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。2） 理解深度优先搜索过程中顶点的三种状态还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。2、 实验内容1） 编程实现深度优先搜索算法。2） 修改算法使之可以找出图的所有树。3） 修改算法使之可以判断图是否为一棵树。4） 修改算法使之可以判断图是否存在一个环。3、 深度优先算法procedure DFS(G); for 每个顶点uG do coloru White; repeat for每个顶点uG do if coloru=White then DFS_Visit(G,u);end; procedure DFS_Visit(u); coloruGray; for (u,w)E do /探寻边(u,w) if colorw=White then DFS_Visit(w); repeat coloruBlack; /完成后置u为黑色end;实验五 回溯法1、 基本要求1） 理解可用回溯法求解的问题问题P通常要能表达为对已知的、由n元组(x1，xn)组成的状态空间E=(x1，xn)| xiSi,i=1,2,n，给定关于n元组中的分量的一个约束集D，求满足D的全部约束条件的所有n元组。 Si 是 xi 的定义域且Si 是有穷集，称E中满足D 的全部约束条件的所有n元组为问题P的一个解。2） 理解回溯法的基本思想回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法的形式描述：procedure BACAKTRACE(n) k =1 ; while (k0) do if Tk (x1，x2， x k-1)的值还未取遍 then xkTk (x1，x2， x k-1)中未取遍过的值；if Bk (x1，x2， x k) then(x1，x2， x k)被激活；if k =n then 输出(x1，x2， x n)；else k =k+1； / 深度扩展搜索 else k = k -1 / 试探完了所有的x k，回溯 end BACAKTRACE2、 实验内容1） 编程实现n皇后算法。2） 用图形输出中间过程。3） 在程序中添加统计扩展节点数，估计算法的复杂性。3、 n皇后算法procedure NQUEENS(n)X(1)0；k1 /