数学院算法实验

《算法设计与分析》实验指导书课程编号：课程名称：算法设计与分析英文名称：AlgorithmsDesignandAnalysis适应专业：计算机科学与技术执笔人：刘少兵参考教材：《计算机算法基础》（余祥宣）、《算法设计与分析》（王晓东）实验一（1）分治法基本要求1）了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2）掌握分治法的一般控制流程DanC(p,q)globaln，A[1:n];integerm,p,q;//1£p£q£nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p£m<qreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC3）实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。实验内容[斜线部分可以不用实现]编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。待排序的实验数据如下：a[]={70,66,88,70,45,90,33,66,70,22,11,90,11,90,11,90};输入10组相同的数据，验证排序结果和完成排序的比较次数。与复杂性函数所计算的比较次数比较。用表格列出比较结果。给出文字分析。归并排序算法和快速排序算法归并排序算法procedureMERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//integerlow，high；iflow<high；thenmid←，//求这个集合的分割点//callMERGESORT(low，mid)//将一个子集合排序//callMERGESORT(mid+1，high)//将另一个子集合排序callMERGE(low，mid，high)//归并两个已排序的子集合//endifendMERGESORT归并两个已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一个全程数组////辅助数组B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//当两个集合都没取尽时//ifA(h)≤A(j)thenB(i)←A(h)；h←h+1elseB(i)←A(j)；j←j+1endifi←i+1repeatifh>midthenfork←jtohighdo//处理剩余的元素//B(i)←A(k)；i←i+1repeatelsefork←htomiddoB(i)←A(k)；i←i+1repeatendif将已归并的集合复制到AendMERGE快速排序算法QuickSort(p,q)//将数组A[1:n]中的元素A[p],A[p+1],¼,A[q]按不降次序排列，并假定A[n+1]是一个确定的、且大于A[1:n]中所有的数。//intp,q;globaln,A[1:n];ifp<qthenj=Partition(p,q+1);//划分后j成为划分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)//退出过程时，p带着划分元素所在的下标位置。//integerm，p，i；globalA(m：p-1)v←A(m)；i←m//A(m)是划分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i)，A(p))//A(i)和A(p)换位//elseexitendifrepeatA(m)←A(p)；A(p)←v//划分元素在位置p//EndPARTITION实验一（2）用分治策略求2维极大点问题1、基本要求在2维空间中，如果x1>x2且y1>y2，那么称点(x1,y1)支配点(x2,y2)。如果一个点没有其他点支配，那么称其为极大者。已知有n个点的集合，求极大点问题是指找出在n个点中的所有极大点。使用分治策略，首先找出垂直于x轴的中位线L，它划分整个点集为两个子集，分别用SL和SR表示中线L的左边点集合和右边点集合。下一步，分别找出SL和SR的极大点。合并过程相当简单。由于在SR中点的x值总是大于SL中每个点的x值，所以SL中的点是极大点当且仅当它的y值不小于SR中极大点的y值。在平面中找出极大点的分治算法输入：n个平面点的集合。输出：S的极大点。步骤1.如果S只含一个点，那么输出该点为极大点；否则，找一条垂直于x轴的直线L，它划分点集合为两个子集合SL和SR，每个子集含有n/2个点。步骤2.递归地找出SL和SR的极大点。步骤3.将SL和SR的极大点投影到直线L上，并根据它们的y值排序这些点。对投影进行线性扫描，如果SL中的极大点的y值小于SR中某个极大点的y值，那么舍弃它。2、实验内容随机输入平面上n个点的集合；使用分治策略编制计算机程序求出这n个点的极大点。编程实现2维极大点问题的求解，且在程序中体现分治策略。程序能处理任意的n个点。

实验二贪心法基本要求优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedycriterion）。2）一般方法①根据题意，选取一种量度标准。②按这种量度标准对这n个输入排序③依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedureGREEDY(A，n)/*贪心法一般控制流程*///A(1：n)包含n个输入//solutions←φ//将解向量solution初始化为空／fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)endifrepeatreturn(solution)endGREEDY实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。实验内容[斜线部分可以不用实现]编程实现背包问题贪心算法和最小生成树prim算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。背包问题的实验数据如下表：n=8,m=110,12345678Profit[i]1121313343535565Weight[i]111212333434555X[i]背包问题贪心算法和prim算法背包问题的贪心算法procedureKNAPSACK(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)是解向量//realP(1：n)，W(1：n)，X(1：n)，M，cu；integeri，n；X←0//将解向量初始化为零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)>cuthenexitendifX(i)←1cu←cu-W(i)repeatifi≤nthenX(i)←cu/W(i)endifendGREEDY-KNAPSACKprocedureprim(G,)status←“unseen”//T为空status[1]←“treenode”//将1放入Tforeachedge(1,w)dostatus[w]←“fringe”//找到T的邻接点dad[w]←1;//w通过1与T建立联系dist[w]←weight(1,w)//w到T的距离repeatwhilestatus[t]≠“treenode”dopickafringeuwithmindist[w]//选取到T最近的节点status[u]←“treenode”foreachedge(u,w)do修改w和T的关系repeatrepeat实验三动态规划基本要求理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（RichardBellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。us初始值，uj第j段的最优值。一般方法找出最优解的性质，并刻画其结构特征；递归地定义最优值（写出动态规划方程）；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。实验内容[斜线部分可以不实现]编程递归实现0-1背包问题并回溯求出问题的解向量（即X[N]的值）和多段图的最短路经问题的动态规划算法。图的数据结构采用邻接表。要求用文件装入5个多段图数据，编写从文件到邻接表的函数。验证算法的时间复杂性。0-1背包问题的实验数据见实验二的背包问题数据。多段图算法procedureFGRAPH(E，k，n，P)//输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i，j)是边<i,j>的成本。P(1：k)是最小成本路径。//realCOST(n)，integerD(n一1)，P(k)，r，j，k，nCOST(n)←0forj←n-1to1by－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；forj←2tok-1do//找路径上的第j个节点//P(j)←D(P(j-1))repeatendFGRAPH

