算法與設(shè)計報告

中國地質(zhì)大學(xué)研究生課程論文封面課程名稱算法分析與設(shè)計教師姓名研究生姓名研究生學(xué)號研究生專業(yè)計算機技術(shù)所在院系計算機學(xué)院類別:B.碩士日期:2014年1月8日評語對課程論文的評語:平時成績：課程論文成績：總成績：評閱人簽名：注：1、無評閱人簽名成績無效；2、必須用鋼筆或圓珠筆批閱，用鉛筆閱卷無效；3、如有平時成績，必須在上面評分表中標(biāo)出，并計算入總成績。第一章算法導(dǎo)引1.1算法算法：用計算機求解問題的步驟、規(guī)則內(nèi)存空間——>初始狀態(tài)—————>終止?fàn)顟B(tài)有限狀態(tài)機算法的五個特性：輸出：一個算法產(chǎn)生一個或多個輸出從內(nèi)存——>認(rèn)識狀態(tài)輸入：一個算法有0個輸入或多個輸入inputa，b無二義性：算法的每一種運算必須要有確切的定義，即每一種運算應(yīng)該執(zhí)行何種動作必須是相當(dāng)清楚的、無二義性的（人和計算機、智能、確定的、機器；人機象棋：搜索）。能行性：（1）人能做，機器沒法做：能夠形式化，沒有辦法寫出算法（2）股票預(yù)測、彩票：模型有限性：可計算問題、有限的、可忍耐算法設(shè)計：自動化、自動程序設(shè)計、公式發(fā)現(xiàn)、公式挖掘、知識發(fā)現(xiàn)算法驗證：設(shè)計—表示（語言）—確認(rèn)—分析—測試程序1.2算法分析數(shù)學(xué)模型：1.串行算法，馮諾依曼機2.均勻存貯，存貯空間足夠大3.基本運算時間確定基本概念：1.問題規(guī)模：與參數(shù)有關(guān)2.頻率計數(shù)不分析算法具體執(zhí)行時間，分析問題復(fù)雜性：問題規(guī)模增大時的規(guī)律根據(jù)復(fù)雜性，將算法分為兩類： 1.多項式時間算法P：C，㏒n，n，n㏒n，n2（理論上可行，實際上也可行）2.指數(shù)時間算法NP：2n，n！，nn（理論上可行，實際上不可行）O(l)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)O(2n)<O(n!)<O(nn)解決方法：降低算法設(shè)計復(fù)雜度分析算法時間與問題規(guī)模：確定f(n)=O(g(n))上界和f(n)=Ω(g(n))下界1.3小結(jié)老師首先帶領(lǐng)我們回顧了本科階段的算法基礎(chǔ)相關(guān)知識，對于沒有系統(tǒng)學(xué)習(xí)過算法知識的我來說，更是一種知識入門，使我對這門課程有一些初步的了解。然后在對算法進行分析時，不分析算法具體的執(zhí)行時間，而是分析問題的復(fù)雜性（問題規(guī)模增大時的規(guī)律）。根據(jù)算法的特點可以將要求解的問題分為兩類：離散型和連續(xù)型。離散型問題需要討論問題的規(guī)模，如果是多項式時間復(fù)雜度則稱為P問題；如果是指數(shù)時間復(fù)雜度則稱為NP問題。對于連續(xù)型問題，需要討論算法的收斂性。第二章分治法2.1一般方法在求解問題時，為了將問題簡化，將實際問題轉(zhuǎn)變?yōu)閿?shù)學(xué)問題，將數(shù)學(xué)問題轉(zhuǎn)變?yōu)榇鷶?shù)問題，將代數(shù)問題轉(zhuǎn)變?yōu)榻夥匠虇栴}，將解方程問題轉(zhuǎn)變?yōu)榻饩€性方程組問題。求解問題的技術(shù)：1.化難為易的校正技術(shù)：例如求f(x)=a-x2=0；2.化粗為精的松弛技術(shù)：直接法，間接法，例如求圓的面積（割圓法）3.化大為小的縮減技術(shù)：f(n)=n*f(n-1)，f(1)=1問題性質(zhì)不變分治法的思想：將整個問題分為若干個小問題分而治之，問題的性質(zhì)不變。它的求解可用一個遞歸過程來表示。2.2二分檢索已知一個按非降次序排列的元素表a1,a2,…,an，要求判定某給定元素x是否在該表中出現(xiàn)。問題規(guī)模O(㏒n)2.3歸并分類（排序）Proceduremergesort(low,high)iflow<highthenmid|(low+high)/2」callmergesort(low,mid)callmergesort(mid+1,high)callmergesort(low,mid,high)endif問題規(guī)模O(n㏒n)2.4快速分類

