精华内容
下载资源
问答
  • 动态规划求解TSP问题

    2019-09-23 23:35:52
    程序入口,求解TSP问题并可视化 cities.json:json数据 [[88, 88], [93, 13], [17, 20], [13, 70]] tool.py:工具模块 # -*- coding:utf-8 -*- import math import json import random ...

    设计思路:

    程序清单:

    文件名

    定位

    作用

    cities.json

    json数据

    存储城市坐标信息

    tool.py

    工具模块

    提供读取JSON数据、生成随机点、生成距离矩阵等函数

    main.py

    主模块

    程序入口,求解TSP问题并可视化

    cities.json:json数据

    [[88, 88], [93, 13], [17, 20], [13, 70]]

    tool.py:工具模块

    # -*- coding:utf-8 -*-
    
    
    
    import math
    
    import json
    
    import random
    
    
    
    # 生成一定范围的随机数
    
    def random_double(_min, _max):
    
        return random.random() * (_max - _min) + _min
    
    
    
    # 生成随机城市坐标
    
    def random_cities(_min, _max, num):
    
        return [[random_double(_min, _max), random_double(_min, _max)] for _ in range(num)]
    
    
    
    # 计算欧式距离
    
    def distance(c1, c2):
    
        return math.sqrt(square_distance(c1, c2))
    
    
    
    # 计算平方欧式距离
    
    def square_distance(c1, c2):
    
        return (c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2
    
    
    
    # 由城市坐标列表,生成距离矩阵
    
    def distance_matrix(_cities):
    
        length = len(_cities)
    
        matrix = [[-1.0] * length for _ in range(length)]
    
        for i in range(length - 1):
    
            for j in range(i + 1, length):
    
                matrix[i][j] = matrix[j][i] = distance(_cities[i], _cities[j])
    
    
    
        return matrix
    
    
    
    # 从json文件中,读取城市信息
    
    def read_cities():
    
        json_path = 'cities.json'
    
        with open(json_path, 'r') as f:
    
            return json.load(f)

    main.py:主模块

    # -*- coding:utf-8 -*-
    
    
    
    from tool import read_cities, distance_matrix
    
    import matplotlib.pyplot as plt
    
    
    
    class Solution:
    
    
    
        def __init__(self, _matrix, start_node):
    
            # 距离矩阵
    
            self.matrix = _matrix
    
            # 节点数目
    
            self.height = len(self.matrix)
    
            # 宽度
    
            self.width = 2 ** self.height
    
            # 开始节点
    
            self.start_node = start_node
    
            # 记录处于x节点,未经历M个节点时
    
            # 矩阵储存x的下一步是M中哪个节点
    
            self.array = [[0] * self.width for _ in range(self.height)]
    
    
    
        def tsp(self):
    
            # 开始节点
    
            s = self.start_node
    
            # 节点数目
    
            num = self.height
    
            # 未遍历节点集合
    
            _cities = list(range(num))
    
            _cities.pop(s)
    
            # 求解函数
    
            return self.solve(s, _cities)
    
    
    
        @staticmethod
    
        def transfer(sets):
    
            _sum = 0
    
            for s in sets:
    
                _sum += 2 ** s  # 二进制转换
    
            return _sum
    
    
    
        def solve(self, node, future_sets):
    
            # 迭代终止条件,
    
            # 表示没有了未遍历节点,直接连接当前节点和起点即可
    
            if len(future_sets) == 0:
    
                return self.matrix[node][self.start_node]
    
            # node如果经过future_sets中节点,最后回到原点的距离
    
            distance = []
    
            # 遍历未经历的节点
    
            for i in range(len(future_sets)):
    
                s_i = future_sets[i]
    
                # 访问s_i,更新当前未访问节点集合
    
                copy = future_sets[:]
    
                copy.pop(i)
    
                # 递归,动态规划递推方程
    
                distance.append(self.matrix[node][s_i] + self.solve(s_i, copy))
    
            # 最小距离
    
            d = min(distance)
    
            # node需要连接的下一个节点
    
            next_one = future_sets[distance.index(d)]
    
            # 未遍历节点集合
    
            c = self.transfer(future_sets)
    
            # (当前节点,未遍历节点集合)-->下一个节点
    
            self.array[node][c] = next_one
    
            return d
    
    
    
    if __name__ == '__main__':
    
        # 从JSON读取数据
    
        cities = read_cities()
    
        # 生成距离矩阵
    
        mat = distance_matrix(cities)
    
        # 调用tsp
    
        S = Solution(mat, 0)
    
        S.tsp()
    
        # 开始回溯
    
        lists = list(range(len(S.matrix)))
    
        start_node = S.start_node
    
        # 生成路径
    
        output_path = list()
    
        while len(lists) > 0:
    
            lists.pop(lists.index(start_node))
    
            # 未访问节点集合 矩阵中的y坐标
    
            y = S.transfer(lists)
    
            # 下一节点
    
            next_node = S.array[start_node][y]
    
            # 添加下一组合
    
            output_path.append([start_node, next_node])
    
            # 从下一节点出发
    
            start_node = next_node
    
        # 输出城市列表
    
        print('城市坐标集合为:')
    
        for city in cities:
    
            print(city, end=' ')
    
        print()
    
        # 距离矩阵
    
        print('距离矩阵为:')
    
        for row in mat:
    
            for col in row:
    
                print('%10.2f' % col, end='   ')
    
            print()
    
        # 输出路径
    
        print('最优路径为:')
    
        for i in output_path:
    
            print(i[0], '-->', end='')
    
        print('0')
    
        # 画散点图
    
        i = 0
    
        for city in cities:
    
            plt.scatter(city[0], city[1])
    
            plt.annotate("City%d(%d, %d)" % (i, city[0], city[1]), (city[0] + 2, city[1] + 2))
    
            i += 1
    
        # 画出路径
    
        for start_node, next_node in output_path:
    
            cs = cities[start_node]
    
            cn = cities[next_node]
    
            plt.plot([cs[0], cn[0]], [cs[1], cn[1]])
    
        # 不显示坐标轴
    
        plt.axis('off')
    
        # 绘图
    
    plt.show()
    
    

    TSP问题

    输出结果:

    绘图结果:

    展开全文
  • 该文档使用Java语言编写了一个通用的TSP问题求解方法,不仅进行了代码求解,还根据实际例子进行了手动求解和介绍,适合旅行商入门,以及Java语言的学习,附带源码和伪代码,以及详细的解释。
  • 使用动态规划方法求解TSP问题 这两天看到了一个用动态规划方法求解TSP问题的案例,原文代码是用C++写的,本人照着写成了java的代码,可以运行出相同的最后结果,但是不知道该如何得到最终的访问城市序列。 但是...

    使用动态规划方法求解TSP问题

    这两天看到了一个用动态规划方法求解TSP问题的案例,原文代码是用C++写的,本人照着写成了java的代码,可以运行出相同的最后结果,但是不知道该如何得到最终的访问城市序列。

    但是其中的每个步骤已经弄得很详细了,算是把明白的记录下来,不懂得留下来有机会再研究。

    参考文章:https://mp.weixin.qq.com/s/gLO9UffCMEqqMVxkOfohFA

    感谢原作者,感谢感谢。

    1. 什么是动态规划(DP),什么是TSP问题

    这个就百度就好了

    2. 将DP应用到TSP问题中,建立动态规划模型。

    具体解TSP问题时,没有必要将所有的DP步骤全部写出来。将状态转移方程写明白就可以理解代码了。下面仔细讲解状态转移方程。

    2.1 指标函数 d ( i , V' )

    i 表示当前路径中最后一个访问的城市节点(将要去的下一个城市,决策变量);V' 表示已经访问过的城市集合(状态)。

    d ( i , V' ) 表示从初始点出发,经过V'集合中的所有城市一次,最终到达城市 i,的最小花费。

    假设s为起点,则d ( t , { s, q, t } ) = 0 表示:s -> q -> t 这条路径的最小花费

    2.2 状态转移方程

    d(i, V' + { i }) 表示的是:s -> V' -> k -> i ,这条路径的最小花费。

    要想找到下一个访问城市i,以达到最小花费,需要在V'(已访问城市集合)中找到路径末端的城市,用路径末端城市与下一个可能的访问城市进行匹配,找到最小花费的匹配。

    3. 状态压缩(这里仅介绍本文用到的状态压缩方式)

     所谓状态压缩,就是利用二进制以及位运算来实现对于本来应该很大的数组的操作。而求解动态规划问题,很重要的一环就是状态的表示,一般来说,一个数组即可保存状态。但是有这样的一些题目,它们具有DP问题的特性,但是状态中所包含的信息过多,如果要用数组来保存状态的话需要四维以上的数组。于是,我们就需要通过状态压缩来保存状态,而使用状态压缩来保存状态的DP就叫做状态压缩DP。(以上是废话)

    假设问题中一共有四个访问点,编号为:0,1,2,3

    在上图中,最右遍那一列,0 ~ 15即为V'的值,用十进制数字来保存当前状态。

    例如:当V' = 3时,3的二进制为左边的四列 0 0 1 1 ,表示已经访问过的城市集合中有城市0城市1

    而且,通过左移运算(<<),计算出n个城市节点一共有多少种可能的状态。例如:四个城市节点时,(1 << 4) = 16,一共有16种状态。

    4. 代码部分

    代码部分是我照着那个朋友的C++代码直接写的java代码,可能会有还未发现的错误。希望朋友们指正。就其中三点做主要说明。

    4.1 过滤1

    这句代码在sovle()函数中, j 为下一步要访问的城市编号,i(状态)为已经访问过的城市集合,当状态 i 中已经包含了城市 j ,则过滤掉这个状态,跳出本次循环。

     if ((i & (1 << j)) != 0) continue;

    例如:i = 12 , j = 4 。将 i j 都转化为二进制:i = 1 1 0 0 , j = 0 1 0 0 。通过位运算&,可以判断出 i & j = 0 1 0 0 ,此时在状态 i 中已经访问过了城市 j 。

    此种情况下,就可以跳过i = 12 的状态,遍历下一个状态。

    4.2 过滤2

    这句代码在sovle()函数中,i(状态)为已经访问过的城市集合,用来过滤掉不是从城市0出发的状态。

    if ((i & 1) == 0) continue;

     例如:i = 12 , i 转化为二进制:i = 1 1 0 0 。将1转化为二进制:1 = 0 0 0 1,这表示路径中只有出发的城市0通过位运算&,可以判断出 i & j = 0 0 0 0 ,此时在状态 i 不是从城市0出发

     4.3 在状态i中寻找

    这句代码在sovle()函数,据说有两个功能:确保 k 节点已经在集合 i 中、确保 k 是上一步转过来的。

    “ 确保 k 节点已经在集合 i 中” ,这个功能的原理在4.1中已经有讲解。

    但是 “确保 k 是上一步转过来的 ” 这个功能还没发现是如何实现的。

    只有实现了这个功能,才能保证将城市 j 连接到了路径的末端,而不是连接到了路径中的某个城市。

    if (((i & (1 << k)) > 0))

    4.4 如何得出城市访问序列

    这个还有待解决

    5 代码部分

    package TSP01;
    
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.*;
    
    public class Main {
        final static double INF = 999999;
        static int N; // 城市数量
        static double distance[][]; // 距离矩阵
        static Vertex vertexs[]; // 储存城市结点的数组
        static double dp[][]; // 存储状态
        // dp[i][j]:j表示状态,i表示当前城市
        static int p[]; // p[i]的值表示i节点的前驱节点
        static double ans = INF; // 总距离
        static int pre[]; // 索引为状态,值为此状态中上一次加入到状态数组中的车辆
    
        public static void main(String[] args) throws FileNotFoundException {
            // 1.读取数据
            input("src\\TSP01\\a.txt", 1);
            // 2.初始化状态
            init_dp();
            // 3.解问题
            solve();
            // 4.输出答案
            //  4.1 按顺序将逆序访问序列添加到list链表中
            List<Integer> list = new LinkedList<>();
            int t = 0;
            list.add(0);
            while(p[t]!=0){
                list.add(p[t]);
                t = p[t];
            }
            //  4.2 反转列表
            Collections.reverse(list);
            //  4.3 输出正序的城市访问序列
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i) + " -> ");
            }
            System.out.println();
            System.out.println("总路程为:" + ans);
            for (int i = 0; i < N; i++) {
                System.out.println(i + "的前置节点为:" + p[i]);
            }
        }
    
    
        /**
         * 读取数据(数据类型有两种,1是矩阵,0是二位数组)
         *
         * @param filename 文件名
         * @param type     数据类型
         */
        public static void input(String filename, int type) throws FileNotFoundException {
            File file = new File(filename);
            Scanner sc = new Scanner(file);
            if (type == 1) {
                N = sc.nextInt(); // 城市数量
                p = new int[N];
                distance = new double[N][N];
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        distance[i][j] = sc.nextDouble();
                    }
                }
            } else if (type == 0) {
                N = sc.nextInt(); // 城市数量
                p = new int[N];
                vertexs = new Vertex[N];
                distance = new double[N][N];
                while (sc.hasNext()) {
                    int i = sc.nextInt() - 1; // 城市编号(从0开始)
                    vertexs[i] = new Vertex();
                    vertexs[i].id = i + 1;
                    vertexs[i].x = sc.nextDouble();
                    vertexs[i].y = sc.nextDouble();
                }
                for (int i = 0; i < N; i++) {
                    distance[i][i] = 0;
                    for (int j = 0; j < i; j++) {
                        distance[i][j] = edc_2d(vertexs[i], vertexs[j]);
                        distance[j][i] = distance[i][j];
                    }
                }
            } else {
                System.out.println("类型输入错误");
            }
            sc.close();
        }
    
        // 计算两点之间的距离
        public static double edc_2d(Vertex a, Vertex b) {
            return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
        }
    
        // 初始化状态
        public static void init_dp() {
            dp = new double[(1 << N) + 5][]; // 富余出5个
            for (int i = 0; i < (1 << N); i++) { // 遍历所有状态
                dp[i] = new double[N + 5];
                for (int j = 0; j < N; j++) { // 每个状态下出发点到达每个点的距离
                    dp[i][j] = INF;
                }
            }
        }
    
        // 解决问题
        public static void solve() {
            int M = (1 << N); // 状态的个数
            pre = new int[M];
            pre[0] = 0; // 初始化为0
            dp[1][0] = 0; // 确定出发点
            // 下面的每个十进制的i转化成N位的二进制,就可以代表当前的状态。0代表没有经过这个点,1代表已经过这个点。
            for (int i = 1; i < M; i++) { // 遍历每种状态
                for (int j = 1; j < N; j++) { // 每种状态下遍历每个可访问的下一个城市
                    // 过滤1(按位与运算):过滤掉状态中已经包含了城市节点j的状态
                    if ((i & (1 << j)) != 0) continue;
    
                    // 过滤2(按位与运算):默认必须从0号城市开始出发,过滤掉不是从0号城市出发的状态
                    if ((i & 1) == 0) continue;
    
                    // 尝试使用V'集合中的节点连接下一个节点。...->k->j
                    for (int k = 0; k < N; k++) {
                        // 1. 确保k节点已经在集合中
                        // 2. 确保k是上一步转过来的(如何确保源代码中也没有做到)
                        // 只有当k是上一步转过来的,才可以得到一个TSP环,而不是其中有多个子环
                        // 这个问题在源代码中也没有得到解决
                        if (((i & (1 << k)) > 0)) {
                            // dp[(1<<j)][j] 表示的是当j点即为出发点时的情况
                            // dp[(1<<j)][j]中,(1<<j)表示的状态是计算不到这一步的,因此此种状态表示以j为出发点,不符合上面要求
                            if (dp[(1 << j) | i][j] > dp[i][k] + distance[k][j]) {
                                dp[(1 << j) | i][j] = dp[i][k] + distance[k][j]; // 状态转移方程
    
                                pre[i] = j;
                                String q = Integer.toBinaryString(i);
                                System.out.println("i= " + i + " : " + q + "  p[" + j + "] = " + k);
                            }
                            if(dp[i][j] > dp[i][k] + distance[k][j]){
                                p[j] = k;
                            }
                        }
                    }
                }
    //            System.out.println("状态"+i+"的前一个添加进来的节点为:"+pre[i]);
            }
            for (int i = 0; i < N; i++) {
                if (ans > dp[M - 1][i] + distance[i][0]) {
                    ans = dp[M - 1][i] + distance[i][0];
                    p[0] = i;
                }
            }
        }
    }
    
    // 访问城市节点的类
    class Vertex {
        double x, y; // 坐标
        int id; // 节点编号
    
        public Vertex() {
        }
    
        @Override
        public String toString() {
            return "Vertex{" +
                    "x=" + x +
                    ", y=" + y +
                    ", id=" + id +
                    '}';
        }
    
        public Vertex(int id) {
            this.id = id;
        }
    }

    6. 算例部分

    6.1 type = 1

    4
    0   3   6   7
    5   0   2   3
    6   4   0   2
    3   7   5   0

    6.2 type = 0

     

    16
       1   38.24   20.42
       2   39.57   26.15
       3   40.56   25.32
       4   36.26   23.12
       5   33.48   10.54
       6   37.56   12.19
       7   38.42   13.11
       8   37.52   20.44
       9   41.23   9.10
     10   41.17   13.05
     11   36.08   -5.21
     12   38.47   15.13
     13   38.15   15.35
     14   37.51   15.17
     15   35.49   14.32
     16   39.36   19.56
    展开全文
  • 首先,什么是TSP问题?直接摘百度—— 旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的...

    首先,什么是TSP问题?直接摘百度——

    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

    显然这是一个寻求最短路径的问题,对于这类问题解法很多。如果没有了解过动态规划的思想,先来考虑一下一种很常见的生活场景。比如,某市长需要评选最佳学生,那么市长需要怎么做呢?理所当然地,要知道最佳学生是谁,该学生必然是某学校的最佳学生,也必然是某年级、某班的最佳学生。

    也就是说想要解决一个复杂的问题,可以把它分解成较小的子问题,在子问题中选择最优解。上述例子就是这样的,市长选一个最佳学生不需要了解全市所有的同学,会累死的!他只要在各学校选出来的学生之中选一个就行。校长也不需要了解全校学生,他同样是在各年级最佳学生中选一位就行;到了级长,也是同样的操作;最后到班级,老师直接选一位最好的就行。这样,在解决问题的每一个阶段,工作量都是很小的,谁都不会累死,那么问题到最后都是可解决的。

    解决这个问题的步骤总结为:

    寻找市最佳->寻找校最佳->寻找年级最佳->寻找班级最佳

    其实这个就是动态规划的核心思想,一看专业名词好像很高深,但生活中是个正常人都会这么思考。

    动态规划,(dynamic programming,代码中一般都用dp简称)——将一个问题拆成几个子问题,分别求解这些子问题,最后求出大问题的解。

    那么问题来了,如何用动态规划求解tsp?首先我们可以沿用刚刚的选最佳学生思路。当前,有n个城市,如何求最短路径?我们先来拆分子问题,将复杂问题简单化。怎么拆分呢?

    从数学角度分析一下

    经历n个城市的最短路径(用Ret表示)必定存在,设起点为Cx,假设这个最短的访问顺序为Cx,C1,C2,C3,... ,Cn-1, Cn,Cx.则有

    Ret = 前n个城市的最短路径+第n个城市到起点Cx的距离

    但其实我们还不知道哪个城市才应该是第n个,所以每个城市都要试一试,看看哪个城市是第n个时,ret取得最小值。所以实际上

    问题1:Ret = min{(前n个城市的最短路径)+(第n个城市到起点Cx的距离)}

    同理,再次分解子问题:

    问题2:前n个城市的最短路径 = min{(前n-1个城市的最短路径)+(第n个城市到第n-1个城市的距离)}

    继续不断分解。。。最后一个子问题是:

    前1个城市的最短路径 = min{(前0个城市的最短路径)+(第1个城市到第0个城市的距离)}

    重点来了,最终这个最小子问题只要是可以解决的,那么也就一步步向上反推解决tsp问题。那么这个最小子问题是不是可以解决的呢?

    看等号左边,(第1个城市到第0个城市的距离)这个是tsp问题的给定的已知参数,也就是起点到每一个城市的距离,ok,这部分没问题;困扰的是——(前0个城市的最短路径),这个是多少???其实很简单,中文表达有些绕,前0个城市的最短路径其实就是起点Cx到起点Cx的距离,那肯定是零啊 = 。= (PS:这个其实就是动态规划的边界)

    好了,那么现在问题很清晰了,把我们的公式搬出来!用V表示需要途经若干个城市的集合,x是起点,i表示若干个城市中的某一个点,d(V,x-->i)表示从x出发,中间经历了V集合中所有的城市,最后到达城市i的最短路径。

    先公式表述一个最简单的,就是上述的(前0个城市的最短路径),前0个城市,也就是V中只有起点Cx,第一个变量V={x};起点Cx走到起点Cx,其实就是没动~所以有:

    • ① d({x}, x-->x)= 0;

    问题2则可以变成(n-1到n的距离表示为Cn-1-->n):

    • ② d(V+{Cn}, x-->n) = min {d(V, x-->(n-1)) + Cn-1-->n}

    问题1则可以变成(n回到起点Cx的距离表示为Cn-->x):

    • ③ Ret = min{d(V, x-->n) + Cn-->x}

    PS:其实上3式就是动态规划的边界、状态转移和最优解方程,一共有2的n次方种状态,每种状态要尝试一次各个节点,算法的时间复杂度O(2^n*n*n)

    算法设计好了,开始码代码,先整理一下思路。动态规划一般都有两种实现方式,第一种是从子问题出发,不断求解,这个叫迭代;第二种是从最终问题开始,不断划分子问题这个叫递归。我觉得迭代比较容易实现,代码实现就是先解决方程①,不断推到方程②,最后求解方程③。其中有个问题需要思考的就是,如何用代码去表示城市的集合?这里可以使用二进制数字和位运算的技巧。也就是

    用一个二进制数表示这个集合V——如果城市 k 在集合 V中,那么存储集合的变量 i 的第 k 位就为 1,否则为 0。由于有 n 个城市,所有的状态总数我们用 M 来表示,那么很明显:M = 2^n,而 0 到 2^n -1 的所有整数则构成了 V的所有情况需要注意的是由于起点是确定的,也就是说集合 V中必定包含起点,所以这个二进制数字的第1位必须为1。

    Python我不会,我查了一下python同样是有位运算的,所以也可以实现~下面看C++代码~

    #include<bits/stdc++.h>
    using namespace std;
    
    #define SQR(x) ((x)*(x))
    #define INVALID_NUM (0xffffffff)
    
    string file_name = "haha.txt";// 原始数据存放的文件名
    int SUM;// 一共有多少个城市
    double **DP; // 动态规划数组DP[i][j],i表示城市的集合V,
    //j表示某一个城市结点,对应着方程中的d{V, x->j}
    double **cityDistance; // 城市之间的距离
    
    // 定义结构体
    struct cityNode{
        int input(FILE *fp){//从数据文件中读取一个城市的座标信息
            return fscanf(fp, "%lf %lf", &x, &y);
        }
        double x, y; // 城市结点的坐标
    }*pCityNode;
    
    //计算两个城市的距离
    double calculateCityDistance(const cityNode &a, const cityNode &b){
        return sqrt(SQR(a.x - b.x) + SQR(a.y - b.y));
    }
    
    void readDataFromFile(){ // 数据读入
        FILE *pFile = fopen(file_name.c_str(), "r");
        fscanf(pFile, "%d", &SUM);//首先读入城市的总数
        if(!pFile){
            perror("errno");
        }
        pCityNode = new cityNode[SUM];
        cityDistance = new double*[SUM];
    
        for (int i = 0; i < SUM; i ++)
            pCityNode[i].input(pFile);
        for (int i = 0; i < SUM; i ++){
            cityDistance[i] = new double[SUM];
            for (int j = 0; j < SUM; j ++)
                cityDistance[i][j] = calculateCityDistance(pCityNode[i], pCityNode[j]);
        }
        fclose(pFile);
        return;
    }
    void init(){ // 数据初始化
        DP = new double*[(1 << SUM)];
        for(int i = 0; i < (1 << SUM); i++){
            DP[i] = new double[SUM];
            for(int j = 0; j < SUM; j++)
                DP[i][j] = INVALID_NUM;
        } // 初始化为一个无效值
        return;
    }
    double findShortestPath(){
      int totalState = (1 << SUM);
      // 1<<N表示2^N,城市集合总共有2^N种状态
      DP[1][0] = 0;// 从起点出发回到起点的cost为0,这里是方程1。
        for (int i = 1; i < totalState; i++){// 遍历V的所有状态
            for (int j = 1; j < SUM; j++){// 选择下一个加入集合的城市
    
                if (!(i & 1)) continue; // 起点必定在V中,所以i的第1位必定为1,不是1的就跳过
                if (i & (1 << j)) continue;// 城市已经存在于集合V之中,跳过
    
                for (int k = 0; k < SUM; k++){// 在V这个城市集合中尝试每一个还未进入集合的结点
                    if (i & (1 << k)){// 确保k已经在集合之中
                        // k每次变化都会产生一个新的数值,最小的数值就是局部的最优解,这里是方程2
                        DP[(1 << j) | i][j] = min(DP[(1 << j) | i][j], DP[i][k] + cityDistance[k][j]);
                    }
                }
            }
        }
        double result = INVALID_NUM;
        for (int i = 0; i < SUM; i ++)
            // 加上回到起点城市的距离。这里是方程3
            result = min(DP[totalState - 1][i] + cityDistance[i][0], result);
        return result;
    }
    int main(){
        readDataFromFile();
        init();
        cout << "最短的路程是:" << findShortestPath() << endl;
        delete[] DP;
        delete[] pCityNode;
        delete[] cityDistance;
        return 0;
    }
    

    最后,把数据文件加载进来就ok啦

    文件内容格式需要是下面这样的~第一行是城市数量,后面是城市的x坐标+y左边。比如有16个城市点

    16
    8.2 20.4
    9.7 26.5
    4.5 2.3
    6.6 3.2
    3.8 1.4
    7.6 1.9
    8.2 13.1
    3.2 20.4
    1.3 9.1
    4.7 13.5
    6.8 -5.1
    8.7 5.3
    38.5 15.3
    3.1 15.7
    3.9 14.2
    39.6 9.6

     

     

     

     

     

    展开全文
  • 最近在做毕业设计,从0学习了matlab和一些启发式算法,其中有个部分为tsp问题,思来想去想复现参考论文中的动态规划求解,网上看了一些资料,代码都是c++或者java的,这里分享下自己用matlab写的代码: 注:参考资料...

    最近在做毕业设计,从0学习了matlab和一些启发式算法,其中有个部分为tsp问题,思来想去想复现参考论文中的动态规划求解,网上看了一些资料,代码都是c++或者java的,这里分享下自己用matlab写的代码:
    注:参考资料为https://blog.csdn.net/hytfly/article/details/95739609
    本算法相关问题情景和解题思路均通过学习参考资料所获,欢迎各位在评论区交流学习

    在这里插入图片描述

    展开全文
  • 某推销员要从城市v1出发,访问其它城市v2,v3,…,v6各一次且仅一次,最后返回v1。D为各城市间的距离矩阵。 问:该推销员应如何选择路线,才能使总的行程最短?
  • distence_matrix = np.zeros([n,n]) for i in range(0, n): for j in range(n): distence = distance(cities[i],cities[j]) distence_matrix[i][j] = distence 使用动态规划求解TSP问题: S = Solution(distence_...
  • 动态规划求解TSP

    2019-05-31 10:51:03
    动态规划的方法的最大难点就在于初始变量的确定,选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),设s出发点,其中i是一个点,而S是点的集合,这个变量的意思就是从i出发,...
  • 动态规划求解TSP问题 C++

    万次阅读 多人点赞 2018-07-01 14:06:16
    “鸡汤惠”帮“鸭汤莹”看代码,于是翻出了自己写的动态规划求解TSP问题,于是整理了一下。(算法思想在知识点整理的部分,这里是具体实现的代码) 问题描述:  TSP问题是指旅行家要旅行n个城市,要求各个城市...
  • 动态规划求解TSP问题

    千次阅读 2020-04-19 18:04:30
    一、求解TSP问题 1、问题描述 TSP问题(担货郎问题,旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短 各个城市间的距离可以用代价矩阵来表示。 2、...
  • 本资源为用python语言写的使用动态规划求解TSP问题,并包含较为详细的中文注释。
  • 动态规划求解TSP(旅行商)问题

    万次阅读 多人点赞 2012-11-28 20:29:40
    某推销员要从城市v1出发,访问其它城市v2,v3,…,v6各一次且仅一次,最后返回v1。D为各城市间的距离矩阵。问:该推销员应如何选择路线,才能使总的行程最短?   ...阶段k:已遍历过k个结点,k=1,2…6,7。...
  • 动态规划法】求解TSP问题

    千次阅读 2019-07-14 23:50:18
    假设从顶点i出发,令d(i, V’ )表示从顶点i出发经过V’ 中各个顶点一次且仅一次,最后回到出发点(i)的最短路径长度,开始时, V’ =V-{i},于是,TSP问题动态规划函数为: d(i, V’ )=min{cik+d(k, V’ -{k})...
  • 解题思路主要有两部分:第一部分:i为当前节点(城市),S为还没有遍历的节点(城市集合),表示从第i个节点起,经历S集合中所有的点,到达终点的最短路径长度。因此有:第二部分,回溯,找到...代码如下:# tsp问题clas...
  • 对基于动态规划TSP问题求解 ,这个源码很好的说明其中的求解过程,以及数据结构的设计问题
  • 针对蚁群算法搜索空间大、收敛速度慢、容易陷入局部最优等缺陷,提出一种基于动态凸包引导的偏优规划蚁群算法。改进后的算法动态控制蚂蚁的待选城市范围,有助于在跳出局部最优并向全局最优逼近的基础上减少蚂蚁搜索...
  • # tsp问题 class Solution: def __init__(self,X,start_node): self.X = X #距离矩阵 self.start_node = start_node #开始的节点 self.array = [[0]*(2**len(self.X)) for i in range(len(self.X))] #记录处于x...
  • 状压dp求解TSP问题

    2019-08-02 17:16:49
    状压dp求解TSP问题 尝试过用贪心算法求解TSP问题,但是并...所以可以判断具有最优子结构和重叠子问题时,该问题可以用动态规划求解。 问题描述: 小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市...
  • 旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...
  • 动态规划问题使用GA和PSO算法求解10个城市TSP问题动态规划
  • 思路:使用动态规划,dp[i][j],其中i是压缩的状态,表示第i个城市是否已经走过,j表示第j个城市。dp[i][j]表示状态是i且当前所在的城市是j时最小代价。转移方程: dp[i|(1<<k)][k] = min(dp[i|(1<<k)]...
  • 这篇文章的代码是笔者自己用动态规划的思想用matlab实现的,里面的用到了矩阵运算和matlab内置函数的使用,相比c写起来代码少了很多,数学好的看起来应该更加简单易懂。 但是是根据一位大牛的文章写的,这里附上他...
  • 遗传算法求解TSP问题

    2020-07-22 19:12:13
    传统精确算法:穷举法,动态规划 近似处理算法:贪心算法,改良圈算法,双生成树算法 智能算法:模拟退火,粒子群算法,蚁群算法,遗传算法等 2、遗传算法 2.1 遗传算法简介 遗传算法的实质是通过群体搜索技术,根据...
  • TSP问题描述:  旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是...
  • 本报告仅供参考,不足之处请指正,版权由博主所有,未经同意禁止应用于非法用途,请下载者自觉。
  • 经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。...代码包含遗传算法和动态规划求解这个问题,里面有完整源代码,并且有详细注释,还有两者的比较分析。
  • TSP问题(python) 排序问题 读取文件格式:第一行为城市数目,剩余行为各城市坐标 (1) 城市全排列,在所有解决方案中选择最好的一个(解决20个城市的时候会有困难了(见维基百科)) # 生成全排列列表的函数 def ...

空空如也

空空如也

1 2 3 4 5
收藏数 94
精华内容 37
关键字:

动态规划求解tsp问题