解决tsp问题的算法,

  解决tsp问题的算法,

  1.TSP问题

  TSP (Traveling Salesman Problem)即旅行商问题,也译为旅行商问题和旅行商问题。这是数学领域中著名的问题之一。假设一个出差的商人想去N个城市,他必须选择他想走的路线。路线的限制是每个城市他只能去一次,最后还得回到原来的城市。路径选择的目标是所需的路径距离是所有路径中最小的。

  TSP问题是一个组合优化问题。这个问题可以证明具有NPC的计算复杂性。TSP问题可以分为两类,一类是对称TSP问题,一类是非对称TSP问题。所有TSP问题都可以用图来描述:

  V={c1,c2,…,ci,…,cn},i=1,2,…,n,这是所有城市的集合。ci代表第I个城市,N是城市个数;

  TSP问题可以表示为:

  求解遍历图G=(V,E,C),所有节点都是一次并返回到初始节点,使得连接这些节点的路径代价最低。

  二、爬山算法

  爬山算法是一种局部优化方法,采用启发式方法,是深度优先搜索的改进。它使用反馈信息来帮助制定解决方案的决策。该算法每次从当前解的相邻解空间中选择一个最优解作为当前解,直到达到一个局部最优解。它属于一种人工智能算法。

  爬山算法实现简单,主要缺点是会陷入局部最优解,但不一定能搜索到全局最优解。如下图所示:假设C点为当前解,爬山算法在搜索A点时会停止搜索局部最优解,因为无论往哪个方向移动,都无法在A点得到更好的解.

  爬山算法的实现步骤:

  3.求解TSP问题的爬山算法。

  在这个JAVA实现中,我们选择使用tsplib上的数据att48,这是一个对称的TSP问题。城市规模为48,其最优值为10628。距离计算方法如下图所示:

  具体代码如下:

  包诺亚;

  导入Java . io . buffered reader;

  导入Java . io . file inputstream;

  导入Java . io . io exception;

  导入Java . io . inputstreamreader;

  导入Java . util . random;

  公共类爬山{

  private int MAX _ GEN//迭代次数

  private int cityNum//城市数量,编码长度

  private int[][]距离;//距离矩阵

  private int bestT//最佳出现代数

  private int[]best GH;//最佳路径编码

  私有int bestEvaluation

  私有Random random

  公共爬山(){

  * GA的构造者

  * @param n

  *城市数量

  * @param g

  *运行代数

  公共爬山(int n,int g) {

  city num=n;

  MAX _ GEN=g;

  //给编译器一个指令,让它对带注释的代码元素中的一些警告保持沉默。

  @SuppressWarnings(resource )

  *初始化爬山算法类

  * @param filename数据文件名,存储所有城市节点坐标数据。

  * @抛出IOException

  私有void init(字符串文件名)引发IOException {

  //读取数据

  int[]x;

  int[]y;

  字符串strbuff

  buffered reader data=new buffered reader(new InputStreamReader(

  新文件输入流(文件名)));

  distance=new int[city num][city num];

  x=new int[city num];

  y=new int[city num];

  for(int I=0;i cityNumi ) {

  //读取一行数据,数据格式1 6734 1453

  strbuff=data . readline();

  //字符分割

  string[]strcol=strbuff . split();

  x[I]=integer . value of(strcol[1]);//x坐标

  y[I]=integer . value of(strcol[2]);//y坐标

  //计算距离矩阵

  //针对具体问题,距离计算方法不同,

  //这里以att48为例。它有48个城市。距离计算方法为伪欧氏距离,最优值为10628。

  for(int I=0;I city num-1;i ) {

  距离[I][I]=0;//对角线为0

  for(int j=I 1;j cityNumj ) {

  double rij=数学。sqrt((x[I]-x[j])*(x[I]-x[j))(y[I]-y[j])

  *(y[I]-y[j])/10.0);

  //圆形,圆形

  int tij=(int)math . round(rij);

  if (tij rij) {

  距离[I][j]=tij 1;

  距离[j][i]=距离[I][j];

  }否则{

  距离[I][j]=tij;

  距离[j][i]=距离[I][j];

  距离[城市编号-1][城市编号-1]=0;

  best GH=new int[city num];

  最佳评估=整数最大值

  bestT=0;

  Random=新的Random(系统。当前时间毫秒());

  //初始化编码德国

  void initGroup() {

  int i,j;

  最佳GH[0]=随机。nextint(65535)%城市号码;

  for(I=1;i cityNum)//编码长度

  最佳GH[I]=random。nextint(65535)%城市号码;

  for(j=0;j j ) {

  if (bestGh[i]==bestGh[j]) {

  打破;

  if (j==i) {

  我;

  public int evaluate(int[] chr) {

  int len=0;

  //染色体,起始城市,城市1,城市2.城市n

  for(int I=1;i cityNumi ) {

  len=distance[chr[I-1]][chr[I]];

  //城市n,起始城市

  len=distance[chr[城市编号-1]][chr[0]];

  返回低输入联网(low-entry networking的缩写)

  //爬山算法

  public void pashan(int[] Gh,int T) {

  int i,temp,TT=0;

  int ran1,ran2

  int e;//评价新值

  int[]tempGh=new int[city num];

  最佳评价=评价(Gh);

  //爬山代数T

  for(TT=0;tt tt ) {

  for(I=0;i cityNumi ) {

  tempGh[I]=Gh[I];

  ran 1=随机。nextint(65535)%城市号码;

  ran 2=随机。nextint(65535)%城市号码;

  while (ran1==ran2) {

  ran 2=随机。nextint(65535)%城市号码;

  //两交换法实施邻域操作

  temp=tempGh[ran 1];

  tempGh[ran 1]=tempGh[ran 2];

  tempGh[ran 2]=temp;

  e=evaluate(tempGh);//评价新值

  如果(最佳评估){

  bestT=TT;

  最佳评价=e;

  for(I=0;i cityNumi ) {

  GH[I]=tempGh[I];

  公共void solve() {

  init group();//初始化编码

  帕山(bestGh,MAX _ GEN);

  System.out.println(最佳长度出现代数:);

  系统。出去。println(bestT);

  System.out.println(最佳长度);

  系统。出去。println(最佳评价);

  System.out.println(最佳路径:);

  for(int I=0;i cityNumi ) {

  System.out.print(bestGh[i],);

  if (i % 10==0 i!=0) {

  系统。出去。println();

  * @param args

  * @抛出异常

  公共静态void main(String[] args)引发IOException {

  System.out.println(Start . );

  爬山爬山=新爬山(48,5000);

  希尔剪辑。init( c://data。txt’);

  希尔剪辑。solve();

  运行结果截图:

  四、总结

  爬山算法由于其简单的结构,在处理多约束大规模问题时比较力不从心,很难得到较好的解,但在小规模的公证人问题求解中,解的质量还是比较好的;此外爬山算法结构简单,在某些情况下,整体效率比A星算法的效果还好。

  注:本文部分内容来源于网络,但程序以及分析结果属于本人成果,转载请注明!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: