搜索
算法读书笔记学生姓名：学号：院系：信息科学与技术学院专业：软件工程年级：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)//检查矩阵中第一行的边数是不是最多，并返回最多和最少的行数的