目錄

一、實驗目的

二、實驗環境

三、實驗內容

四、核心代碼

五、記錄與處理

六、思考與總結

七、完整報告和成果文件提取鏈接

一、實驗目的

????????掌握分支界限求解問題的思想；針對不同的問題，能夠利用分支界限法進行問題拆分和求解以及時間復雜度分析，并利用JAVA/C/C++等編程語言將算法轉換為對應的程序上機運行（語言不限）。

二、實驗環境

????????1、機房電腦? Window11

????????2、Eclipse/devc++

三、實驗內容

實驗要求：

①分支限界求解問題的策略及思路；（BFS廣度優先搜索）

分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。

【求解過程】

在分支限界法中，每一個活結點只有一次機會成為擴展結點。

1.活結點一旦成為擴展結點，就一次性產生其所有兒子結點。當前點從活動節點隊列中刪去；

2.兒子結點中，不可行解或非最優解結點刪去，其余兒子結點被加入活結點列表中；

3.從活結點表中取下一結點成為當前擴展結點；

4.重復上述結點擴展過程。直至活動結點列表為空；

活結點擴展順序：先進入活結點列表，優先變為擴展節點

?? 活結點存儲結構是隊列Queue

②分析與回溯法求解問題的異同；

分支限界法與回溯法的不同之處：

(1)求解目標：

?回溯法：一般是找出解空間樹中滿足約束條件的所有解，也可找最優解的樹；

分支限界法：找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。

(2)搜索方式的不同：

回溯法：以深度優先的方式搜索解空間樹；

分支限界法：以廣度優先或以最小耗費優先的方式搜索解空間樹。

③掌握基于分支限界的TSP旅行商問題的設計求解；

針對如下問題，給出基于優先隊列分支限界的算法設計策略。

如下4個城市，城市間的耗費如圖。從城市1出發進行遍歷。尋找最短遍歷路徑。

首先分析該問題的解空間樹，它是一棵排列樹:

它的特點如下：

(1)指定一個城市作為出發城市

(2)把第n-1層結點看做葉子結點

1.算法開始時創建一個最小堆，用于表示活結點優先隊列。

2.堆中每個結點的優先級為：cc+lcost，cc為出發城市到當前城市的路程，lcost是當前頂點最小出邊+剩余頂點最小出邊和

3.每次從優先隊列中取出一個活結點成為擴展結點

4. 當s=n-2時，擴展出的結點是排列樹中某個葉子結點的父結點。如該葉結點相應一條可行回路且費用小于當前最優解bestc，則將該結點插入到優先隊列中，否則舍去該結點

5. 當s<n-2時，產生當前擴展結點的所有兒子結點。計算可行兒子。結點的優先級cc+lcost及相關信息。當cc+lcost<bestc時，將這個可行兒子結點插入到活結點優先隊列中。

④對上述算法進行時間復雜性分析，分析時間復雜度對比。

????????回溯法是一種通過探索所有可能的候選解來找出所有解的算法。在解決TSP問題時，回溯法會生成一棵解空間樹，其中每個節點代表一個可能的城市訪問順序，葉子節點代表一個完整的訪問序列。

????? 對于n個城市，解空間樹是一個n-1層的完全二叉樹，這棵樹的節點總數是(n-1)!

????? 在最壞情況下，回溯法需要遍歷解空間樹的所有節點來找到最短路徑。因此，時間復雜度是O((n-1)!)，但由于(n-1)!與n!相差不大，通常可以簡化為O(n!)。

????? 分支限界法解決TSP問題的時間復雜度在最壞情況下也是O(n!)，然而，在實際應用中，通過剪枝操作，分支限界法大大減少了實際搜索空間，因此平均運行時間優于蠻力算法。

四、核心代碼

//用這種簡單粗暴的方法獲取必定小于結果的一個值
void get_low()
{//取每行最小值之和作為下界low = 0;for (int i = 1; i <= n; i++){//創建一個等同于map的臨時數組，可用memcpyint tmpA[MAX_N];for (int j = 1; j <= n; j++){tmpA[j] = cost[i][j];}sort(tmpA + 1, tmpA + 1 + n);//對臨時的數組進行排序low += tmpA[1];}
}
int get_lb(Node p)
{int ret = p.sumv * 2;//路徑上的點的距離的二倍int min1 = INF, min2 = INF;//起點和終點連出來的邊for (int i = 1; i <= n; i++){if (!p.visited[i] && min1 > cost[i][p.s]){min1 = cost[i][p.s];}}ret += min1;for (int i = 1; i <= n; i++){if (!p.visited[i] && min2 > cost[p.e][i]){min2 = cost[p.e][i];}}ret += min2;for (int i = 1; i <= n; i++){if (!p.visited[i]){min1 = min2 = INF;for (int j = 1; j <= n; j++){if (min1 > cost[i][j])min1 = cost[i][j];}for (int j = 1; j <= n; j++){if (min2 > cost[j][i])min2 = cost[j][i];}ret += min1 + min2;}}return (ret + 1) / 2;
}

五、記錄與處理

此處定義INF無窮大為100000，即對角線為INF

六、思考與總結

通過分析回溯法和分支限界法的時間復雜度以及實際運行效率，我深刻認識到了算法優化的重要性。我學會了如何使用限界函數和剪枝策略來減少搜索空間，從而提高算法的運行效率。

七、完整報告和成果文件提取鏈接

完整可運行代碼以及相關實驗報告以下鏈接可獲取：
鏈接: https://pan.baidu.com/s/1iss6-C2nxZQGkEpo-WDn0A?pwd=g5cg 提取碼: g5cg?