算法讀書報(bào)告

1、算法讀書筆記學(xué)生姓名： 學(xué) 號(hào)： 院 系： 信息科學(xué)與技術(shù)學(xué)院 專 業(yè)： 軟件工程 年 級(jí)： 2015級(jí) 引言算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。算法設(shè)計(jì)的優(yōu)劣決定著軟件系統(tǒng)的性能，對(duì)算法進(jìn)行研究使我們深刻理解問題的本質(zhì)以及可能的求解技術(shù)。評(píng)價(jià)算法性能的標(biāo)準(zhǔn)主要從算法執(zhí)行時(shí)間和存儲(chǔ)空間兩方面考慮，即算法執(zhí)行所需的時(shí)間T和存儲(chǔ)空間S來判斷一個(gè)算法的優(yōu)劣，他們都與問題規(guī)模有關(guān)，可以說算法效率是問題規(guī)模的函數(shù)。算法分析是對(duì)一個(gè)算法所需時(shí)間和空間所做的定量分析。需要一定的準(zhǔn)則和方法來分析算法的優(yōu)劣，主要考慮算法的正確定、可讀性、健壯性、高效率和低存儲(chǔ)量這幾個(gè)方面。算法分析是對(duì)一種

2、算法所消耗資源的估算。我們可依據(jù)此對(duì)解決同一問題的多種算法的代價(jià)加以比較。算法的復(fù)雜性就是算法所需的計(jì)算機(jī)資源，常用到復(fù)雜度函數(shù)表示算法的復(fù)雜性。使用漸進(jìn)分析法對(duì)算法復(fù)雜性進(jìn)行分析，在漸進(jìn)形態(tài)中高階、低階、等階之分。在算法設(shè)計(jì)階段，主要是如何設(shè)計(jì)解決給定的問題的有效算法也就是構(gòu)造問題的解，算法設(shè)計(jì)的任務(wù)就是對(duì)各類具體的問題設(shè)計(jì)高質(zhì)量的算法，以及研究算法的一般規(guī)律和方法。常用的算法設(shè)計(jì)方法主要有分治法、動(dòng)態(tài)規(guī)劃法、貪心算法和回溯法等。算法設(shè)計(jì)是一個(gè)構(gòu)造專用工具的過程，永遠(yuǎn)不會(huì)存在一種能解決所有問題的萬能方法；算法設(shè)計(jì)是一個(gè)復(fù)雜的、創(chuàng)造性的勞動(dòng)，要求設(shè)計(jì)者能運(yùn)用已有的知識(shí)和抽象思維，逐步形成算法的

3、基本思想，構(gòu)造出算法的具體步驟，以正確解決問題。算法的設(shè)計(jì)和分析有密切的聯(lián)系，它們相互影響。算法需要檢驗(yàn)和評(píng)價(jià)，反過來，算法評(píng)價(jià)的結(jié)果也可影響算法設(shè)計(jì)，以便改進(jìn)算法的性能。摘要P和NP問題是Steve Cook于1971年首次提出。“P/NP問題”，這里的P指多項(xiàng)式時(shí)間（Polynomial），一個(gè)復(fù)雜問題如果能在多項(xiàng)式時(shí)間內(nèi)解決，那么它便被稱為P問題，這意味著計(jì)算機(jī)可以在有限時(shí)間內(nèi)完成計(jì)算；NP指非確定性多項(xiàng)式時(shí)間（nondeterministic polynomial），一個(gè)復(fù)雜問題不能確定在多項(xiàng)式時(shí)間內(nèi)解決。先來介紹一下P問題和NP問題的定義。P類語言=L | L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)能

4、被一個(gè)DTM所接收的語言；NP類語言=L| L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一個(gè)NDTM所接收的語言。知道了NP問題，再來看看NPC問題。NPC問題的定義非常簡(jiǎn)單。同時(shí)滿足下面兩個(gè)條件的問題就是NPC問題。首先，它得是一個(gè)NP問題；然后，所有的NP問題都可以約化到它。證明一個(gè)問題是 NPC問題也很簡(jiǎn)單。先證明它至少是一個(gè)NP問題，再證明其中一個(gè)已知的NPC問題能約化到它，這樣就可以說它是NPC問題了。接下來要討論的頂點(diǎn)覆蓋問題就是NPC問題。頂點(diǎn)覆蓋的定義是這樣的：給定一個(gè)無向圖G=(V, E)和一個(gè)正整數(shù)k，若存在 ，V=k使得對(duì)任意的(u,v)E,都有uV或vV,則V稱為圖G的一個(gè)大小為k的頂點(diǎn)

