算法读书报告

1、算法读书笔记学生姓名： 学 号： 院 系： 信息科学与技术学院 专 业： 软件工程 年 级： 2015级 引言算法是规则的有限集合，是为解决特定问题而规定的一系列操作。算法设计的优劣决定着软件系统的性能，对算法进行研究使我们深刻理解问题的本质以及可能的求解技术。评价算法性能的标准主要从算法执行时间和存储空间两方面考虑，即算法执行所需的时间T和存储空间S来判断一个算法的优劣，他们都与问题规模有关，可以说算法效率是问题规模的函数。算法分析是对一个算法所需时间和空间所做的定量分析。需要一定的准则和方法来分析算法的优劣，主要考虑算法的正确定、可读性、健壮性、高效率和低存储量这几个方面。算法分析是对一种

2、算法所消耗资源的估算。我们可依据此对解决同一问题的多种算法的代价加以比较。算法的复杂性就是算法所需的计算机资源，常用到复杂度函数表示算法的复杂性。使用渐进分析法对算法复杂性进行分析，在渐进形态中高阶、低阶、等阶之分。在算法设计阶段，主要是如何设计解决给定的问题的有效算法也就是构造问题的解，算法设计的任务就是对各类具体的问题设计高质量的算法，以及研究算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划法、贪心算法和回溯法等。算法设计是一个构造专用工具的过程，永远不会存在一种能解决所有问题的万能方法；算法设计是一个复杂的、创造性的劳动，要求设计者能运用已有的知识和抽象思维，逐步形成算法的

3、基本思想，构造出算法的具体步骤，以正确解决问题。算法的设计和分析有密切的联系，它们相互影响。算法需要检验和评价，反过来，算法评价的结果也可影响算法设计，以便改进算法的性能。摘要P和NP问题是Steve Cook于1971年首次提出。“P/NP问题”，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决。先来介绍一下P问题和NP问题的定义。P类语言=L | L是一个能在多项式时间内能

4、被一个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,都有uV或vV,则V称为图G的一个大小为k的顶点

5、覆盖。用通俗的话来说，顶点覆盖至少包含无向图中边的一个顶点。对于顶点覆盖问题的NPC的证明主要分了两步。第一步是证明其NP性，第二步是证明其完全性。NP性的证明：对给定的无向图G=(V, E)，若顶点 是图G的一个大小为k的顶点覆盖，则可以构造一个确定性的算法，以多项式的时间验证V=k，及对所有的(u,v)E，是否有uV或vV，因此顶点覆盖问题是一个NP问题。完全性的证明：已知团集问题是一个NP完全问题，若团集问题归约与顶点覆盖问题，则顶点覆盖问题就是一个NP完全问题。书中的解决方案顶点覆盖的优化问题是找出图中的最小顶点覆盖。为了用近似算法解决这个问题，假设顶点用编号，并用下面的邻接表来存放顶

6、点与顶点之间的关联边 ：Struct adj_list/*邻接表结点的数据结构*/ int v_num; /*邻接结点的编号*/ struct adj_list * next; /*下一个邻接顶点*/ ;typedef struct adj_list NODE;NODE *Vn; /*图的邻接表头结点*/则顶点覆盖问题的近似算法的求解步骤可以叙述如下：步骤1. 顶点的初始编号u=0；步骤2. 如果顶点u存在关联边，转到步骤3，否则，转到步骤5；步骤3. 令关联边为(u,v)，把顶点u和顶点v登记到顶点覆盖中；步骤4. 删去与顶点u和顶点v关联的所有边；步骤5.，u=u+1, 如果，u<n

7、, 则转到步骤2，否则，算法结束。 该算发的缺点就是没有对算法做优化，在某些情况下，求得的顶点几乎包含了无向图中全部的顶点。因为该算法的思想是把边中的所有顶点都放到顶点集中。但是该算法的思想是比较好的。我的想法由于课本上的算法没有优化，我的解决办法主要是对算法进行优化。主要的思想是：尽量只把变边中的一个顶点放到顶点覆盖集里面。该算法的实现是基于图的邻接矩阵的。顶点的数据结构为：typedef struct vertex_content /顶点int index; /顶点的编号，作交换和输出用char content; /顶点的内容VC; 优化算法的大体步骤如下：1. 先输入顶点集对应的邻接矩阵

8、；2. 为了减少空间复杂度，将矩阵的第一行作为最优顶点集，该集合 中有两个值0和1，0表示该下标元素对应的顶点不在最优集里面，1则表示在最优集里面；3. 从邻接矩阵的第二行开始遍历整个邻接矩阵: 1). 若matrixrowlist=0,则不做任何处理继续遍历； 2). 若matrixrowlist=1,则需要看该列所对应的顶点是在最优集里面（即if(1=matrix0row)），若在，则将该列对应的顶点从最优集中删除（即matrix0list=0），否则不做任何处理。直至遍历完该邻接矩阵。4. 对结果做一修正。首先来说明一下为什么对结果进行修正。由于我们只取了一条边中的一个顶点。这种做法有可

