【整理】旅行商问题(traveling salesman problem，TSP)

本文主要是介绍【整理】旅行商问题(traveling salesman problem，TSP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

旅行商

一个旅行商由某市出发，经过所有给定的n个城市后，再

回到出发的城市。除了出发的城市外，其它城市只经过一

回。这样的回路可能有多个，求其中路径成本最小的回路。

蛮力【穷举】

【例4-4】旅行商问题——排列树

计算模型

(1) 存储图G(V, E)。以邻接矩阵的方式存储，设计如下：

(2)计算设起始点下标为0

 生成排列树。设解空间为a，则其解空间的计算过程可描述为：

 求回路代价。设sumi 是并入第i个结点的代价：

sumi并入第i个结点的代价= sum_i-1代入第i-1个结点的代价 + 边（i-1到i)

分支限界法：

穷举法代码：

#include<iostream>
using namespace std;//蛮力（穷举）
//邻接矩阵
int n = 4;
int edge[4][4] = { 0,8,5,4,8,0,7,3,5,7,0,1,4,3,1,0 };
int vertex[4] = { 'a','b','c','d' };
int a[] = { 0,1,2,3 };//解空间
int minvalue = 10000;//当前最小值
int path[4] = { 0 };//当前解的路径
int minpath[4] = { 0 };//最优解的路径void showpath(int a[])
{cout << "showpath:";for (int i = 0; i < n; i++){cout << a[i] << "\t";}//回到终点cout <<a[0]<< endl;
}
void copypath(int minpath[])
{for (int i = 0; i < n; ++i){minpath[i] = a[i];}
}
int cost()//求当前路径的权值
{int sum = edge[0][a[0]];int i;for (i = 1; i < n; ++i){sum += edge[a[i - 1]][a[i]];}sum += edge[a[i - 1]][0];//回到0return sum;
}
//递归
void EnumTSP(int i)
{int k, temp;if (i == n - 1)//最后一个结点，递归出口{if (cost() < minvalue)//当前解的权值 < 当前最小{minvalue = cost();//更新最小权值copypath(minpath);//赋值到最优解路径}}else{for (int k = i; k < n; k++){//全排列temp = a[i]; a[i] = a[k]; a[k] = temp;//下一层递归EnumTSP(i + 1);//恢复现场temp = a[i]; a[i] = a[k]; a[k] = temp;}}
}int	main()
{EnumTSP(0);//从第0层开始showpath(minpath);cout <<"minvalue:" << minvalue << endl;return 0;
}

回溯法代码：

#include<iostream>
#include<queue>
using namespace std;

//分支限界法
typedef struct node {
   bool vis[20];
   int st;//起点
   int ed;//终点
   int k;//走过的点数
   int sumv;//走过的路径距离
   int lb;//目标函数的值下界
   int path[20];//当前路径
   //运算符重载
   bool operator<(const node& p)
   {
       return lb > p.lb;
   }
}node;

const int INF = 10000000; //表示无穷大
int low, up, n, used[20];
int cost[20][20] = { {4,2,6,9},{4,7,8,10}, {2,7,5,3}, {6,8,5,4}, {9,10,3,4} };
char city[20] = {'A','B','C','D','E'};
priority_queue<node>q;//优先级队列
node answer;//答案最优解

//求上界
// 当前结点下标，第几层，当前路径长度
int get_up_digui(int v, int j, int len)
{
   int minE = INF;
   int pos;
   if (j == n)//结束
   {
       return len + cost[v][1];
   }
   //v的邻接边中最短
   for (int i = 1; i <= n; i++)//从1开始
   {
       //未访问
       if (used[i] == 0 && minE > cost[v][i])
       {
           minE = cost[v][i];
           pos = i;
       }
   }
   //设为访问
   used[pos] = 1;
   return get_up_digui(pos, j + 1, len + minE);
}
//求上界
void get_up()//求当前上界
{
   used[1] = 1;//从1开始访问
   up = get_up_digui(1, 1, 0);
}
//下界
void get_low()//求当前下界
{
   low = 0;
   //最短两条边
   for (int i = 1; i <= n; i++)
   {
       int temp[20];
       for (int j = 1; j <= n; j++)
       {
           temp[j] = cost[i][j];
       }
       sort(temp + 1, temp + 1 + n);//从1开始
       low += temp[1]+temp[2];
   }
   low = low / 2;
   //其他顶点最短两条边

}