反復(fù)對產(chǎn)生的文件進行劃分2.5斯特拉森矩陣乘法問題規(guī)模O(n3)2.6小結(jié)分治法是一種用空間換時間的技術(shù)，通過將大規(guī)模的問題劃分為小規(guī)模問題進行求解來降低求解難度，采用分治技術(shù)，問題首先必須能夠分解，而且分解后，問題的性質(zhì)并沒有發(fā)生變化。采用分治技術(shù)的目的只是并行算法設(shè)計，降低算法時間復(fù)雜度。在本章老師主要講解了分治法的基本遞歸求解，二分檢索、歸并分類、快速分類、斯特拉森矩陣乘法以及它們的時間復(fù)雜度的求解。第三章貪心法3.1一般方法概念：有n個輸入，問題的解是這n個輸入的一個子集，子集滿足一組條件（約束條件），子集可能有很多，滿足條件的子集叫做可行解，根據(jù)問題，人們設(shè)計一個函數(shù)，通過函數(shù)極值的計算，找到一個最優(yōu)的可行解，叫做最優(yōu)解。離散優(yōu)化問題連續(xù)函數(shù)優(yōu)化問題的分類：1.函數(shù)優(yōu)化問題：f(x)：高維、非線性、不連續(xù)、沒有明確的解析式；這類問題的求解方法有：解方程法、迭代法（最速下降法、共軛方向法、牛頓迭代法等）、隨機優(yōu)化（演化計算）等。2.模型參數(shù)優(yōu)化：此類問題的求解方法一般是：根據(jù)所給問題或者曲線，然后預(yù)測方程，對預(yù)測方程中的參數(shù)進行優(yōu)化求解。3.模型發(fā)現(xiàn)問題：自動程序設(shè)計，一般是輸入散點，要求給出擬合曲線。解決方法有基因表達(dá)式程序設(shè)計等。優(yōu)化問題分類：1.有約束優(yōu)化與無約束優(yōu)化2.線性優(yōu)化與非線性優(yōu)化3.靜態(tài)優(yōu)化與動態(tài)優(yōu)化（實時性）4.確定性優(yōu)化與隨機優(yōu)化5.單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化（矛盾或不協(xié)調(diào)的）貪心算法是一種分級處理方法，它根據(jù)問題性質(zhì)找到一種度量標(biāo)準(zhǔn)3.2背包問題部分背包問題的數(shù)學(xué)模型為：假設(shè)背包容量為m，有n件物品，每種物品i的重量為wi，其效益值為pi，問如何裝包，在背包的容量范圍內(nèi)裝出的值最多。xi∈{0,1}0/1背包問題xi∈[0,1]部分背包問題老師以書上的題目為例，根據(jù)按效益值由大到小的裝、按質(zhì)量由小到大的裝和按單位質(zhì)量效益值由大到小的裝（pi/wi）三種方法來尋找最優(yōu)解。經(jīng)過計算可知按單位質(zhì)量效益值由大到小的裝包獲得的結(jié)果最好。3.3最小生成樹問題設(shè)G=(V,E)是一個無向連通圖，如果G的生成子圖T=(V,E’)是一棵樹，則稱T是G的一棵生成樹。根據(jù)邊成本由小到大排序，找到最優(yōu)的生成樹。3.4小結(jié)貪心算法適用于求解從給定的n個輸入中找到一個滿足約束條件的子集的問題。滿足約束條件的子集稱為可行解，滿足目標(biāo)函數(shù)的可行解稱為最優(yōu)解。用貪心算法求解問題的關(guān)鍵在于找出求解問題的量度標(biāo)準(zhǔn)。本章老師主要講了貪心算法的適用領(lǐng)域，詳細(xì)講解了背包問題及最小生成樹的算法及其時間復(fù)雜度的求解。為了便于學(xué)生理解，老師聯(lián)系自己曾經(jīng)做過的畢業(yè)設(shè)計的凸多邊形問題，講述了是如何對問題進行分析和尋找解決方案的，而且講解了為何貪心算法無法用于求解凸多邊形問題，使同學(xué)們更好的領(lǐng)悟和體會貪心法的應(yīng)用范圍。第四章動態(tài)規(guī)劃4.1一般方法求解優(yōu)化問題的方法：1.多階段決策：可以把問題分成若干階段2.最優(yōu)性原理：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列（找到一個遞推關(guān)系式）。4.2多段圖問題多段圖G=(V,E)，求源點s到匯點t的最短路徑設(shè)cost(i,j)表示從源點到第i個階段的j點的最短路徑：設(shè)Bcost(i,j)表示從第i個階段的j點到匯點的最短路徑：4.3每對結(jié)點之間的最短路徑單源最短路徑問題O(n2)任意兩點間最短路徑問題O(n3)設(shè)Ak代表i，j兩個結(jié)點間考慮了1-k結(jié)點時最短路徑，A0(i,j)就是成本矩陣A0(i,j)=C(i,j)An(i,j)=min{An-1(i,j),An-1(i,n)+An-1(n,j)}Ak(i,j)=min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)}4.4最優(yōu)二分檢索樹設(shè)a1<a2<a3<…<an，n個符號a1a2a3…anP(1)P(2)P(3)…P(n)E0E1E2E3En-1EnQ(0)Q(1)Q(2)Q(3)Q(n-1)Q(n)檢索成本的計算方法：表示的是單倍成本/單倍的概率之和總成本：比較運算n次——耗時C(i,j)代表構(gòu)造的二分檢索樹最優(yōu)成本 aa1a2…anE0E1E2En-1Enaai+1ai+2…ajEiEi+1Ei+2Ej-1Ej4.5矩陣連乘問題：，假設(shè)r0=10，r1=30，r2=70，r3=1，r4=200，求最小計算量。矩陣連乘問題滿足以下公式：，根據(jù)分析，得到遞推公式：D(i,j)表示最優(yōu)的次數(shù)據(jù)此得到結(jié)果：0210002400440010210081001201400033304.60/1背包問題設(shè)fj(x)表示將第1至j件物品裝入容量為x的包所獲得的最大效益值。fj-1(x)表示前面已裝滿的情況下的效益值，fj(x-wj)+Pj表示將第j件物品裝進去后的效益值，兩者取最大者為最終結(jié)果。老師以書上題目為例，為大家講解整個求解過程，題目為：n=3，（w1,w2,w3）=（2,3,4），（p1,p2,p3）=（1,2,5），M=6。部分背包問題同樣的n件物品，xi∈{x|0≤x≤1}，部分背包情況下獲得的效益值為P1，0/1背包情況下獲得的效益值為P2，部分背包情況下減去小數(shù)部分的效益值為P3，三者滿足關(guān)系P1≥P2≥P3。4.7TSP問題有n個城市，城市之間距離用C(i,j)表示，從編號為1的城市經(jīng)過其他的n-1個城市一次且一次，回到城市1，路徑最短。圖中任意兩點間最短路徑O(n3)靜態(tài)TSP：C(n,n)不變（O(n!)）動態(tài)TSP：Ct(n,n)隨時間變化，實時（動態(tài)）多目標(biāo)TSP：C(n,n)，Cij={a1,a2}，速度快、成本低設(shè)g(i,S)代表從i點出發(fā)經(jīng)過S中的（S是城市編號的集合）所有城市后回到1的最大路徑，最終求：老師以書上題目為例，利用上面給出公式，計算得出結(jié)果。4.8子集和數(shù)問題：設(shè)有n個正整數(shù){a1,a2,…,an}，求和為M的一個子集。4.9調(diào)度問題：1.相同處理機的調(diào)度設(shè)有{t1,t2,…,tn}有相同的設(shè)備兩臺，讓你給出調(diào)度模式調(diào)度這n個任務(wù)2.流水線調(diào)度問題兩個設(shè)備的流水線調(diào)度問題：P問題（排序問題）三個設(shè)備的流水線調(diào)度問題：NP問題S={t1,t2,…,tn}，g(S,0)可得遞推公式：（ai,t都結(jié)束才可以調(diào)度bi）根據(jù)問題所要求的解的不同，可以將這些問題分為三類：1.求解整數(shù)規(guī)劃類問題。要求自變量為整數(shù)，即最終結(jié)果是要求給出整數(shù)解集合的一個選擇。例如：多段圖問題和0/1背包問題。2.求解最優(yōu)結(jié)構(gòu)。要求最終結(jié)果是給出一棵最優(yōu)二分樹的結(jié)構(gòu)。例如：最優(yōu)二分檢索樹和矩陣連乘問題。3.序列優(yōu)化問題。要求最終結(jié)果是找出最優(yōu)的一個排列。例如：TSP問題和調(diào)度問題。4.10小結(jié)動態(tài)規(guī)劃方法一般用來求解優(yōu)化問題。使用該方法求解的問題主要有兩個特點：多階段決策，可以把問題分為若干個階段；滿足最優(yōu)性原理，當(dāng)前狀態(tài)和決策只和它前一階段的狀態(tài)有關(guān)，和前一階段的狀態(tài)和決策如何得到無關(guān)。用動態(tài)規(guī)劃求解問題，關(guān)鍵在于找到求解問題的一個遞推關(guān)系式。本章內(nèi)容很多，同時又很重要，老師詳細(xì)的為我們講解了如何利用動態(tài)規(guī)劃技術(shù)求解多段圖問題、任意兩點間最短路徑問題、最優(yōu)二分檢索樹、矩陣連乘問題、0/1背包問題、TSP問題和調(diào)度問題，并詳細(xì)講解了如何構(gòu)造與使用遞推關(guān)系式來解決這些問題。對于每一個問題，老師都通過講解書上的實例來加深我們對算法理解和認(rèn)識，也讓我們更清楚如何利用算法解決相關(guān)問題。用動態(tài)規(guī)劃技術(shù)解決矩陣連乘問題是老師課外拓展的內(nèi)容。老師還向我們簡單介紹了子集和數(shù)問題，它與0/1背包問題、TSP問題、3-Sat問題都屬于NP問題，想要求解它們，就要找到合適的方法將它們化簡為P問題。另外，對于本章用動態(tài)規(guī)劃解決的幾類問題，老師也帶我們進行了歸類總結(jié)，更加深了我們對動態(tài)規(guī)劃技術(shù)的印象。第五章基本檢索與周游方法5.1一般方法1.樹的檢索二叉樹檢索（先根、中根、后根）以下圖為例：寬度優(yōu)先：=1\*GB3①=2\*GB3②③④⑤⑥⑦⑧深度優(yōu)先：=1\*GB3①=2\*GB3②④⑧⑤⑥③⑦5.2雙連通分圖和深度優(yōu)先檢索雙連通、單連通、關(guān)節(jié)點識別關(guān)節(jié)點：根節(jié)點有幾個兒子葉子節(jié)點肯定不是關(guān)節(jié)點中間節(jié)點：從它每個兒子出發(fā)往下走，能經(jīng)過邊到達(dá)它的祖先節(jié)點。計算每一個節(jié)點的深度優(yōu)先數(shù)DFN(x)，最低深度優(yōu)先數(shù)L(x)。5.3對策樹（博弈樹）每個節(jié)點，狀態(tài)評估函數(shù)E(x)max-min過程max(f)A；min(f)Bα截斷：如果一個求最小值位置的值被判斷為小于或等于它父親的α值，那么可以停止生成這個求最小值位置的其余兒子的值。β截斷：如果一個求最大值位置的值被判斷為大于或等于它父親的β值，那么可以停止生成這個求最大值位置的其余兒子的值。α-β截斷：對于任一結(jié)點x，設(shè)B是該結(jié)點父親的B值且D=-B，那么如果x的值判斷為大于或等于D，則可以停止生成x的其他兒子。老師以書上題目為例，通過一種假想的博弈游戲，為我們講解了α-β截斷的使用方法。5.4小結(jié)基本檢索與周游方法一般是針對樹、圖這樣的數(shù)據(jù)結(jié)構(gòu)。對數(shù)據(jù)結(jié)構(gòu)的操作即為算法的設(shè)計與分析。老師首先帶領(lǐng)大家回顧了樹的搜索策略和圖的周游策略。老師通過一個實例詳細(xì)講解了如何將一個已有的圖變?yōu)橐粋€雙連通圖；詳細(xì)講解了決策樹問題，決策樹要求非常有限的結(jié)點和層數(shù)；對于有限次博弈游戲所有可能的實際戰(zhàn)例或者有限步之內(nèi)的戰(zhàn)例可以用一顆決策樹表示，每一個結(jié)點表示一種戰(zhàn)例，而對于一些博弈游戲（例如：國際象棋）來說，構(gòu)造的決策樹相當(dāng)大，因此我們只需要構(gòu)造有限步驟的決策樹，并且用一些剪枝策略減去對自己不利的部分，這里老師詳細(xì)講解了α-β剪枝算法。第六章回溯法6.1一般方法在本章內(nèi)容開始時，老師將問題的求解技術(shù)進行了總結(jié)：對于連續(xù)問題，有連續(xù)性、容易判斷大小，可以利用搜索技術(shù)、領(lǐng)域變換規(guī)則進行求解；對于離散問題（子集和數(shù)），通過初始狀態(tài)引導(dǎo)出最終狀態(tài)，需要的方法更復(fù)雜。離散問題連續(xù)問題問題子集和數(shù)x2-2=0問題狀態(tài)(0,0,0,0)(1)求解方法貪心算法（量度標(biāo)準(zhǔn)）動態(tài)規(guī)劃（遞推關(guān)系式）通過構(gòu)造解空間樹直接法（數(shù)學(xué)分析）通過領(lǐng)域變換（迭代法）根據(jù)問題的性質(zhì)和規(guī)范函數(shù)要求，找出限界函數(shù)、問題的上下界深度優(yōu)先+限界函數(shù)=回溯法寬度優(yōu)先+限界函數(shù)=分枝限界法1.問題描述：求一個n元組(x1,x2,…,xn)，xi∈Si，||Si||=ni。2.問題狀態(tài)：一個元組，要求的參數(shù)的集合有兩種表示方法：元組長度固定：(0,0,0,0)；元組長度不定：(a1),(a1,a4)；3.解空間樹（狀態(tài)空間樹）：用樹的結(jié)構(gòu)表示4.解狀態(tài)：與表示方法有關(guān)5.答案狀態(tài)6.20/1背包問題老師以書上題目為例，P=(11,21,31,33,43,53,55,65)，w=(1,11,21,23,33,43,45,55)。下圖為回溯法求解0/1背包問題所生成的樹：6.3小結(jié)回溯法一般用于求解n元組問題。求解方法有兩種：部分解和完全解。所需要的求解結(jié)構(gòu)為狀態(tài)空間樹結(jié)構(gòu)，將回溯過程用樹的形式表達(dá)。老師以0/1背包問題為例講解了如何利用回溯法求解問題，并講解了樹結(jié)點的得出，以及剪枝（限界函數(shù)）的策略。在回溯狀態(tài)空間樹結(jié)構(gòu)中加入限界函數(shù)，可以盡可能少的檢索樹結(jié)構(gòu)結(jié)點，盡快找到解結(jié)點。第七章分枝-限界法7.1一般方法(x1,x2,…,xn)，xi∈Si狀態(tài)及狀態(tài)轉(zhuǎn)移深度優(yōu)先寬度優(yōu)先計算：基于規(guī)則的一組符號變換過程7.2LC分枝-限界求解老師以書上題目為例，通過0/1背包問題和TSP問題，為我們講解了LC分枝-限界方法：對于0/1背包問題，我們利用兩個函數(shù)來為成本函數(shù)c(x)限界，前者為將包裝滿時的成本估計函數(shù)，后者為舍棄分?jǐn)?shù)尾時的上界函數(shù)，使它們對于每個結(jié)點x，都滿足以下式子：利用這兩個函數(shù)，可以獲得最優(yōu)的結(jié)果。對于TSP問題，同樣是利用兩個函數(shù)限界，結(jié)合成本矩陣和歸約矩陣獲得最終的結(jié)果。搜索方法（狀態(tài)轉(zhuǎn)移方法）確定性方法：1.解析法：非線性方程組求解直接法：基于梯度、grad導(dǎo)數(shù)間接法：變成線性方程組、迭代2.規(guī)劃：整數(shù)規(guī)劃：0/1背包動態(tài)規(guī)劃：多段圖3.枚舉法（遍歷）寬度優(yōu)先深度優(yōu)先4.剪枝法基于狀態(tài)樹概念：α-β截斷、限界函數(shù)隨機性方法：盲目搜索：概率算法導(dǎo)向搜索：演化算法、禁忌搜索7.3小結(jié)分枝-限界方法是利用廣度優(yōu)先的方法來構(gòu)造狀態(tài)空間樹。老師首先以0/1背包問題為例講解如何通過分枝-限界法構(gòu)造一個狀態(tài)空間樹，計算每個結(jié)點的上界和下界，以及如何生成新結(jié)點。然后又以TSP問題為例講解了如何利用分枝-限界法，結(jié)合構(gòu)造狀態(tài)空間樹、成本矩陣和歸約矩陣，找到解決TSP問題的一個最優(yōu)組合排列。比較動態(tài)規(guī)劃方法與分枝-限界法解決TSP問題的效果，雖然兩種方法計算復(fù)雜度的最壞情況是一樣的，但是對于許多具體實例而言，分枝-限界算法要比動態(tài)規(guī)劃技術(shù)所用的時間少得多。第八章程序設(shè)計因為本人曾在完成畢業(yè)設(shè)計時了解過有關(guān)TSP問題的求解方法，因此，當(dāng)老師布置本課程的程序設(shè)計題目時，我選擇了利用動態(tài)規(guī)劃技術(shù)求解TSP問題。根據(jù)動態(tài)規(guī)劃算法需要求g(i,S)。以4個城市為例，需要求出g(i,S)，i取值從1到3，S取值為{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}},也就是集合{1,2,3}的所有子集合，而所有的子集合可以用二進制數(shù)表示。如果數(shù)在集合中，為二進制1，否則為0，數(shù)字大的在高位，如{1,2,3}表示成111，也就是7。{3}表示成100，也就是4。這樣可以把集合映射成數(shù)組的下表，同時通過C語言的位操作來完成判斷元素是否在集合中等操作，所以算法的過程就是計算二維表（n*2^(n-1)）的過程。源代碼如下：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#defineMAXCOST99999intmin(intfirst,intsecond){ returnfirst<second? first:second;}intmain(intargc,char*argv[]){ intnCity=0; printf("pleaseenterthenumberofcities:\n"); scanf("%d",&nCity); int**cost=(int**)malloc(sizeof(int*)*nCity); for(inti=0;i<nCity;i++){ cost[i]=(int*)malloc(sizeof(int)*((int)pow(2.0,nCity-1))); memset(cost[i],0,sizeof(int)*((int)pow(2.0,nCity-1))); } int**distance=(int**)malloc(sizeof(int*)*nCity); for(inti=0;i<nCity;i++){ distance[i]=(int*)malloc(sizeof(int)*nCity); } printf("pleaseenterthedistancebetweencities:\n"); for(inti=0;i<nCity;i++){ for(intj=0;j<nCity;j++){ scanf("%d",&distance[i][j]); } } //初始化g(i,{}) for(inti=1;i<nCity;i++){ cost[i][0]=distance[i][0]; } for(inti=1;i<(1<<(nCity-1))-1;i++){ for(intj=1;j<nCity;j++){ if(((1<<(j-1)&i)>>(j-1))==0){//判斷i是否在S中，防止重復(fù) //求出S中包含的元素和元素的個數(shù) intcounter=0; int*set=(int*)malloc(sizeof(int)*nCity); for(intk=0;k<nCity-1;k++){ if(((i>>k)&1)==1){ set[counter]=k+1; counter++; } } intmincost=MAXCOST; for(intk=0;k<counter;k++){ //求出除去i,j后集合中元素映射到數(shù)組的下標(biāo)，根據(jù)g(i,S)=min(c(i,j)+g(j,{S-J}) intnCitytoSet=0; for(intl=0;l<counter;l++){ if(set[l]!=set[k]){ nCitytoSet+=(1<<(set[l]-1)); } } mincost=min(mincost,(distance[j][set[k]]+cost[set[k]][nCitytoSet])); } cost[j][i]=mincost; } } } //根據(jù)g(i,S)=min(c(i,j)+g(j,{S-J})，算出經(jīng)過g(0,{1,2,3,...N-1}),也就是經(jīng)過節(jié)點0返回節(jié)點0的最小代價 intmincost=MAXCOST; for(inti=1;i