9、能会漏掉好多边，具体如下图1;图1 顶点覆盖问题示例图如果a和b顶点的这条边取b顶点，那么根据算法，和a和b相关的边都要删除掉，那么a和j、a和g之间的边都要删除掉。那么问题来了，如果g和k之间的边选顶点k，那么a和g是有边的，但是a和g都不在顶点覆盖集合里面，这就不符合顶点覆盖的定义。所以，该种算法如果不在最后对结果做修正的话，求出的顶点覆盖集就是错误的。很多次的实验都证明了该算法是可行的，在某些特殊的情况下可以求出顶点覆盖的最优集。实验结果无向图如下图的实验结果。a bcde算法的程序#ifndef coreFuction#define coreFuction#include<ios

10、tream>#include<iomanip>using namespace std;typedef struct vertex_content /顶点int index; /顶点的编号，作交换和输出用char content; /顶点的内容VC;void createAdjoinMatrix(int vertex_Count);void vertexCoverApp(VC *vc, int *matrix, int vertex_Count);void returnExchangeRowsNum(int &rowMax, int &rowMin, int v

11、ertex_Count, int *matrix); /返回需要交换的矩阵中两行的行号void exchangeMatrixRows(int row1, int row2, int vertex_Count, int *matrix); /交换矩阵中两行的元素（相应的列也需要交换）void modifyResults(int vertex_Count, int *matrix); /对结果做一个修正void creatMenu(); /创建菜单void createAdjoinMatrix(int vertex_Count) /创建顶点集和图的邻接矩阵VC *vc=new VCvertex_C

12、ount; /定义顶点集并动态的申请空间int *adjMatrix=new int *vertex_Count; /定义邻接矩阵并动态的申请空间for(int i=0;i<vertex_Count;i+)adjMatrixi=new int vertex_Count;cout<<endl;cout<<"请输入各个顶点："<<endl; /输入顶点集cout<<"-"<<endl;for(int j=0;j<vertex_Count;j+)vcj.index=j;cin>>

13、;vcj.content;cout<<endl;cout<<"请输入图的邻接矩阵（有边的输入1，无边的为0）"<<endl; /输入对应的邻接矩阵cout<<"-"<<endl<<endl;for(int row=0;row<vertex_Count;row+)for(int list=0;list<vertex_Count;list+)cin>>adjMatrixrowlist;vertexCoverApp(vc, adjMatrix, vertex_Cou

14、nt); /调用核心的算法void vertexCoverApp(VC *vc, int *matrix, int vertex_Count) /顶点覆盖核心算法int row1=0,row2=0; returnExchangeRowsNum(row1,row2,vertex_Count,matrix); /统计矩阵各行中1的个数，返回最多边和最少边的定点编号if(0=row1) /若第一行的1的个数最多，则交换两行exchangeMatrixRows(row1,row2,vertex_Count,matrix); /交换第一行和最少边数的行号swap(vcrow1.index,vcrow2.

15、index); /将顶点集中的对应的顶点的序号置换一下cout<<setw(2)<<row1<<row2<<vcrow1.content<<vcrow2.content<<endl;for(int firstRow=0;firstRow<vertex_Count;firstRow+) /为了减少空间复杂度，使用矩阵的第一行存储符合条件的顶点（1表示在最优集里面，0则相反【初始值全为1】）matrix0firstRow=1;for(int row=1;row<vertex_Count;row+) /优化问题的算法

16、的核心代码for(int list=0;list<vertex_Count;list+)switch(matrixrowlist)case 0: /无边时不做任何处理break;case 1: /有边时if(1=matrix0row) /若该顶点在最优集合里面，则把该顶点对应的边的另外一个顶点从最优集合中除去matrix0list=0;break;default:break;modifyResults(vertex_Count,matrix);/对结果做一个修正cout<<endl;cout<<"顶点覆盖最优集为："<<endl;

17、/输出顶点覆盖的结果cout<<"-"<<endl;for(int i=0;i<vertex_Count;i+)if(1=matrix0i)cout<<setw(3)<<vcvci.index.content;cout<<endl;for(int count=0;count<vertex_Count;count+) /释放空间delete matrixcount;delete matrix;delete vc;void returnExchangeRowsNum(int &rowMax, int

18、 &rowMin, int vertex_Count, int *matrix) /检查矩阵中第一行的边数是不是最多，并返回最多和最少的行数的行号int count=0; /对邻接矩阵中1的个数计数int rowMaxNum=0;int rowMinNum=vertex_Count-1;for(int row=0;row<vertex_Count;row+)for(int list=0;list<vertex_Count;list+)if(1=matrixrowlist)count+;if(rowMaxNum<=count)rowMaxNum=count;rowMax=row;if(rowMinNum>=count)rowMinNum=count;rowMin=row;count=0;void exchangeMatrixRows(int row1, int row2, int vertex_Count, int *matrix)/交换矩阵中两行的元素（相应的列也需要交换）for(int list=0;list<vertex_Count;list+) /先交换两行的对应位置的元素swap(