【正文】 Fig. Huffman code after debug to resultFig. Dijkstra debug 單源最短路徑問題的調(diào)試Fig. Delete data problem debug 。算法復雜度為O（nlogn）。遇到f[i]，一種活動出棧（相當于一個會場用完，可以作為其他活動用），直到遇到最后一個活動的開始時間，把所有的活動都安排好，結(jié)束遍歷。Count用于會場數(shù)使用的最大數(shù)，遍歷數(shù)組，統(tǒng)計區(qū)間的最大的重疊數(shù)目。算法分析：時間復雜性為O(n)，空間復雜性為O(n)。（4）新問題和原問題相同，只是問題規(guī)模由n減小為n1，刪去的數(shù)字個數(shù)由k減少為k1。 刪數(shù)問題通過第五章對刪數(shù)問題的分析，可以得出刪數(shù)算法的思路為：（1）x1x2…xixj；（2）如果xkxj，則刪去xj，即得到一個新的數(shù)且這個數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2…xixkxm…xn。j++) ；if((!s[j])＆＆(c[u][j]maxint)){Type newdist=dist[u)+c[u][j]if (newdistdist[j]){dist[]]=newdist； prev[j]=u。amp。 }dist[v]=0；s[v]=true；for (int i=1。i=n。(4)重復操作(2)，(3)共n1次。令S=SU{j}。設(shè)S為已知最短路徑的終點的集合，它的初始狀態(tài)為空集。算法描述：(1)用帶權(quán)的鄰接矩陣c來表示帶權(quán)有向圖，c[i][j]表示弧vi，v上的權(quán)值。算法思路(Dijkstra)：設(shè)最短路長已知的終點集合為S，初始時v0∈S，其最短路長為0，然后用貪心選擇逐步擴充S：每次在VS中，選擇路徑長度值最小的一條最短路徑的終點x加入S。要計算從V的一點v0(源)到所有其他各頂點的最短路長度。所以n個字符的哈夫曼算法的計算時間為O(nlogn)。DeleteMin和Insert需O(logn)。in。（3）反復進行步驟（2）直到只剩一棵樹為止。（2）每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹：增加一個根結(jié)點將這兩棵樹作為左右子樹。鑒于該語言有這么優(yōu)秀的特點，該論文選擇C++為編程語言。5）通過模板等特征實現(xiàn)了類型和函數(shù)定義的參數(shù)化，把抽象又提升了一級。3）以繼承和派生的方式實現(xiàn)程序的重用機制，為程序的重用找到了一種可靠而方便的方式。2）抽象數(shù)據(jù)類型。其中包括：1）封裝和信息隱藏。在程序設(shè)計語言的歷史上，在所有比較成功的高級語言中，C++語言有著不少與眾不同的地方，它的這些特點既是人們愿意選擇它的原因，主要有：（1）C++語言是支持面向?qū)ο蟪绦蛟O(shè)計的最主要的代表語言之一。這種情形在結(jié)構(gòu)程序設(shè)計時期也曾出現(xiàn)，一些傳統(tǒng)的編程語言如Fortran、BASIC語言都開發(fā)了結(jié)構(gòu)化的新版本，不過其影響還是沒有超過Pascal和C語言。另一類則是傳統(tǒng)的重要編程語言向面向?qū)ο蟪绦蛟O(shè)計靠攏的結(jié)果，除了C++語言之外，幾乎所有成功的語言，包括Pascal語言、Ada語言、C語言和Fortran語言，都發(fā)展了它們自己的面向?qū)ο蟮男掳姹?，其中常見的有Ada9Borland開發(fā)的Turbo 、ObjectC、Forth等。第9章 貪心算法的C++實現(xiàn) C++語言概述據(jù)統(tǒng)計，目前世界上支持面向?qū)ο蟪绦蛟O(shè)計的語言已近百種，除了大多數(shù)是供研究用的非商業(yè)軟件外，具有強大競爭力OOP語言也很多，其中一類是以Smalltalk和EIFFEL語言為代表的新的面向?qū)ο笳Z言。（4）那么得出總的會場數(shù)目：S=5。經(jīng)過第一輪的篩選可知會場集合A1中包含：A1={E1，E4，E8，E11}。Table 81 The ploy in assembly room arrange table表81 會場活動安排表活動i1234567891011開始時間s（i）130535688212結(jié)束時間E（i）4567891011121314（1）根據(jù)貪心策略：現(xiàn)將1～12個活動的結(jié)束時間排序（為解說方便上表格已經(jīng)排好）排序可用快速排序。俗話所的好的：紙上得來終覺淺，絕知此事要躬行！那么讓我們舉個例子來進一步清晰化問題：下面表格有12個活動，并給出各個活動的開始時間與結(jié)束時間，那么請用上述貪心解法分析并求解最優(yōu)會場數(shù)目。 貪心算法（1）將所有活動按結(jié)束時間排序，得到活動集合E={e1，e2，…，en}；（2）先將e1選入結(jié)果集合A中，即A={e1}；（3）依次掃描每一個活動ei：如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei。如果這個輸入和當前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法就是貪心方法。輸入文件示例輸出文件示例 5 3 1 23 12 28 25 35 27 80 36 50 編碼分析根據(jù)會場安排問題的定義，首先將問題簡化為：找出兩個活動，若ei和ej滿足si≥fj或sj≥fi，則稱這兩個活動相容，即問題轉(zhuǎn)化為：要求找出最多相容會場集合A。時間以0點開始的分鐘計。第一行有1個正整數(shù)k，表示有k個待安排的活動。使相鄰頂點著有不同顏色的最小著色數(shù)，相應于要找的最小會場數(shù)。(這個問題實際上是著名的圖著色問題。第8章 會場安排問題 問題的提出假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。 原理分析 這個程序比較適合用堆，最優(yōu)用最小堆，最差用最大堆；以最優(yōu)合并為例：（1）使用各序列的長度建堆； （2）兩個最小的元素出堆，計算這兩序列合并需要的比較次數(shù)，該次數(shù)入堆； （3）重復（2），直到堆只剩下一個元素； 最后剩下的元素即為題目的解。試設(shè)計一個算法確定合并這個序列的最優(yōu)合并順序，使所需的總比較次數(shù)最少。第7章 最優(yōu)合并問題 問題的提出給定k個排好序的序列S1，S2…，Sk，用2路合并算法將這k個序列合并成一個序列。由于（b[1]，b[2]，……b[n]）是這段路程加油次數(shù)最少的一個滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個加油站加油時，b[1]=1，則（b[2]，b[3]，……b[n]）是從a[2]到a[n]這段路程上加油次數(shù)最少且這段路程上的加油站個數(shù)為（a[2]，a[3]，……a[n]）的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當于與起點具有相同的條件，每個過程都是相同且獨立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。該題設(shè)在加滿油后可行駛的N千米這段路程上任取兩個加油站Ａ、Ｂ，且Ａ距離始點比Ｂ距離始點近，則若在Ｂ加油不能到達終點那么在Ａ加油一定不能到達終點，因為m+Nn+N，即在B點加油可行駛的路程比在A點加油可行駛的路程要長nm千米，所以只要終點不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會選擇距離加滿油得點遠一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。 貪心算法正確性證明貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。每加一次油我們可以看作是一個新的起點，用相同的遞歸方法進行下去。我們可以假設(shè)不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個加油站，我們才加一次油。提出問題是解決的開始。不斷地將問題實例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個全局得最優(yōu)解。貪心算法將問題的求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目標推進。對于這個問題我們有以下幾種情況：設(shè)加油次數(shù)為k，每個加油站間距離為a[i]；i=0，1，2，3……n（1）始點到終點的距離小于N，則加油次數(shù)k=0；（2）始點到終點的距離大于N時：A 加油站間的距離相等，即ａ[i]=a[j]=L=N，則加油次數(shù)最少k=n；B 加油站間的距離相等，即ａ[i]=a[j]=LN，則不可能到達終點；C 加油站間的距離相等，即ａ[i]=a[j]=LN，則加油次數(shù)k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；D 加油站間的距離不相等，即ａ[i]！=a[j]，則加油次數(shù)k通過貪心算法求解。 編碼分析把兩加油站的距離放在數(shù)組中，a[1..k]表示從起始位置開始跑，經(jīng)過k個加油站，a[i]表示第i－1個加油站到第i個加油站的距離。旅途中有若干個加油站。 編碼該問題使用C++編程實現(xiàn)，其時間復雜性為O(n)，空間復雜性為O(n)。 因此，刪數(shù)問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。這與TA為問題T的最優(yōu)值相矛盾。而根據(jù)TA的定義可知：TA= TA’+xj*1Onj，而TB’TA’，因此有TB’+xj*1OnjTA’+xj*1Onj=TA。若A=(xj，A’)是原問題T的最優(yōu)解，則A’是子問題T’的最優(yōu)解，其最優(yōu)值為TA’。 因此刪數(shù)問題滿足貪心選擇性質(zhì)。 問題的貪心選擇性質(zhì) 先來證明該問題具有貪心選擇性質(zhì)，即對問題T刪除最近下降點的數(shù)xj后得到的N1是n一1位數(shù)是中最小的數(shù)。新問題和原問題相同，只是問題規(guī)模由n減小為n1，刪去的數(shù)字個數(shù)由k減少為k1。 本問題采用貪心算法求解，采用最近下降點優(yōu)先的貪心策略：即x1x2…xixj；如果xkxj，則刪去xj，即得到一個新的數(shù)且這個數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2…xixkxm…xn。設(shè)本問題為T，其最優(yōu)解A=(y1，y2…yk)表示依次刪去的k個數(shù)，在刪去k個數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計一個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。因此，綜合來看算法的時間復雜度為O(nlogn)。 算法結(jié)果分析程序主要是花費在對各顧客所需服務時間的排序和貪心算法，即計算平均服務時間上面。故只需對所有服務先按服務時間從小到大進行排序，然后按照排序結(jié)果依次進行服務即可。從以上貪心選擇及最優(yōu)子結(jié)構(gòu)性質(zhì)的證明，可知對最優(yōu)服務次序問題用貪心算法可求得最優(yōu)解。因此TB’+t(1)TA’+t(1)=TA，即存在一個比最優(yōu)值TA更短的總等待時間，而這與TA為問題T的最優(yōu)值相矛盾。若A是原問題T的最優(yōu)解，則A’={t(2)，…t(i)…t(n))是服務次序問題子問題T’的最優(yōu)解。 故最優(yōu)服務次序問題滿足貪心選擇性質(zhì)。 用反證法來證明：假設(shè)t(1)不是最小的，不妨設(shè)t(1)t(i)(i1)?；诖朔N選擇策略，對新問題T’，選擇n1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇后，原問題T變成了需對n1個顧客服務的新問題T’。 貪心選擇策略假設(shè)原問題為T，而我們已經(jīng)知道了某個最優(yōu)服務系列，即最優(yōu)解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；那么總等待時問，即最優(yōu)值為：TA=n*t(1)+(n1)*t(2)+…+(n+1j)*t(i)+…2*t(n1)+t(n)；由于平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。共有s處可以提供此項服務。 第4章 多處最優(yōu)服務次序問題 問題的提出設(shè)有n個顧客同時等待一項服務。缺點：該算法的時間復雜度為O(n2)。MST性質(zhì)確保此時的T是G的一棵MST。MST性質(zhì)保證了此邊是安全的。將T中U和TE分別看作紅點和紅邊集，VU看作藍點集。流程如下：（1）初始化操作：T←￠，q(1)←1，i從2到n作[p(i)←1，q(i)←di1]，k←1；（2）若k≥n，則作[輸出T，結(jié)束]否則作[min←∞，j從2到n作[若0q(i)min則作[min←q(i)h←j]]]；（3）T←T∪{h，p(h)}，q(h)←1；（4）j從2到n作[若dkjq(j)則作[q(j)←dkj，p(j)←h]]。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。編碼原理：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jvs，且c[i][j]最小的邊，將頂點j添加到S中。它較適合于稠密圖。缺點：當e=Ω(n2)時，Kruskal算法比Prim算法差，但當e=O(n2)時，Kruskal算法卻比Prim算法好得多。實現(xiàn)UnionFind所需的時間為O(eloge)或O(elog*e)。（2）初始化操作w←0，T←￠，k←0，t0；（3）若t=n1，則轉(zhuǎn)(6)，否則轉(zhuǎn)(4)（4）若構(gòu)成一回路，則作[k←k+1，轉(zhuǎn)(4)]（5）T←，w←w+wR，t←t+1，k←k+1，轉(zhuǎn)(3)（6）輸出T，w停止下面我們對這個算法的合理性進行證明：設(shè)在最小樹中，有邊vi，vj，連接兩頂點vi，vj，邊vi，vj的權(quán)為wp，若vi，vj加入到樹中不能保證樹的總長度最短，那么一定有另一條邊vi，vj或另兩條邊vi，vk，vk，vj，且wvi，vjwp或wwi，vkwvk，vjwp，因為vi，vq，vq，vp不在最小樹中，可知當vi，vq，vq，vp加入到樹中時已構(gòu)成回路，此時程序終止，因為vi，vk∈T，vk，vj∈T且wvi，vk+wvk，viwp，與程序流程矛盾。其中Wi≤Wi+1，然后在不構(gòu)成回路的條件下?lián)駜?yōu)取