您好,欢迎访问三七文档
算法读书笔记学生姓名:学号:院系:信息科学与技术学院专业:软件工程年级:2015级引言算法是规则的有限集合,是为解决特定问题而规定的一系列操作。算法设计的优劣决定着软件系统的性能,对算法进行研究使我们深刻理解问题的本质以及可能的求解技术。评价算法性能的标准主要从算法执行时间和存储空间两方面考虑,即算法执行所需的时间T和存储空间S来判断一个算法的优劣,他们都与问题规模有关,可以说算法效率是问题规模的函数。算法分析是对一个算法所需时间和空间所做的定量分析。需要一定的准则和方法来分析算法的优劣,主要考虑算法的正确定、可读性、健壮性、高效率和低存储量这几个方面。算法分析是对一种算法所消耗资源的估算。我们可依据此对解决同一问题的多种算法的代价加以比较。算法的复杂性就是算法所需的计算机资源,常用到复杂度函数表示算法的复杂性。使用渐进分析法对算法复杂性进行分析,在渐进形态中高阶、低阶、等阶之分。在算法设计阶段,主要是如何设计解决给定的问题的有效算法也就是构造问题的解,算法设计的任务就是对各类具体的问题设计高质量的算法,以及研究算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划法、贪心算法和回溯法等。算法设计是一个构造专用工具的过程,永远不会存在一种能解决所有问题的万能方法;算法设计是一个复杂的、创造性的劳动,要求设计者能运用已有的知识和抽象思维,逐步形成算法的基本思想,构造出算法的具体步骤,以正确解决问题。算法的设计和分析有密切的联系,它们相互影响。算法需要检验和评价,反过来,算法评价的结果也可影响算法设计,以便改进算法的性能。摘要P和NP问题是SteveCook于1971年首次提出。“P/NP问题”,这里的P指多项式时间(Polynomial),一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算;NP指非确定性多项式时间(nondeterministicpolynomial),一个复杂问题不能确定在多项式时间内解决。先来介绍一下P问题和NP问题的定义。P类语言={L|L是一个能在多项式时间内能被一个DTM所接收的语言};NP类语言={L|L是一个能在多项式时间内被一个NDTM所接收的语言}。知道了NP问题,再来看看NPC问题。NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。证明一个问题是NPC问题也很简单。先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它,这样就可以说它是NPC问题了。接下来要讨论的顶点覆盖问题就是NPC问题。顶点覆盖的定义是这样的:给定一个无向图G=(V,E)和一个正整数k,若存在,∣V’∣=k使得对任意的(u,v)∈E,都有u∈V’或v∈V’,则V’称为图G的一个大小为k的顶点覆盖。用通俗的话来说,顶点覆盖至少包含无向图中边的一个顶点。对于顶点覆盖问题的NPC的证明主要分了两步。第一步是证明其NP性,第二步是证明其完全性。NP性的证明:对给定的无向图G=(V,E),若顶点是图G的一个大小为k的顶点覆盖,则可以构造一个确定性的算法,以多项式的时间验证∣V’∣=k,及对所有的(u,v)∈E,是否有u∈V’或v∈V’,因此顶点覆盖问题是一个NP问题。完全性的证明:已知团集问题是一个NP完全问题,若团集问题归约与顶点覆盖问题,则顶点覆盖问题就是一个NP完全问题。书中的解决方案顶点覆盖的优化问题是找出图中的最小顶点覆盖。为了用近似算法解决这个问题,假设顶点用编号,并用下面的邻接表来存放顶点与顶点之间的关联边:Structadj_list{/*邻接表结点的数据结构*/intv_num;/*邻接结点的编号*/structadj_list*next;/*下一个邻接顶点*/};typedefstructadj_listNODE;NODE*V[n];/*图的邻接表头结点*/则顶点覆盖问题的近似算法的求解步骤可以叙述如下:步骤1.顶点的初始编号u=0;步骤2.如果顶点u存在关联边,转到步骤3,否则,转到步骤5;步骤3.令关联边为(u,v),把顶点u和顶点v登记到顶点覆盖中;步骤4.删去与顶点u和顶点v关联的所有边;VV'VV'步骤5.,u=u+1,如果,un,则转到步骤2,否则,算法结束。该算发的缺点就是没有对算法做优化,在某些情况下,求得的顶点几乎包含了无向图中全部的顶点。因为该算法的思想是把边中的所有顶点都放到顶点集中。但是该算法的思想是比较好的。我的想法由于课本上的算法没有优化,我的解决办法主要是对算法进行优化。主要的思想是:尽量只把变边中的一个顶点放到顶点覆盖集里面。该算法的实现是基于图的邻接矩阵的。顶点的数据结构为:typedefstructvertex_content//顶点{intindex;//顶点的编号,作交换和输出用charcontent;//顶点的内容}VC;优化算法的大体步骤如下:1.先输入顶点集对应的邻接矩阵;2.为了减少空间复杂度,将矩阵的第一行作为最优顶点集,该集合中有两个值0和1,0表示该下标元素对应的顶点不在最优集里面,1则表示在最优集里面;3.从邻接矩阵的第二行开始遍历整个邻接矩阵:1).若matrix[row][list]==0,则不做任何处理继续遍历;2).若matrix[row][list]==1,则需要看该列所对应的顶点是在最优集里面(即if(1==matrix[0][row])),若在,则将该列对应的顶点从最优集中删除(即matrix[0][list]=0),否则不做任何处理。直至遍历完该邻接矩阵。4.对结果做一修正。首先来说明一下为什么对结果进行修正。由于我们只取了一条边中的一个顶点。这种做法有可能会漏掉好多边,具体如下图1;图1顶点覆盖问题示例图如果a和b顶点的这条边取b顶点,那么根据算法,和a和b相关的边都要删除掉,那么a和j、a和g之间的边都要删除掉。那么问题来了,如果g和k之间的边选顶点k,那么a和g是有边的,但是a和g都不在顶点覆盖集合里面,这就不符合顶点覆盖的定义。所以,该种算法如果不在最后对结果做修正的话,求出的顶点覆盖集就是错误的。很多次的实验都证明了该算法是可行的,在某些特殊的情况下可以求出顶点覆盖的最优集。实验结果无向图如下图的实验结果。abgkjhidcefml算法的程序#ifndefcoreFuction#definecoreFuction#includeiostream#includeiomanipusingnamespacestd;typedefstructvertex_content//顶点{intindex;//顶点的编号,作交换和输出用charcontent;//顶点的内容}VC;voidcreateAdjoinMatrix(intvertex_Count);voidvertexCoverApp(VC*vc,int**matrix,intvertex_Count);voidreturnExchangeRowsNum(int&rowMax,int&rowMin,intvertex_Count,int**matrix);//返回需要交换的矩阵中两行的行号voidexchangeMatrixRows(introw1,introw2,intvertex_Count,int**matrix);//交换矩阵中两行的元素(相应的列也需要交换)voidmodifyResults(intvertex_Count,int**matrix);//对结果做一个修正voidcreatMenu();//创建菜单voidcreateAdjoinMatrix(intvertex_Count)//创建顶点集和图的邻接矩阵{VC*vc=newVC[vertex_Count];//定义顶点集并动态的申请空间int**adjMatrix=newint*[vertex_Count];//定义邻接矩阵并动态的申请空间for(inti=0;ivertex_Count;i++)adjMatrix[i]=newint[vertex_Count];coutendl;cout请输入各个顶点:endl;//输入顶点集cout-----------------------------endl;for(intj=0;jvertex_Count;j++){vc[j].index=j;cinvc[j].content;}coutendl;cout请输入图的邻接矩阵(有边的输入1,无边的为0)endl;//输入对应的邻接矩阵cout---------------------------------------------endlendl;for(introw=0;rowvertex_Count;row++)for(intlist=0;listvertex_Count;list++)cinadjMatrix[row][list];vertexCoverApp(vc,adjMatrix,vertex_Count);//调用核心的算法}voidvertexCoverApp(VC*vc,int**matrix,intvertex_Count)//顶点覆盖核心算法{introw1=0,row2=0;returnExchangeRowsNum(row1,row2,vertex_Count,matrix);//统计矩阵各行中1的个数,返回最多边和最少边的定点编号if(0==row1)//若第一行的1的个数最多,则交换两行{exchangeMatrixRows(row1,row2,vertex_Count,matrix);//交换第一行和最少边数的行号swap(vc[row1].index,vc[row2].index);//将顶点集中的对应的顶点的序号置换一下coutsetw(2)row1row2vc[row1].contentvc[row2].contentendl;}for(intfirstRow=0;firstRowvertex_Count;firstRow++)//为了减少空间复杂度,使用矩阵的第一行存储符合条件的顶点(1表示在最优集里面,0则相反【初始值全为1】)matrix[0][firstRow]=1;for(introw=1;rowvertex_Count;row++)//优化问题的算法的核心代码{for(intlist=0;listvertex_Count;list++){switch(matrix[row][list]){case0://无边时不做任何处理break;case1://有边时if(1==matrix[0][row])//若该顶点在最优集合里面,则把该顶点对应的边的另外一个顶点从最优集合中除去matrix[0][list]=0;break;default:break;}}}modifyResults(vertex_Count,matrix);//对结果做一个修正coutendl;cout顶点覆盖最优集为:endl;//输出顶点覆盖的结果cout-----------------------------endl;for(inti=0;ivertex_Count;i++){if(1==matrix[0][i])coutsetw(3)vc[vc[i].index].content;}coutendl;for(intcount=0;countvertex_Count;count++)//释放空间delete[]matrix[count];delete[]matrix;delete[]vc;}voidreturnExchangeRowsNum(int&rowMax,int&rowMin,intvertex_Count,int**matrix)//检查矩阵中第一行的边数是不是最多,并返回最多和最少的行数的
本文标题:算法读书报告
链接地址:https://www.777doc.com/doc-2096956 .html