//结点所在分支的下界
int get_lb(node p)
{
   int res = p.sumv * 2;//已遍历的城市的距离
   int min1 = INF, min2 = INF, pos;
   //从起点到最近未遍历的城市的距离
   for (int i = 1; i <= n; i++)
   {
       if (p.vis[i] == 0 && min1 > cost[p.st][i])
       {
           min1 = cost[p.st][i];
           pos = i;
       }
   }
   res += min1;
   //从离开结点到最近未便利城市的距离
   for (int i = 1; i <= n; i++)
   {
       if (p.vis[i] == 0 && min2 > cost[i][p.ed])
       {
           min2 = cost[i][p.ed];
           pos = i;
       }
   }
   res += min2;
   //进入并离开每个未遍历城市的最小成本
   for (int i = 1; i <= n; i++)
   {
       if (p.vis[i] == 0)
       {
           int temp[n];
           min1 = min2 = INF;
           for (int j = 1; j <= n; j++)
           {
               temp[j] = cost[i][j];
           }
           sort(temp + 1, temp + 1 + n);
           res += temp[1] + temp[2];
       }
   }
   //向上取整
   res = res % 2 == 0 ? (res / 2 ):( res / 2 + 1);
   return res;
}

//求解
int solve()
{
   int res = INF;//
   get_up();//求当前上界
   get_low();//当前下界
   node s;//
   s.st = 1;//起始节点
   s.ed = 1;//终点
   s.k = 1;//走过点数
   s.sumv = 0;//
   s.lb = low;//当前下界
   s.path[0] = 0;//起点
   //
   for (int i = 0; i < n; i++)//初始化未访问，没有路径
   {
       s.vis[i] = 0;
       s.path[i] = 0;
   }
   s.vis[0] = 1;//访问第一个结点
   q.push(s);//当前结点入队
   node next, temp;
   while (!q.empty())
   {
       temp = q.top();//队首元素
       q.pop();//出队
       //结束条件
       //只剩最后一个点
       if (temp.k == n - 1)
       {
           int pos = 0;
           for (int i = 1; i <= n; i++)//从0开始
           {
               if (temp.vis[i] == 0)//如果路径上第i点没有被访问
               {
                   pos = i;
                   break;
               }
           }
           //结束遍历
           if (pos == 0)//都被访问
           {
               break;//结束while循环
           }
           //还有pos没有访问到，那么设最后一个结点是POS
           //结果当前路径长度+当前路径终点到POS+POS到当前路径起点
           int ans = temp.sumv+cost[pos][temp.st]+cost[temp.ed][pos];
           //最后一个结点是POS
           temp.path[n] = pos;//从结点1开始计算
           //当前路径的上界是
           temp.lb = ans;
           //此时队首元素，也是当前最优元素
           node judge = q.top();
           //如果当前路径比所有分支的上界都小，找到最优解
           if (ans <= judge.lb);
           {
               res = min(ans, res);
               answer = temp;//返回答案
               break;
           }
           else if(up>=ans)//当前答案<=上界，还是有可能从其他路径更新上界
           {
               up = ans;
               answer = temp;

           }
           res = min(res, ans);//更新此时的最小值
           continue;

       }
       //
       for (int i = 1; i <= n; i++)
       {
           if (temp.vis[i] == 0)//当前路径还未访问该点
           {
               next.st = temp.st;//一样的起点
               next.ed = i;//结点是i
               next.k = temp.k + 1;//点数+1
               next.sumv = temp.sumv + cost[temp.ed][i];//更新
               for (int j = 1; j <= n; j++)
               {
                   next.vis[j] = temp.vis[j];
                   next.path[j] = temp.path[j];
               }
               next.vis[i] = 1;
               next.path[next.k] = 1;//路径
               next.lb = get_lb(next);//下界
               if (next.lb <= up)//如果
               {
                   q.push(next);
               }//反之，剪枝
           }
       }
   }
   return res;
}