答案家

 找回密码
 立即注册
查看: 466|回复: 0

2018使用动态规划解决旅行商问题

[复制链接]

1

主题

1

帖子

41

积分

幼儿园

Rank: 1

积分
41
发表于 2018-8-14 17:34:19 | 显示全部楼层 |阅读模式
  【摘要】旅行商问题是指给定一组城市和道路,求一条从指定城市出发、通过所有其它城市一次、再返回出发城市的代价最小的路径。旅行商问题是一个经典的NP完全问题,其传统的求解算法为穷举法,按所有可能的路径计算一遍,比较所有的计算结果,选择其中的最短路径。
/6/view-10686688.htm
  【关键词】动态规划;旅行商;算法
  二、动态规划求解策略
  动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,希望找到具有最优解的那个解。一个动态规划算法通常可按以下几个步骤进行:
  (1) 找出最优解的性质,并刻画其结构
  (2) 递归定义最优值的求解公式
  (3) 以自底向上的方式计算最优值
  (4) 根据计算时得到的信息,构造一个最优解
  三、旅行商问题的动态规划实现算法
  用程序来模仿动态规划算法,最重要的是一个分段过程,它与传统算法的区别是“以自底向上的方式计算出最优值”,我们以这一条准则分段。
  在第一次遍历所有的城市流时,每相邻的两个城市流,前三个字符相同的,我们判断一下最后两个字符决定的路径长度,删除路径较长的城市流,保存路径较短的城市流,由于删除了一个城市流,所以我们需要从当前的城市流重新比较一次(反映在一个循环中,就应该是当前的index减1)。当然,在这个比较过程中,我们把计算出的每一个长度都保存起来,这样,我就能避免很多重复计算,这也正是使用动态规划的益处!反映到程序当中,这需要一个包含循环的迭代函数来描述:
  private void guihua(int temp) {
  if (list.size() == 1) {
  this.firnalRoad = list.get(0);
  this.min = this.store.get(list.get(0)) + "";
  return;
  }
  for (int i = 0; i = nextValue) {
  list.remove(i);
  } else {
  list.remove(next);
  }
  i--;
  }
  }
  this.guihua(temp - 1);
  }
  4.测试实例
  (1) first为{{0, 1, 2, 3}, {3, 0, 4, 6}, {4, 2, 0, 8}, {4, 3, 9, 0}};
  运行结果为:
  路径是:3201
  城市顺序:0->3->1->2->0
  最小值:14.0
  生成所有合法城市流用时:15毫秒
  动态规划求解过程用时:0毫秒
  (2) first为{{0,2,1,3,4}, {1,0,4,4,2}, {5,4,0,2,2}, {5,2,2,0,3}, {4,2,4,2,0}};
  运行结果为:
  路径是:20413
  城市顺序:0->2->4->3->1->0
  最小值:8.0
  生成所有合法城市流用时:62毫秒
  动态规划求解过程用时:0毫秒
  看第2个例子,输出城市顺序是“0->2->4->3->1->0”,由于我们是从0开始计数的,所以与上面数学计算中输出的城市顺序相同,并且最小值为8.0,也是正确的。可以用数学计算方法验证一下,以上例子的输出都是正确的。
  四、结束语
  动态规划法是一种有着广泛应用的算法,它的优越性在于省略了很多重复计算,所以在数学计算中应用较多。但随着城市数量的增多,动态规划算法求解问题的时间还是保持很大的增长率,所以动态规划虽然提供了一种问题的求解办法,但并不完美。
  作者简介
  申永康(1997),男,汉族,山东日照,高中生,山东省日照一中。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

CopyRight(c)2016 www.daanjia.com All Rights Reserved. 本站部份资源由网友发布上传提供,如果侵犯了您的版权,请来信告知,我们将在5个工作日内处理。
快速回复 返回顶部 返回列表