1.最近鄰點法 (貪心策略 TSP）

2. 最短連接 TSP問題 貪心算法

#include<stdio.h> #include<iostream> using namespace std;//采用最近鄰點貪心策略求TSP問題。 int TSP1(double arc[6][6],int w)//假定從頂點w出發 {int n=6;int edgeCount=0;//哈密頓回路的邊數 int TSPLength=0;int min,u,v;int flag[n]={0}; // 頂點均未加入哈密頓回路u=w;//w為出發點 u為加入到哈密頓回路的點 flag[w]=1; while(edgeCount<n-2) //已經加入一個出發點，只需要再4個點 0 1 2 3 四次找點{min=100;for(int j=1;j<n;j++) //求arc[u]的最小值 {if((flag[j]==0) && (arc[u][j]!=0) &&((arc[u][j]!=100e5))&& (arc[u][j]<min)) //j點沒有被加入哈密頓回路 排除自己 找到最小值 {v=j;//v點最終是距離u點最近的點 min=arc[u][j];}} //找到距離u點的最近的點，把它加入哈密頓回路TSPLength+=arc[u][v];flag[v]=1;edgeCount++;cout<<u<<"-->"<<v<<endl; u=v; //把v點賦值給u，接下來找距離v點最近的點 while循環控制直到所有點都被加入進去 }cout<<v<<"-->"<<w<<endl;//輸出最后的回邊return (TSPLength+arc[u][w]);//返回最終的最短哈密頓回路的長度!! } int main() {double arc[6][6]={{0,0,0,0,0,0},{0,100e5,3,3,2,6},{0,3,100e5,7,3,2},{0,3,7,100e5,2,5},{0,2,3,2,100e5,3},{0,6,2,5,3,100e5}};int n2=TSP1(arc,1);cout<<n2; } #include<stdio.h> #include<iostream> #include<malloc.h> using namespace std;//查找最小邊函數 Search pair<int,int> Search(int **A,int N,int *flag,int **AF) { //查找最小邊int min=10e5,a=0,b=0;for(int i=0; i<N; i++) {for(int j=0; j<i; j++) {if(!AF[i][j]&&flag[i]<2&&flag[j]<2&& A[i][j]<min) {//如果這條邊沒有走過，兩邊的城市沒有同時有兩個被走過的邊 a=i; b=j;min=A[i][j];//依次比較 }}}flag[a]++;flag[b]++;AF[a][b]=1;return pair<int,int>(a,b); }//TSP2 int TSP2(int **A,int N,int *flag,int **AF) {int tsp=0,i,j,k;for(k=0; k<N; k++) {//選擇N次最短邊 pair<int,int> a=Search(A,N,flag,AF);tsp+=A[a.first][a.second];//每次加入最增的最短邊 }return tsp; }int main() {//N初始化int N=5; //A初始化(城市之間的距離)int **A=(int **)malloc(N*sizeof(int));cout<<"輸入5個城市之間的距離(0表示城市間不通):"<<endl;for(int i=0;i<N;i++){A[i]=(int*)malloc(N*sizeof(int));for(int j=0;j<N;j++){cin>>A[i][j];}} //AF初始化，記錄邊是否走過 int **AF=(int **)malloc(N*sizeof(int));//記是否邊走過，初始值設為0，走過設為1for(int i=0;i<N;i++){AF[i]=(int*)malloc(N*sizeof(int));for(int j=0;j<N;j++){AF[i][j]=0;}}//flag初始化,記錄城市是否走過 int *flag=(int *)malloc(N*sizeof(int));//標記是否城市走過，初始值設為0，走進去又走出來成為2 for(int i=0;i<N;i++)//設置flag的初值 {flag[i]=0;}cout<<"最短路徑長度：";cout<<TSP2(A,N,flag,AF);}

總結

以上是生活随笔為你收集整理的TSP问题(贪心法）最近邻点和最短连接的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。