qjh2375580241的gravatar頭像
qjh23755802412020-04-02 22:47:10

使用java寫出旅行商問題,很難很難,求大佬們幫幫忙!

現在需要做一個TSP問題的解法,表示遇到了無奈的情況

問題描述:旅行商問題,已知N個城市的坐標或者距離鄰接矩陣(int類型),從一個城市出發固定0城市或者固定1城市出發,經過且僅經過其余N-1個城市一次,回到出發城市。求最短距離,并且需要知道最短距離的途徑路徑。

測試樣例:已知坐標的,最大有52個城市
                    已知距離鄰接矩陣的,最大有58個城市

0、暴力法:城市順序全排列,找到最短距離(純屬開玩笑,跑兩天不知道行不行···
1、回溯法:運行了1個小時才能得到結果而且只是,表示未免也太慢了點吧。
2、分支定界法:空間消耗太大了,運行時間也難以保證。
3、動態規劃法:空間復雜度要求太高了,城市稍微比較多的樣例程序就會崩···,數量比較少的樣例倒是沒問題,自己寫出來了
4、模擬退火算法,遺傳算法,蟻群算法,看了半天的算法介紹,表示自己學不會怎么破···
5、其他算法:禁忌搜索?(其實這個覺得能寫,但算法有點不理解····

想問問大神們,有什么好的方法可以過了那17個樣例。真心感謝啊······

所有回答列表(2)
lzj1239825268的gravatar頭像
lzj1239825268 LV24月3日

就用tsp 算法啊,TSP還不簡單么,給你個案例

package book;

import java.util.Scanner;

public class TSP {
static int n,m;//n城市數量,m邊數量
static int grh[][];//地圖
static int curentlength,bestlength;//當前距離,最短距離
static int curent[],best[];//當前路線,最好的路線
static int Max=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		grh=new int[n+1][n+1];
		curent=new int[n+1];
		best=new int[n+1];
		curentlength=0;
		bestlength=-1;
		for(int i=1;i<=n;i++) {
			curent[i]=i;
			for(int j=1;j<=n;j++) {
				grh[i][j]=Max;//初始化地圖,每個點之間的距離都是無窮大
		   }
		}
		for(int i=1;i<=m;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			int length = sc.nextInt();
		    
		    	grh[start][end]=length;
		    	grh[end][start]=length;//把所有的邊存儲起來
		    
		}
		backtrace(2);
		if(bestlength!=-1) {
		for(int i=1;i<=n;i++) {
			System.out.print(best[i]+" ");
		}
		System.out.println("1");
		
		System.out.println(bestlength);
	}else {
		System.out.println("-1");
	}
		
	}

	
	private static void backtrace(int t) {
		if(t==n) {
			if(grh[curent[n-1]][curent[n]]!=Max&&grh[curent[n]][1]!=Max&&
					(curentlength+grh[curent[n-1]][curent[n]]+grh[curent[n]][1]<bestlength||bestlength==-1)) {
				//1.當到準備去第n個城市的時候,首先要判斷當前售貨員與第n個點有沒有路線,沒有路線就剪掉
				//2.要判斷第n個點與起點1有沒有路線,沒有也要剪掉
				//3.判斷走完這條路線,回到原點的總距離是不是小于已經知道的最短距離,如果大于也剪掉
				//如果都符合,就要做更新操作
				for(int i=1;i<=n;i++) {
					best[i]=curent[i];
				}
				bestlength=curentlength+grh[curent[n-1]][curent[n]]+grh[curent[n]][1];
			}
		}else {
			for(int i=t;i<=n;i++) {
				if(grh[curent[t-1]][curent[i]]<Max&&(curentlength+grh[curent[t-1]][curent[i]]<bestlength||bestlength==-1)) {
					//上面的剪枝條件是,t-1表示現在售貨員所在的城市,i表示他現在要準備去的城市,兩者之間必須要有邊
					//bestlength=-1表示第一次走
					//符合條件我們就需要交換
					swap(t,i);
					curentlength=curentlength+grh[curent[t-1]][curent[t]];
					backtrace(t+1);
					curentlength=curentlength-grh[curent[t-1]][curent[t]];
				    swap(t,i);
				    
				}
			}
		}
		
	}
	private static void swap(int t, int i) {
		int temp=0;
		temp=curent[t];
		curent[t]=curent[i];
		curent[i]=temp;
	}

}


 

評論(0)最佳答案
ZH0001的gravatar頭像
ZH0001 LV25月28日

看你需要得到結果的精確度了,如果只是要一個滿意解,可以考慮蟻群算法、遺傳算法,tsp本身是一個NP難問題,隨著城市數量的增多,解空間也會指數級的增大,是不可能窮舉盡的。

頂部客服微信二維碼底部
>掃描二維碼關注最代碼為好友掃描二維碼關注最代碼為好友
海王捕鱼2内购破解版