5、覆蓋。用通俗的話來說，頂點(diǎn)覆蓋至少包含無向圖中邊的一個(gè)頂點(diǎn)。對(duì)于頂點(diǎn)覆蓋問題的NPC的證明主要分了兩步。第一步是證明其NP性，第二步是證明其完全性。NP性的證明：對(duì)給定的無向圖G=(V, E)，若頂點(diǎn) 是圖G的一個(gè)大小為k的頂點(diǎn)覆蓋，則可以構(gòu)造一個(gè)確定性的算法，以多項(xiàng)式的時(shí)間驗(yàn)證V=k，及對(duì)所有的(u,v)E，是否有uV或vV，因此頂點(diǎn)覆蓋問題是一個(gè)NP問題。完全性的證明：已知團(tuán)集問題是一個(gè)NP完全問題，若團(tuán)集問題歸約與頂點(diǎn)覆蓋問題，則頂點(diǎn)覆蓋問題就是一個(gè)NP完全問題。書中的解決方案頂點(diǎn)覆蓋的優(yōu)化問題是找出圖中的最小頂點(diǎn)覆蓋。為了用近似算法解決這個(gè)問題，假設(shè)頂點(diǎn)用編號(hào)，并用下面的鄰接表來存放頂

6、點(diǎn)與頂點(diǎn)之間的關(guān)聯(lián)邊 ：Struct adj_list/*鄰接表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)*/ int v_num; /*鄰接結(jié)點(diǎn)的編號(hào)*/ struct adj_list * next; /*下一個(gè)鄰接頂點(diǎn)*/ ;typedef struct adj_list NODE;NODE *Vn; /*圖的鄰接表頭結(jié)點(diǎn)*/則頂點(diǎn)覆蓋問題的近似算法的求解步驟可以敘述如下：步驟1. 頂點(diǎn)的初始編號(hào)u=0；步驟2. 如果頂點(diǎn)u存在關(guān)聯(lián)邊，轉(zhuǎn)到步驟3，否則，轉(zhuǎn)到步驟5；步驟3. 令關(guān)聯(lián)邊為(u,v)，把頂點(diǎn)u和頂點(diǎn)v登記到頂點(diǎn)覆蓋中；步驟4. 刪去與頂點(diǎn)u和頂點(diǎn)v關(guān)聯(lián)的所有邊；步驟5.，u=u+1, 如果，u<n

7、, 則轉(zhuǎn)到步驟2，否則，算法結(jié)束。 該算發(fā)的缺點(diǎn)就是沒有對(duì)算法做優(yōu)化，在某些情況下，求得的頂點(diǎn)幾乎包含了無向圖中全部的頂點(diǎn)。因?yàn)樵撍惴ǖ乃枷胧前堰呏械乃许旤c(diǎn)都放到頂點(diǎn)集中。但是該算法的思想是比較好的。我的想法由于課本上的算法沒有優(yōu)化，我的解決辦法主要是對(duì)算法進(jìn)行優(yōu)化。主要的思想是：盡量只把變邊中的一個(gè)頂點(diǎn)放到頂點(diǎn)覆蓋集里面。該算法的實(shí)現(xiàn)是基于圖的鄰接矩陣的。頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：typedef struct vertex_content /頂點(diǎn)int index; /頂點(diǎn)的編號(hào)，作交換和輸出用char content; /頂點(diǎn)的內(nèi)容VC; 優(yōu)化算法的大體步驟如下：1. 先輸入頂點(diǎn)集對(duì)應(yīng)的鄰接矩陣

8、；2. 為了減少空間復(fù)雜度，將矩陣的第一行作為最優(yōu)頂點(diǎn)集，該集合 中有兩個(gè)值0和1，0表示該下標(biāo)元素對(duì)應(yīng)的頂點(diǎn)不在最優(yōu)集里面，1則表示在最優(yōu)集里面；3. 從鄰接矩陣的第二行開始遍歷整個(gè)鄰接矩陣: 1). 若matrixrowlist=0,則不做任何處理繼續(xù)遍歷； 2). 若matrixrowlist=1,則需要看該列所對(duì)應(yīng)的頂點(diǎn)是在最優(yōu)集里面（即if(1=matrix0row)），若在，則將該列對(duì)應(yīng)的頂點(diǎn)從最優(yōu)集中刪除（即matrix0list=0），否則不做任何處理。直至遍歷完該鄰接矩陣。4. 對(duì)結(jié)果做一修正。首先來說明一下為什么對(duì)結(jié)果進(jìn)行修正。由于我們只取了一條邊中的一個(gè)頂點(diǎn)。這種做法有可

