问题描述

已知图G=(V,E),利用贪心策略求解图G上的从顶点1出发的最短巡回旅行路线,要求输出找到的(近似)最短巡回旅行路线。

要求:给出问题的贪心算法,并编程实现

问题分析

本题类似邮递员问题,从图中任意一个出发,首先寻找起始点到所有点距离最近 的点,找到后,新的点再找离它最近的点,知道回到出发点,即位所求最短路径。这种思路显然为贪心思路。简洁总结如下:

  1. 从某个城市开始,每次选择一个城市,知道所有的城市都被走完
  2. 每次只选择到下一个城市最近的路线所对应的城市

算法设计

(1) 从文件读入内存数据,时间复杂度为线性O(n)

(2) 邻接矩阵储存顶点之间的边的长度。

(3) 使用双重循环,从起点开始,依次找到最短路径上的顶点:

具体思路如下:

开始时X = {起点a},Y = {顶点b,顶点c,顶点d}

确定起点到另外三个顶点中最短的一个顶点路径,并将b号顶点加入X集合,此时X ={a,b}Y ={c,d}

按照每次只加入离当前顶点最近的顶点,知道Y集合为空。

时间复杂度为O(n^2)

综上所述,时间复杂度为O(n^2)

参考代码

#include <bits/stdc++.h>
using namespace std;
#define MAXLEN 99999
int greedy(int start_city,const int number,vector<int>&city, const vector< vector<int> > length ){
cout << "TSP路线:" << endl;
//cout << start_city << "-->";
int start = start_city ;
int next_city = 0;
int sum_min = 0 ;
for(int i = 1 ; i <= number ; ++i){
int len = MAXLEN;
for(int j = 1 ; j <= number ; j++){
if(city[j] == 1) {continue;}

if(len > length[start_city][j]) {
len = length[start_city][j];
next_city = j ;
}
}
start_city = next_city ;
cout<<start_city<<"-->";
city[start_city] = 1;
sum_min += len;
}
sum_min += length[start_city][start] ;
cout << start <<endl;
return sum_min;
}
int main()
{
char buffer[200];
int number = 0 ; //城市个数
int edge = 0 ; //边个数
vector<int> city(number+1); // 记录城市已经路过
ifstream in("tsp.txt");
in.getline(buffer,20);
sscanf(buffer,"%d",&number);
// 构造二维数组
vector< vector<int> > length(number+1);
for(int i = 0 ; i < length.size() ; ++i){length[i].resize(number+1);}
//临界矩阵保存两点间路的长度
//输入两点间的路径个数
in.getline(buffer,20);
sscanf(buffer,"%d",&edge);
//保存两点间路径长度
for(int i = 1 ; i <= edge ; ++i){
in.getline(buffer,20);
int m = 0 , n = 0 , w = 0;
sscanf(buffer,"%d%d%d",&m,&n,&w);
length[m][n] = w ;
length[n][m] = w ;
}
for(int i = 0 ; i < length.size();++i){
for(int j = 0 ; j < length.size(); ++j){
cout << length[i][j] <<" ";
}
cout << endl;
}
int start_city = 0 ;
int sum_min = 0 ;
in.getline(buffer,20);
sscanf(buffer,"%d",&start_city);
sum_min = greedy(start_city,number,city,length);
cout << "最短路径长度为: " << sum_min ;
return 0;
}

谢谢访问