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

9927939

　　【摘要】旅行商问题是指给定一组城市和道路，求一条从指定城市出发、通过所有其它城市一次、再返回出发城市的代价最小的路径。旅行商问题是一个经典的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），男，汉族，山东日照，高中生，山东省日照一中。