9、能會(huì)漏掉好多邊，具體如下圖1;圖1 頂點(diǎn)覆蓋問題示例圖如果a和b頂點(diǎn)的這條邊取b頂點(diǎn)，那么根據(jù)算法，和a和b相關(guān)的邊都要?jiǎng)h除掉，那么a和j、a和g之間的邊都要?jiǎng)h除掉。那么問題來了，如果g和k之間的邊選頂點(diǎn)k，那么a和g是有邊的，但是a和g都不在頂點(diǎn)覆蓋集合里面，這就不符合頂點(diǎn)覆蓋的定義。所以，該種算法如果不在最后對(duì)結(jié)果做修正的話，求出的頂點(diǎn)覆蓋集就是錯(cuò)誤的。很多次的實(shí)驗(yàn)都證明了該算法是可行的，在某些特殊的情況下可以求出頂點(diǎn)覆蓋的最優(yōu)集。實(shí)驗(yàn)結(jié)果無向圖如下圖的實(shí)驗(yàn)結(jié)果。a bcde算法的程序#ifndef coreFuction#define coreFuction#include<ios

10、tream>#include<iomanip>using namespace std;typedef struct vertex_content /頂點(diǎn)int index; /頂點(diǎn)的編號(hào)，作交換和輸出用char content; /頂點(diǎn)的內(nèi)容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); /返回需要交換的矩陣中兩行的行號(hào)void exchangeMatrixRows(int row1, int row2, int vertex_Count, int *matrix); /交換矩陣中兩行的元素（相應(yīng)的列也需要交換）void modifyResults(int vertex_Count, int *matrix); /對(duì)結(jié)果做一個(gè)修正void creatMenu(); /創(chuàng)建菜單void createAdjoinMatrix(int vertex_Count) /創(chuàng)建頂點(diǎn)集和圖的鄰接矩陣VC *vc=new VCvertex_C

12、ount; /定義頂點(diǎn)集并動(dòng)態(tài)的申請(qǐng)空間int *adjMatrix=new int *vertex_Count; /定義鄰接矩陣并動(dòng)態(tài)的申請(qǐng)空間for(int i=0;i<vertex_Count;i+)adjMatrixi=new int vertex_Count;cout<<endl;cout<<"請(qǐng)輸入各個(gè)頂點(diǎn)："<<endl; /輸入頂點(diǎn)集cout<<"-"<<endl;for(int j=0;j<vertex_Count;j+)vcj.index=j;cin>>

13、;vcj.content;cout<<endl;cout<<"請(qǐng)輸入圖的鄰接矩陣（有邊的輸入1，無邊的為0）"<<endl; /輸入對(duì)應(yīng)的鄰接矩陣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); /調(diào)用核心的算法void vertexCoverApp(VC *vc, int *matrix, int vertex_Count) /頂點(diǎn)覆蓋核心算法int row1=0,row2=0; returnExchangeRowsNum(row1,row2,vertex_Count,matrix); /統(tǒng)計(jì)矩陣各行中1的個(gè)數(shù)，返回最多邊和最少邊的定點(diǎn)編號(hào)if(0=row1) /若第一行的1的個(gè)數(shù)最多，則交換兩行exchangeMatrixRows(row1,row2,vertex_Count,matrix); /交換第一行和最少邊數(shù)的行號(hào)swap(vcrow1.index,vcrow2.

15、index); /將頂點(diǎn)集中的對(duì)應(yīng)的頂點(diǎn)的序號(hào)置換一下cout<<setw(2)<<row1<<row2<<vcrow1.content<<vcrow2.content<<endl;for(int firstRow=0;firstRow<vertex_Count;firstRow+) /為了減少空間復(fù)雜度，使用矩陣的第一行存儲(chǔ)符合條件的頂點(diǎn)（1表示在最優(yōu)集里面，0則相反【初始值全為1】）matrix0firstRow=1;for(int row=1;row<vertex_Count;row+) /優(yōu)化問題的算法

16、的核心代碼for(int list=0;list<vertex_Count;list+)switch(matrixrowlist)case 0: /無邊時(shí)不做任何處理break;case 1: /有邊時(shí)if(1=matrix0row) /若該頂點(diǎn)在最優(yōu)集合里面，則把該頂點(diǎn)對(duì)應(yīng)的邊的另外一個(gè)頂點(diǎn)從最優(yōu)集合中除去matrix0list=0;break;default:break;modifyResults(vertex_Count,matrix);/對(duì)結(jié)果做一個(gè)修正cout<<endl;cout<<"頂點(diǎn)覆蓋最優(yōu)集為："<<endl;

17、/輸出頂點(diǎn)覆蓋的結(jié)果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) /檢查矩陣中第一行的邊數(shù)是不是最多，并返回最多和最少的行數(shù)的行號(hào)int count=0; /對(duì)鄰接矩陣中1的個(gè)數(shù)計(jì)數(shù)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)/交換矩陣中兩行的元素（相應(yīng)的列也需要交換）for(int list=0;list<vertex_Count;list+) /先交換兩行的對(duì)應(yīng)位置的元素swap(