分支限界法 tsp java_基于分支限界法的旅行商问题（TSP）一
//分支限界法
#include#include#include#include
const int INF = 100000;const int MAX_N = 22;using namespacestd;//n*n的一個矩陣
intn;int cost[MAX_N][MAX_N];//最少3個點，最多MAX_N個點
structNode
{bool visited[MAX_N];//標記哪些點走了
int s;//第一個點
int s_p;//第一個點的鄰接點
int e;//最后一個點
int e_p;//最后一個點的鄰接點
int k;//走過的點數
int sumv;//經過路徑的距離
int lb;//目標函數的值(目標結果)
bool operator
}
};
priority_queue pq;//創建一個優先隊列
int low, up;//下界和上界
bool dfs_visited[MAX_N];//在dfs過程中搜索過//確定上界,利用dfs(屬于貪心算法)，貪心法的結果是一個大于實際值的估測結果
int dfs(int u, int k, int l)//當前節點，目標節點，已經消耗的路徑
{if (k == n) return l + cost[u][1];//如果已經檢查了n個節點，則直接返回路徑消耗+第n個節點回歸起點的消耗
int minlen =INF, p;for (int i = 1; i <= n; i++)
{if (!dfs_visited[i] && minlen > cost[u][i])//取與所有點的連邊中最小的邊
{
minlen= cost[u][i];//找出對于每一個節點，其可達節點中最近的節點
p =i;
}
}
dfs_visited[p]= true;//以p為下一個節點繼續搜索
return dfs(p, k + 1, l +minlen);
}voidget_up()
{
dfs_visited[1] = true;//以第一個點作為起點
up = dfs(1, 1, 0);
}//用這種簡單粗暴的方法獲取必定小于結果的一個值
voidget_low()
{//取每行最小值之和作為下界
low = 0;for (int i = 1; i <= n; i++)
{//創建一個等同于map的臨時數組，可用memcpy
inttmpA[MAX_N];for (int j = 1; j <= n; j++)
{
tmpA[j]=cost[i][j];
}
sort(tmpA+ 1, tmpA + 1 + n);//對臨時的數組進行排序
low += tmpA[1];
}
}intget_lb(Node p)
{int ret = p.sumv * 2;//路徑上的點的距離的二倍
int min1 = INF, min2 = INF;//起點和終點連出來的邊
for (int i = 1; i <= n; i++)
{//cout << p.visited[i] << endl;
if (!p.visited[i] && min1 >cost[i][p.s])
{
min1=cost[i][p.s];
}//cout << min1 << endl;
}
ret+=min1;for (int i = 1; i <= n; i++)
{if (!p.visited[i] && min2 >cost[p.e][i])
{
min2=cost[p.e][i];
}//cout << min2 << endl;
}
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;
}intsolve()
{//貪心法確定上界
get_up();//取每行最小的邊之和作為下界//cout << up << endl;//test
get_low();//cout << low << endl;//test//設置初始點,默認從1開始
Node star;
star.s= 1;//起點為1
star.e = 1;//終點為1
star.k = 1;//走過了1個點
for (int i = 1; i <= n; i++)
{
star.visited[i]= false;
}
star.visited[1] = true;
star.sumv= 0;//經過的路徑距離初始化
star.lb = low;//讓目標值先等于下界
int ret = INF;//ret為問題的解
pq.push(star);//將起點加入隊列
while(pq.size())
{
Node tmp=pq.top();pq.pop();if (tmp.k == n - 1)//如果已經走過了n-1個點
{//找最后一個沒有走的點
intp;for (int i = 1; i <= n; i++)
{if (!tmp.visited[i])
{
p= i;//讓沒有走的那個點為最后點能走的點
break;
}
}int ans = tmp.sumv + cost[p][tmp.s] + cost[tmp.e][p];//已消耗+回到開始消耗+走到P的消耗//如果當前的路徑和比所有的目標函數值都小則跳出
if (ans <=tmp.lb)
{
ret=min(ans, ret);break;
}//否則繼續求其他可能的路徑和，并更新上界
else{
up= min(up, ans);//上界更新為更接近目標的ans值
ret =min(ret, ans);continue;
}
}//當前點可以向下擴展的點入優先級隊列
Node next;for (int i = 1; i <= n; i++)
{if (!tmp.visited[i])
{//cout << "test" << endl;
next.s = tmp.s;//沿著tmp走到next，起點不變
next.sumv = tmp.sumv + cost[tmp.e][i];//更新路徑和
next.e = i;//更新最后一個點
next.k = tmp.k + 1;//更新走過的頂點數
for (int j = 1; j <= n; j++) next.visited[j] = tmp.visited[j];//tmp經過的點也是next經過的點
next.visited[i] = true;//自然也要更新當前點//cout << next.visited[i] << endl;
next.lb = get_lb(next);//求目標函數//cout << next.lb << endl;
if (next.lb > up) continue;//如果大于上界就不加入隊列
pq.push(next);//否則加入隊列//cout << "test" << endl;
}
}//cout << pq.size() << endl;BUG:測試為0
}returnret;
}intmain()
{
cin>>n;for (int i = 1; i <= n; i++)
{for (int j = 1; j <= n; j++)
{
cin>>cost[i][j];if (i ==j)
{
cost[i][j]=INF;
}
}
}
cout<< solve() <
}/*測試
5
100000 5 61 34 12
57 100000 43 20 7
39 42 100000 8 21
6 50 42 100000 8
41 26 10 35 100000
36
請按任意鍵繼續. . .*/
總結
以上是生活随笔為你收集整理的分支限界法 tsp java_基于分支限界法的旅行商问题（TSP）一的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java中的gui_java gui快速
- 下一篇： 安卓曲线图（安卓曲线）