算法論文分治法和分支限界.doc

成 績 評 定 表學(xué)生姓名xx班級學(xué)號xx專 業(yè)信息與計(jì)算科學(xué)課程設(shè)計(jì)題目1.分治法解決最近距離問題2.分支限界解決旅行商售貨員問題評語組長簽字：成績?nèi)掌?20 年 月 日課程設(shè)計(jì)任務(wù)書學(xué) 院理學(xué)院專 業(yè)信息與計(jì)算科學(xué)學(xué)生姓名xx班級學(xué)號xx課程設(shè)計(jì)題目1.分治法解決最近距離問題2.分支限界解決旅行商售貨員問題實(shí)踐教學(xué)要求與任務(wù):1、鞏固和加深對計(jì)算機(jī)算法分析與設(shè)計(jì)基本知識的理解。2、初步掌握簡單軟件的分析方法和設(shè)計(jì)方法。3、了解與課程有關(guān)的工程技術(shù)規(guī)范，能正確解釋和分析設(shè)計(jì)結(jié)果。4、具體任務(wù)（1）分治法解決最近距離問題（2）分支限界解決旅行商售貨員問題工作計(jì)劃與進(jìn)度安排:第一天 查閱資相關(guān)料； 第二、三天 程序設(shè)計(jì)； 第四天 程序調(diào)試； 第五天 答辯指導(dǎo)教師： 201 年 月 日專業(yè)負(fù)責(zé)人：201 年 月 日學(xué)院教學(xué)副院長：201 年 月 日摘 要計(jì)算效率是一個(gè)古老的研究課題?？茖W(xué)技術(shù)的發(fā)展使得計(jì)算日趨復(fù)雜，計(jì)算量越來越大，許多理論上可計(jì)算的問題，常常由于其計(jì)算量巨大布變成了現(xiàn)實(shí)不可計(jì)算的問題，這就產(chǎn)生了理論可計(jì)算而現(xiàn)實(shí)不可計(jì)算的矛盾，而算法設(shè)計(jì)與分析的任務(wù)就是對各類具體的問題設(shè)計(jì)高質(zhì)量的算法，以及研究設(shè)計(jì)算法的一般規(guī)律和方法。常用的算法設(shè)計(jì)方法主要有分治法、動(dòng)態(tài)規(guī)劃、貪婪法和回溯法等。問題一：運(yùn)用分治法對多點(diǎn)最近距離問題進(jìn)行算法設(shè)計(jì)，把問題分解為不是相互獨(dú)立的子問題，計(jì)算保存子問題的答案，從而再求重復(fù)子問題時(shí)可以直接找到答案。通過反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。問題二：運(yùn)用分支限界對旅行商售貨員問題進(jìn)行算法設(shè)計(jì)，求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。）分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界；然后按照廣度優(yōu)先策略遍歷問題的解空間樹，在某一分支上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值（對最小化問題，估算結(jié)點(diǎn)的下界，對最大化問題，估算結(jié)點(diǎn)的上界）。如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將其丟棄（從此結(jié)點(diǎn)生成的解不會(huì)比目前已得的更好），否則入待處理。 關(guān)鍵詞： 算法設(shè)計(jì)與分析；分支限界法；分治法目 錄1分治法解決最近距離問題11.1 問題描述11.2 算法設(shè)計(jì)21.3 算法實(shí)現(xiàn)31.4 運(yùn)行結(jié)果與分析62分支限界解決旅行商售貨員問題72.1 問題描述72.2 算法設(shè)計(jì)82.3 算法實(shí)現(xiàn)92.4 運(yùn)行結(jié)果與分析14總結(jié)15參考文獻(xiàn)16V1分治法解決最近距離問題1.1 問題描述已知集合S中有n個(gè)點(diǎn)，分治法的思想就是將S進(jìn)行拆分，分為2部分求最近點(diǎn)對。算法每次選擇一條垂線L，將S拆分左右兩部分為SL和SR，L一般取點(diǎn)集S中所有點(diǎn)的中間點(diǎn)的x坐標(biāo)來劃分，這樣可以保證SL和SR中的點(diǎn)數(shù)目各為n/2，（否則以其他方式劃分S，有可能導(dǎo)致SL和SR中點(diǎn)數(shù)目一個(gè)為1，一個(gè)為n-1，不利于算法效率，要盡量保持樹的平衡性）依次找出這兩部分中的最小點(diǎn)對距離：L和R，記SL和SR中最小點(diǎn)對距離 = min（L，R），如圖1.1：圖1.1以L為中心，為半徑劃分一個(gè)長帶，最小點(diǎn)對還有可能存在于SL和SR的交界處，如圖1.1中的虛線帶，p點(diǎn)和q點(diǎn)分別位于SL和SR的虛線范圍內(nèi)，在這個(gè)范圍內(nèi)，p點(diǎn)和q點(diǎn)之間的距離才會(huì)小于，最小點(diǎn)對計(jì)算才有意義。1.2 算法設(shè)計(jì) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。 分治策略是：對于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。 如果原問題可分割成k個(gè)子問題，1kn ，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 分治法在每一層遞歸上都有三個(gè)步驟： 分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題； 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題； 合并：將各個(gè)子問題的解合并為原問題的解。分治法所能解決的問題一般具有以下幾個(gè)特征： 1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決 2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 3) 利用該問題分解出的子問題的解可以合并為該問題的解； 4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。 第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。算法的時(shí)間復(fù)雜度：首先對點(diǎn)集S的點(diǎn)x坐標(biāo)和y坐標(biāo)進(jìn)行升序排序，需要循環(huán)2nlogn次，復(fù)雜度為O(2nlogn)接下來在分治過程中，對于每個(gè)SyL中的點(diǎn)，都需要與SyR中的6個(gè)點(diǎn)進(jìn)行比較O(n)= 2O(n/2) + (n/2)*6 （一個(gè)點(diǎn)集劃分為左右兩個(gè)點(diǎn)集，時(shí)間復(fù)雜度為左右兩個(gè)點(diǎn)集加上中間區(qū)域運(yùn)算之和）其解為O(n) O(3nlogn)因此總的時(shí)間復(fù)雜度為O(3nlogn)，比蠻力法的O(n2)要高效。1.3 算法實(shí)現(xiàn)#include#includestruct Point double x; double y; ; double ClosestPoints(Point S,int n) int i,j,a=0,b=0,c=0; int p=0,q=0; double dmin,k=99999.0,d1,d2,d,r25,m,sum=0; Point temp,S15,S25,P15,P25; if(n2) return k; for(i=0;i=i;j-)if(Sj.xSj-1.x) temp=Sj; Sj=Sj-1; Sj-1=temp; for(i=0;in;i+) sum+=Si.x; m=sum/(float)n; for(i=0;in;i+) if(Si.xm) S1a+=Si; else S2b+=Si; d1=ClosestPoints(S1,a); d2=ClosestPoints(S2,b); if(d1d2) d=d1; else d=d2; for(i=0;ia;i+) if(abs(S1i.x-m)d) P1p+=S1i; for(i=0;ib;i+) if(abs(S2i.x-m)d) P2q+=S2i; for(i=0;i=i;j-)if(P1j.yP1j-1.y) temp=P1j; P1j=P1j-1; P1j-1=temp; for(i=0;i=i;j-)if(P2j.yP2j-1.y) temp=P2j; P2j=P2j-1; P2j-1=temp; dmin=abs(P20.y-P10.y); for(i=0;iq;i+) for(j=0;jp;j+) if(abs(P2i.y-P1j.y)d) rc+=sqrt(P1i.x-P2j.x)*(P1i.x-P2j.x)+(P1i.y-P2j.y)*(P1i.y-P2j.y); dmin=r0; for(i=0;ic;i+) if(ridmin) dmin=ri; if(ddmin) return d; else return dmin; void main() int i,n; Point S100; cout請輸入點(diǎn)的個(gè)數(shù)(小于等于100的正整數(shù)):n; cout請輸入平面上的n個(gè)點(diǎn)的橫縱坐標(biāo):endl; for(i=0;iSi.xSi.y; cout平面上最近兩個(gè)點(diǎn)間的距離為：ClosestPoints(S,n)endl; 1.4 運(yùn)行結(jié)果與分析圖1.2問題1運(yùn)行結(jié)果 輸入4個(gè)不同點(diǎn)的坐標(biāo)分別為4，5,6，1,2，10,7，8,輸出平面上最近兩個(gè)點(diǎn)的距離為4.47214。根據(jù)多組測試的數(shù)據(jù)來看，分治法解決該問題得效率比蠻力法要高效的多，但是如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。2分支限界解決旅行商售貨員問題2.1 問題描述 某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一次，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。 路線是一個(gè)帶權(quán)圖。如圖1.3中各邊的費(fèi)用（權(quán)）為正數(shù)。圖1.3的一條周游路線是包括V中的每個(gè)頂點(diǎn)在內(nèi)的一條回路。周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和。旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖1.3中找出費(fèi)用最小的周游路線。 圖1.32.2 算法設(shè)計(jì) 分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出T中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。針對本問題我們可以得出：1.利用二維數(shù)組保存圖信息City_GraphMAX_SIZEMAX_SIZE,其中City_Graphij的值代表的是城市i與城市j之間的路徑費(fèi)用,一旦一個(gè)城市沒有通向另外城市的路，則不可能有回路，不用再找下去了 2. 我們可以任意選擇一個(gè)城市，作為出發(fā)點(diǎn)。（因?yàn)樽詈蠖际且粋€(gè)回路，無所謂從哪出發(fā)）。算法的基本思路： 首先考慮s=n-2的情形，此時(shí)當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，否則舍去該葉結(jié)點(diǎn)。當(dāng)sn-2時(shí)，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。由于當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的路徑是x0:s，其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn)xs+1:n-1中選取的頂點(diǎn)xi，且(xs，xi)是所給有向圖G中的一條邊。對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn)，計(jì)算出其前綴(x0:s，xi)的費(fèi)用cc和相應(yīng)的下界lcost。當(dāng)lcostbestc時(shí)，將這個(gè)可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中，算法中while循環(huán)的終止條件是排列樹的一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。當(dāng)s=n-1時(shí)，已找到的回路前綴是x0:n-1，它已包含圖G的所有n個(gè)頂點(diǎn)。因此，當(dāng)s=n-1時(shí)，相應(yīng)的擴(kuò)展結(jié)點(diǎn)表示一個(gè)葉結(jié)點(diǎn)，此時(shí)該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)用等于cc和lcost的值，剩余的活結(jié)點(diǎn)的lcost值不小于已找到的回路的費(fèi)用，它們都不可能導(dǎo)致費(fèi)用更小的回路。因此已找到葉結(jié)點(diǎn)所相應(yīng)的回路是一個(gè)最小費(fèi)用旅行售貨員回路，算法結(jié)束時(shí)返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。2.3 算法實(shí)現(xiàn)#include #include using namespace std; /-宏定義- #define MAX_CITY_NUMBER 10 /城市最大數(shù)目 #define MAX_COST 10000000 /兩個(gè)城市之間費(fèi)用的最大值 /-全局變量- int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; /表示城市間邊權(quán)重的數(shù)組 int City_Size; /表示實(shí)際輸入的城市數(shù)目 int Best_Cost; /最小費(fèi)用 int Best_Cost_PathMAX_CITY_NUMBER; /最小費(fèi)用時(shí)的路徑 /-定義結(jié)點(diǎn)- typedef struct Node int lcost; /優(yōu)先級 int cc; /當(dāng)前費(fèi)用 int rcost; /剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用的和 int s; /當(dāng)前結(jié)點(diǎn)的深度，也就是它在解數(shù)組中的索引位置 int xMAX_CITY_NUMBER; /當(dāng)前結(jié)點(diǎn)對應(yīng)的路徑 struct Node* pNext; /指向下一個(gè)結(jié)點(diǎn) Node; /-定義堆和相關(guān)對操作- typedef struct MiniHeap Node* pHead; /堆的頭 MiniHeap; /初始化 void InitMiniHeap(MiniHeap* pMiniHeap) pMiniHeap-pHead = new Node; pMiniHeap-pHead-pNext = NULL; /入堆 void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node* pinnode = new Node; /將傳進(jìn)來的結(jié)點(diǎn)信息copy一份保存 /這樣在函數(shù)外部對node的修改就不會(huì)影響到堆了 pinnode-cc = node.cc; pinnode-lcost = node.lcost; pinnode-pNext = node.pNext; pinnode-rcost = node.rcost; pinnode-s = node.s; pinnode-pNext = NULL; for(int k=0;kxk = node.xk; pre = pMiniHeap-pHead; next = pMiniHeap-pHead-pNext; if(next = NULL) pMiniHeap-pHead-pNext = pinnode; else while(next != NULL) if(next-lcost) (pinnode-lcost) /發(fā)現(xiàn)一個(gè)優(yōu)先級大的，則置于其前面 pinnode-pNext = pre-pNext; pre-pNext = pinnode; break; /跳出 pre = next; next = next-pNext; pre-pNext = pinnode; /放在末尾 /出堆 Node* RemoveMiniHeap(MiniHeap* pMiniHeap) Node* pnode = NULL; if(pMiniHeap-pHead-pNext != NULL) pnode = pMiniHeap-pHead-pNext; pMiniHeap-pHead-pNext = pMiniHeap-pHead-pNext-pNext; return pnode; /-分支限界法找最優(yōu)解- void Traveler() int i,j; int temp_xMAX_CITY_NUMBER; Node* pNode = NULL; int miniSum; /所有結(jié)點(diǎn)最小出邊的費(fèi)用和 int miniOutMAX_CITY_NUMBER; /保存每個(gè)結(jié)點(diǎn)的最小出邊的索引 MiniHeap* heap = new MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;iCity_Size;i+) miniOuti = MAX_COST; /初始化時(shí)每一個(gè)結(jié)點(diǎn)都不可達(dá) for(j=0;j0 & City_GraphijminiOuti) /從i到j(luò)可達(dá)，且更小 miniOuti = City_Graphij; if (miniOuti = MAX_COST)/ i 城市沒有出邊 Best_Cost = -1; return ; miniSum += miniOuti; for(i=0;ilcost = 0; /當(dāng)前結(jié)點(diǎn)的優(yōu)先權(quán)為0 也就是最優(yōu) pNode-cc = 0; /當(dāng)前費(fèi)用為0（還沒有開始旅行） pNode-rcost = miniSum; /剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用和就是初始化的miniSum pNode-s = 0; /層次為0 pNode-pNext = NULL; for(int k=0;kxk = Best_Cost_Pathk; /第一個(gè)結(jié)點(diǎn)所保存的路徑也就是初始化的路徑 put(heap,*pNode); /入堆 while(pNode != NULL & (pNode-s) City_Size-1) /堆不空 不是葉子 for(int k=0;kxk ; /將最優(yōu)路徑置換為當(dāng)前結(jié)點(diǎn)本身所保存的 /* * * pNode 結(jié)點(diǎn)保存的路徑中的含有這條路徑上所有結(jié)點(diǎn)的索引 * * x路徑中保存的這一層結(jié)點(diǎn)的編號就是xCity_Size-2 * * 下一層結(jié)點(diǎn)的編號就是xCity_Size-1 */ if (pNode-s) = City_Size-2) /是葉子的父親 int edge1 = City_Graph(pNode-x)City_Size-2(pNode-x)City_Size-1; int edge2 = City_Graph(pNode-x)City_Size-1(pNode-x)0; if(edge1 = 0 & edge2 = 0 & (pNode-cc+edge1+edge2) cc + edge1+edge2; pNode-cc = Best_Cost; pNode-lcost = Best_Cost; /優(yōu)先權(quán)為 Best_Cost pNode-s+; /到達(dá)葉子層 else /內(nèi)部結(jié)點(diǎn) for (i=pNode-s;ixpNode-spNode-xi = 0) /可達(dá) /pNode的層數(shù)就是它在最優(yōu)路徑中的位置 int temp_cc = pNode-cc+City_GraphpNode-xpNode-spNode-xi; int temp_rcost = pNode-rcost-miniOutpNode-xpNode-s; /下一個(gè)結(jié)點(diǎn)的剩余最小出邊費(fèi)用和 /等于當(dāng)前結(jié)點(diǎn)的rcost減去當(dāng)前這個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用 if (temp_cc+temp_rcostBest_Cost) /下一個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用和小于當(dāng)前的最優(yōu)解，說明可能存在更優(yōu)解 for (j=0;jxpNode-s+1 = Best_Cost_Pathi; /將當(dāng)前結(jié)點(diǎn)的編號放入路徑的深度為s+1的地方 temp_xi = Best_Cost_PathpNode-s+1; /將原路/徑中的深度為s+1的結(jié)點(diǎn)編號放入當(dāng)前路徑的 /相當(dāng)于將原路徑中的的深度為i的結(jié)點(diǎn)與深度W為s+1的結(jié)點(diǎn)交換 Node* pNextNode = new Node; pNextNode-cc = temp_cc; pNextNode-lcost = temp_cc+temp_rcost; pNextNode-rcost = temp_rcost; pNextNode-s = pNode-s+1; pNextNode-pNext = NULL; for(int k=0;kxk = temp_xk; put(heap,*pNextNode); delete pNextNode; pNode = RemoveMiniHeap(heap); int main() int i,j;printf(請輸入旅行的節(jié)點(diǎn)數(shù)：); scanf(%d,&City_Size); for(i=0;iCity_Size;i+) printf(請分別輸入每個(gè)節(jié)點(diǎn)與其它