pc网站转换手机网站代码,桂林工作网招聘,谷歌seo实战教程,重要新闻事件一、概述 有n个城市#xff0c;旅行者要访问所有n个城市#xff0c;最终回到起始点#xff0c;假设起始点给定为1#xff0c;城市间距离已知#xff0c;求能够完成旅行的最短距离。题干如下图。 算法#xff1a;分支限界法#xff0c;使用队列进行bfs搜索。 二、代码
i…一、概述 有n个城市旅行者要访问所有n个城市最终回到起始点假设起始点给定为1城市间距离已知求能够完成旅行的最短距离。题干如下图。 算法分支限界法使用队列进行bfs搜索。 二、代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class tsp {public static final int MAX9999;public static int arr[][]{{MAX,MAX,MAX,MAX,MAX},{MAX,MAX,30,50,4},{MAX,30,MAX,5,15},{MAX,50,5,MAX,3},{MAX,4,15,3,MAX}};public static int sizearr.length;public static int costminMAX;public static int route[]new int[arr.length];public static class traveling{public int cc; //当前费用public int x[]new int [size-1]; //当前路径public int n; //当前连接点个数public int flag[]new int[size];public traveling(int cc,int x[],int n,int flag[]){this.cccc;this.nn;for(int i0;in;i){this.x[i]x[i];}for(int i0;iarr.length;i){this.flag[i]flag[i];}}}public static void main(String[] args){bfs();for(int i:route)System.out.print(i );System.out.println();System.out.println(costmin:costmin);} public static void bfs(){Queuetravelingqnew LinkedList();int flag[]{0,1,0,0,0};int x[]{1};traveling trnew traveling(0, x, 1,flag);q.offer(tr);while(!q.isEmpty()){trq.poll();int endtr.x[tr.n-1]; //end队列中最后一个值int cctr.cc;if(tr.nsize-1tr.cccostminarr[tr.x[0]][tr.x[tr.n-1]]!MAX){for(int i0;iarr.length-1;i){route[i]tr.x[i];}route[arr.length-1]route[0];}for(int i1;iarr.length;i){if(cccostmin)break;if(tr.flag[i]0arr[end][i]!MAXcccostmin){int xtmp[]new int[arr.length-1];for(int j0;jtr.n;j){xtmp[j]tr.x[j];}xtmp[tr.n]i;int flagtmp[]new int[arr.length];for(int j0;jarr.length;j){flagtmp[j]tr.flag[j];}flagtmp[i]1;traveling addrnew traveling(ccarr[end][i], xtmp, tr.n1, flagtmp);if(tr.n1size-1ccarr[end][i]arr[i][tr.x[0]]costmin)costminccarr[end][i]arr[i][tr.x[0]];q.offer(addr);}}}}
}
