電腦科學與技術學院
課程設計報告
題目全稱： 圖論tsp問題
學生學號： 161110218
姓名徐勤濤
指導老師： 周勇
問題闡述：旅行商問題，是指對於給定的 n 個城市，旅行商從某乙個城市出發不重複的訪問其餘各城市，最終回到出發城市。要求找到一條路線，使總的旅行路程最短。
用圖論來描述，就是給定乙個正權完全圖，找出它的總長最短的哈密頓迴路。
方法一：
使用便宜演算法求解：
1、遍歷整個矩陣，找到乙個路程和最短的三角形。
2、對三角形進行擴充，即：選擇一條邊，用該圈之外的點到該邊的路徑代替該邊，找到一種最好的解決方法，做完該圈所有邊後，找到一種最優解決方法，並擴充該邊。
3、重複步驟2，直到所有點都在這個圈裡。
結果截圖
程式的缺點：
1、只能對無向圖求解；
2、容錯性差，對一些情況無法求解。
3、時間複雜度高
方法二：
回溯法1．回溯法的定義：
回溯法是一種選優搜尋法，按選優條件向前搜尋，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
2. 回溯法的描述：
可用回溯法求解的問題p，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的乙個狀態空間e=，給定關於n元組中的乙個分量的乙個約束集d，要求e中滿足d的全部約束條件的所有n元組。其中si是分量xi的定義域，且 |si| 有限，i=1，2，…，n。
我們稱e中滿足d的全部約束條件的任一n元組為問題p的乙個解。
解問題p的最樸素的方法就是列舉法，即對e中的所有n元組逐一地檢測其是否滿足d的全部約束，若滿足，則為問題p的乙個解。但顯然，其計算量是相當大的。
我們發現，對於許多問題，所給定的約束集d具有完備性，即i元組（x1，x2，…，xi）滿足d中僅涉及到x1，x2，…，xi的所有約束意味著j（jj。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的乙個約束，就可以肯定，以（x1，x2，…，xj）為字首的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜尋它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比列舉法效率更高的演算法。
回溯法首先將問題p的n元組的狀態空間e表示成一棵高為n的帶權有序樹t，把在e中求問題p的所有解轉化為在t中搜尋問題p的所有解。樹t類似於檢索樹，它可以這樣構造：
設si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|si| =mi，i=1，2，…，n。從根開始，讓t的第i層的每乙個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。
照這種構造方式，e中的乙個n元組（x1，x2，…，xn）對應於t中的乙個葉子結點，t的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對於任意的0≤i≤n-1，e中n元組（x1，x2，…，xn）的乙個字首i元組（x1，x2，…，xi）對應於t中的乙個非葉子結點，t的根到這個非葉子結點的路徑上依次的i條邊的權分別為x1，x2，…，xi，反之亦然。特別，e中的任意乙個n元組的空前綴（），對應於t的根。
因而，在e中尋找問題p的乙個解等價於在t中搜尋乙個葉子結點，要求從t的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…，xn滿足約束集d的全部約束。在t中搜尋所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的策略逐步深入，即依次搜尋滿足約束條件的字首1元組（x1i）、字首2元組（x1，x2）、…，字首i元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題p的狀態空間樹；樹t上任意乙個結點被稱為問題p的狀態結點；樹t上的任意乙個葉子結點被稱為問題p的乙個解狀態結點；樹t上滿足約束集d的全部約束的任意乙個葉子結點被稱為問題p的乙個回答狀態結點，它對應於問題p的乙個解.
3． 回溯法的基本思想：
(1)針對所給問題，定義問題的解空間；
(2)確定易於搜尋的解空間結構；
(3)以深度優先方式搜尋解空間，並在搜尋過程中用剪枝函式避免無效搜尋。
用回溯法解題的乙個顯著特徵是在搜尋過程中動態產生問題的解空間。在任何時刻，演算法只儲存從根結點到當前擴充套件結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為o(h(n))。
而顯式地儲存整個解空間則需要o(2h(n))或o(h(n)!)記憶體空間.
4. 遞迴回溯與迭代回溯：
(1) 遞迴回溯:
回溯法對解空間作深度優先搜尋，因此，在一般情況下用遞迴方法實現回溯法。
void backtrack (int t)
其中，形式引數t表示遞迴深度，即當前擴充套件結點在解空間樹中的深度。n用來控制遞迴深度，即解空間樹的高度。當t>n時，演算法已搜尋到乙個葉結點。
此時，由函式output(x)對得到的可行解x進行記錄或輸出處理。演算法backtrack的for迴圈中f(n,t)和g(n,t)分別表示在當前擴充套件結點處未搜尋過的子樹的起始編號。h(i)表示在當前擴充套件結點處x[t]的第i個可選值。
函式constraint(t)和bound(t)表示在當前擴充套件結點處的約束函式和界限函式。函式contraint(t)返回的值為true則表示在當前擴充套件結點處x[1:t]的取值滿足問題的約束條件，否則不滿足問題的約束條件，可剪去相應的子樹。
函式bound(t)返回的值為true則表示在當前擴充套件結點處x[1:t]的取值尚未使目標函式越界，還需由backtrack(t+1)對其相應的子樹作進一步搜尋。否則，當前擴充套件結點處x[1:
t]的取值已使目標函式越界，可剪去相應的子樹。執行了演算法的for迴圈後，已搜尋遍當前擴充套件結點的所有未搜尋過的子樹。backtrack(t)執行完畢，返回t-1層繼續執行，對還沒有測試過的x[t-1]的值繼續搜尋。
當t=1時，若已測試完x[1]的所有可選值，外層呼叫就完全結束。顯然，這一搜尋過程是按深度優先的方式進行的。呼叫一次backtrack(1)即可完成整個回溯搜尋過程。
(2) 迭代回溯:
採用樹的非遞迴深度優先遍歷演算法，可將回溯法表示為乙個非遞迴迭代過程。
void iterativebacktrack ()
}else t--;
}}問題實驗結果及分析：
由實驗可知：
對於10個城市結點的輸入，對於上圖所示的鄰接矩陣，從執行結果可知，最短路徑為1→9→6→5→4→3→7→10→8→2，程式執行的最優值為156.
缺點及心得總結
1. 存在大量的重複搜尋：
在沒有特殊條件約束的情況下，構成tsp問題的無向帶權圖具有無向性，而周遊路線是環形封閉路線，因而，可以明顯看出，回溯法構成的解空間樹中存在著大量的重複截。n+1個連通的城市的tsp問題構成的解空間樹中，其葉子結點的數目為n！，而經過分析，重複的解路徑數目多達n！
/2，是整個解空間路徑的一半。在不考慮約束函式時，整個搜尋中有一半是無效搜尋，這大大降低了搜尋的效率。
2. 剪枝函式作用有限：
3．剪枝效果不穩定：
剪枝方法與解空間的路徑的排列順序有很大關係，這造成了剪枝函式的剪枝效果存在很大的不穩定性。如果費用較小的路徑其排列順序靠前，則剪枝函式發揮的效果就會好些，反之，效果就會差很多。
4．心得總結：
通過回溯法求解tsp問題的模擬與實現，使我對回溯法的認識更加深刻，雖然以前也接觸過這種方法，但實踐用得少，提高了自己動手程式設計的能力，增進了自身的知識。
圖論第二次作業
一 第四章 4.3 1 畫乙個有euler閉跡和hamilton圈的圖 2 畫乙個有euler閉跡但沒有hamilton圈的圖 3 畫乙個有hamilton圈但沒有euler閉跡的圖 4 畫乙個既沒有euler閉跡也沒有hamilton圈的圖 解 1 乙個有euler閉跡和hamilton圈的圖形如...
重力大作業
布格重力異常計算及資料處理與反演報告 姓名 班級 061113 學號 20111001192 指導老師 陳超 日期 2013.11.19 目錄 1 報告要求 2 資料初步校正 3 異常資料處理 1 壓制誤差和干擾 2 異常區分 3 異常轉換 4 異常資料解釋 5 報告總結 1 報告要求 根據在乙個地...
大作業格式要求
2010 2011第1學期 管理資訊系統大作業 案例名稱 溫州的虛擬企業 完 班級 08信管本一 學號 0811 姓名 邢浩 成績 評語教師簽名批閱日期 目錄1.不走尋常路 3 1.1 美特斯 邦威 3 1.2虛擬企業 3 2.成長的腳步 4 2.1資訊化建設的歷史 4 2.2資訊系統的構成 4 3...