实验四回溯法基本要求理解可用回溯法求解的问题问题P通常要能表达为对已知的、由n元组(x1，…，xn)组成的状态空间E={(x1，…，xn)|xiÎSi,i=1,2,…n}，给定关于n元组中的分量的一个约束集D，求满足D的全部约束条件的所有n元组。Si是xi的定义域且Si是有穷集，称E中满足D的全部约束条件的所有n元组为问题P的一个解。理解回溯法的基本思想回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法的形式描述：procedureBACAKTRACE(n)k=1;while(k>0)doifTk(x1，x2，…，xk-1)的值还未取遍then{xk←Tk(x1，x2，…，xk-1)中未取遍过的值；ifBk(x1，x2，…，xk)then{(x1，x2，…，xk)被激活；ifk==nthen输出(x1，x2，…，xn)；elsek=k+1；//深度扩展搜索}}elsek=k-1//试探完了所有的xk，回溯endBACAKTRACE实验内容[斜线部分可以不用实现]编程实现n皇后算法，要求求出8皇后问题的所有解。编程实现0-1背包问题的最优解。测试数据采用贪心算法一章的实验数据。用图形输出中间过程。在程序中添加统计扩展节点数，估计算法的复杂性。n皇后算法procedureNQUEENS(n)X(1)←0；k←1//k是当前行；X(k)是当前列//Whilek>0do//对所有的行执行以下语句//{X(k)←X(k)+1//移到下一列//WhileX(k)≤nandnotPLACE(k)doX(k)←X(k)十lifX(k)≤n//找到一个位置//thenifk=n//是一个完整的解吗//thenprint(X)//是，打印这个数组//else{k←k+1；X(k)←0；}elsek←k－1//回溯//}endNQUEENS

实验五分支限界算法一、实验目的1、掌握树搜索策略。2、掌握分支限界策略。3、掌握用分支限界策略求解最短路径问题。二、实验学时：2学时三、实验要求1、编程实现分支限界策略求解最短路径问题。2、能对任意图，给定源点和终点，求它们的最短路径。四、实验原理1、分支限界策略的思想分支限界策略是解决一大类组合问题的最有效策略之一。基本上，该策略表明问题可能有许多可行解。然而，人们通过发现许多可行解不能成为最优解来修剪解空间。2、分支限界策略的两个重要机制：一个机制是产生分支，另一个机制是产生一个界限以致于能终止许多分支。五、实验内容 1、图3-1中，问题是找出从v0到v3的最短路径。这个问题能先通过转换成一棵树搜索问题而有效地解决。图3-12、图3-2显示了所有6个可行解。如果不使用穷举策略，那么分支限界策略是怎么实现找到最短路径的呢？图3-23、发现可行解，V0->V1,1->V2,3->V3，这个可行解的代价是5。这个代价等于5的可行解可作为最优解的上界。任何代价大于5的解都不能成为一个最优解。因此，这个上界能终止许多不成熟的分支。4、因此，穷举搜索整个解空间是可以避免的。六、实验任务1、使用分支限界策略求解最短路径问题。2、能对任意给定的一副带权图，给定源点和终点，求它们的最短路径长度及经过的最短路径。

实验六解决最近点对问题的随机算法一、实验目的1、掌握随机算法的思想。2、掌握最近点对问题的求解方法。二、实验学时：2学时（综合设计性实验）三、实验要求1、编程实现最近点对问题的求解。2、使用随机算法求解最近点对问题。四、实验原理1、随机算法的概念相对较新。在执行算法的过程中，随机算法可以做出任意的选择，这意味着可随机地执行某些动作。2、由于某些动作的执行是随机的，随机算法具有下面两个属性：(1)在最优化问题的情况中，随意算法给出一个最优解。但是由于在算法中随机地采取动作，因此随机最优算法的时间复杂度也是随机的。这样，随机最优算法的平均情况时间复杂度远比它的最坏情况时间复杂度重要。(2)在判定问题的情况中，随机算法有时会出错。然而，产生错误的概率是非常小的；另外，随机算法并非总是有用。五、实验内容1、最近点对问题令x1,x2,…,xn为二维平面上的n个点。最近点对问题是找到最近的一对点xi和xj，使得xi和xj之间的距离是所有可能的点对距离中最小。解决该问题的直接方法是计算出所有的n(n-1)/2个点对之间的距离，并在这些距离中找出最小值。2、随机算法的主要思想如果两个点xj和xk彼此远离，那么它们之间的距离不可能最小，因此可以被忽略。由于这种思想，随机算法首先将点分成几