问题描述

设有n个城市,城市之间道路的长度均大于或等于0,还可能是∞(对应城市之间无交通线路)。一个旅行商从某个城市出发,要经过每个城市一次且仅一次,最后回到出发的城市,问他如何走才能使他走的路线最短?

要求:优先使用矩阵归约确定限界函数的方法,或者其他方法实现。

问题分析

对于这个问题,我们采用广度优先遍历,把从起点到其他未曾走过的边的权权入队(优先队列)

接下来每次从队中取出最小的权的元素,在其进行广度优先遍历,即从此点到其他未曾走过的边的权加上他本来的权的元素入队

结束条件,第一个所有节点都被访问过的元素被出队。

最后被出队元素在加上其最后一个被访问节点到起点的边的权

算法分析

首先从文件读取节点数量以及边数量、起点、边的权信息。所用时间T = O(n)

接着构造优先队列,所用时间 T = O(nlogn)

接下来将起点到其他个点距离入队,所用时间T = (n-1)O(log n)

之后设置while循环,每次从队中取出最小的权的元素,进行广度优先遍历,将从此点到其他未曾走过的边的权加上他本来的权的元素入队。

所用时间T = O(n) (搜索未访问节点) + (n - deep)O(log n) (入队元素) +一次出队O(log n)

总时间约为T = O(nlogn)

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef struct
{
int meter = 0 ;
int pos = 0 ;
int v[10];
int cnt = 0;
}ties;
bool operator<(ties a, ties b) {
return a.meter > b.meter;
}
int main()
{
char buffer[200];
ifstream in("bandary_TSP.txt");
int number = 0 , side = 0 , source = 0;
in.getline(buffer,20);
sscanf(buffer,"%d%d%d",&number,&side,&source);

vector<vector<int> > v(number+1);
for(int i = 1 ; i < v.size() ;++i) {v[i].resize(number+1);}

for(int i = 1 ; i <= side ;++i) {
int m = 0 , n = 0 , w = 0;
in.getline(buffer,20);
sscanf(buffer,"%d%d%d",&m,&n,&w);
v[m][n] = w ;
v[n][m] = w ;
}

priority_queue<ties> q;
for(int i = 1 ; i <= number ; ++i){
if(i != source) {
ties temp ;
temp.meter = v[source][i];
temp.v[source] = 1 ;
temp.pos = i ;
temp.cnt += 1 ;
q.push(temp);
}
}

while(!q.empty()){
ties temp = q.top();
temp.cnt += 1 ;
if(temp.cnt + 1 == number){
for(int i = 1 ;i <= number ; ++i){
if(temp.v[i] != 1){
cout << temp.meter+v[temp.pos][i];
return 0;
}
}
}
q.pop();
for(int i = 1 ; i <= number ; ++i){
if(temp.v[i] != 1 && i != temp.pos ){
temp.meter += v[temp.pos][i];
temp.v[temp.pos] = 1;
temp.v[i] = 1;
temp.pos = i ;
q.push(temp) ;
}
}
}
return 0;
}

谢谢访问