旅行商问题（动态规划方法，超级详细的）_仁者乐山智者乐水的博客 ...

二、测试用例

其中1,2,3,4,5代表五个城市。此模型可抽象为图，可用邻接矩阵c表示，如下图所示：

三、动态规划方程

假设从顶点s出发，令d(i, V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

推导：(分情况来讨论)

①当V为空集，那么 $d(i, V)$ ，表示直接从i回到s了，此时 $d(i,V) = c_{is}$ 且 $(i\neq s)$

②如果V不为空，那么就是对子问题的最优求解。你必须在V这个城市集合中，尝试每一个，并求出最优解。

注： $c_{ik}$ 表示选择的城市和城市i的距离， $d(k, V-(k))$ 是一个子问题。

综上所述，TSP问题的动态规划方程就出来了：

四、用例分析

现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)

这里只画出了d(1,{2,3,4}),由于篇幅有限这里就不画了。

①我们要求的最终结果是d(0,{1,2,3,4}),它表示，从城市0开始，经过{1,2,3,4}之中的城市并且只有一次，求出最短路径.。
②d(0,{1,2,3,4})是不能一下子求出来的，那么他的值是怎么得出的呢？看上图的第二层，第二层表明了d(0,{1,2,3,4})所需依赖的值。那么得出：

③d(1,{2,3,4})，d(2,{1,3,4})，d(3,{1,2,4})，d(4,{1,2,3})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3,4})

d(2,{1,3,4})，d(3,{1,2,4})，d(4,{1,2,3})同样需要这么求。

④按照上面的思路，只有最后一层的，当V为空集时，就可以满足 $d(i,V) = c_{is}$ 且 $(i\neq s)$ 该条件，直接求出dp数组部分的值。

五、数据结构

由上述动态规划公式d(i,V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。根据上述给的测试用例有5个城市编号0,1,2,3,4。那么访问n个城市，恰好访问每个城市一次，并最终回到出发城市的嘴短距离可表示为d(0,{1,2,3,4}),那么问题来了我们用什么数据结构表示d(i,V)，这里我们就可二维数据dp[N][M]来表示，N表示城市的个数，M表示集合的数量，即 $M = 2^{N-1}$ ,之所以这么表示因为集合V有 $2^{N-1}$ 个子集。根据测试用例可得出如下dp数组表格：

那么你们可能就有疑问了，为什么这么表示？这里说明一下比如集合{1,2,3,4}为什么用15表示，我们可以把集合中元素看成二进制1的位置（二进制从右开始看），1表示从右开始第一位为1,2表示从又开始第二位为1，所以集合{1,2,3,4}可表示二进制（1111）转化为十进制为15。再举个例子比如集合{1,3}表示为二进制为0101，十进制为5。所以我们求出dp[0][15]（通用表示dp[0][ $2^{N-1}-1$ ]）就是本题的最终解。

对于第y个城市，他的二进制表达为，1<<(y-1)。
对于数字x，要看它的第i位是不是1，那么可以通过判断布尔表达式 (((x >> (i - 1) ) & 1) == 1或者（x & (1<<(i-1))）!= 0的真值来实现。
由动态规划公式可知，需要从集合中剔除元素。假如集合用索引x表示，要剔除元素标号为i,我们异或运算实现减法，其运算表示为： x = x ^ (1<<(i - 1))。

六、最短路径顶点的计算

我们先计算dp[N][M]数组之后，我可以用dp数组来反向推出其路径。其算法思想如下：

比如在第一步时，我们就知道那个值最小，如下图所示：

因为dp[][]数组我们已经计算出来了，由计算可知C01+d(1,{2,3,4})最小，所以一开始从起始点0出发，经过1。接下来同样计算d(1,{2,3,4})

由计算可知C14+d(4,{2,3})所以0--->1---->4，接下来同理求d(4,{2,3})，这里就省略，读者可以自行计算。最终计算出来的路径为：0--->1--->4--->2--->3--->0

七、代码编写

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
#define N 5
#define INF 10e7
#define min(a,b) ((a>b)?b:a)
static const int M = 1 << (N-1);
//存储城市之间的距离
int g[N][N] = {{0,3,INF,8,9},
               {3,0,3,10,5},
               {INF,3,0,4,3},
               {8,10,4,0,20},
               {9,5,3,20,0}};
//保存顶点i到状态s最后回到起始点的最小距离
int dp[N][M] ;
//保存路径
vector<int> path;
//核心函数，求出动态规划dp数组
void TSP(){
    //初始化dp[i][0]
    for(int i = 0 ; i < N ;i++){
        dp[i][0] = g[i][0];
    //求解dp[i][j],先跟新列在更新行
    for(int j = 1 ; j < M ;j++){
        for(int i = 0 ; i < N ;i++ ){
            dp[i][j] = INF;
            //如果集和j(或状态j)中包含结点i,则不符合条件退出
            if( ((j >> (i-1)) & 1) == 1){
                continue;
            for(int k = 1 ; k < N ; k++){
                if( ((j >> (k-1)) & 1) == 0){
                    continue;
                if( dp[i][j] > g[i][k] + dp[k][j^(1<<(k-1))]){
                    dp[i][j] = g[i][k] + dp[k][j^(1<<(k-1))];
//判断结点是否都以访问,不包括0号结点
bool isVisited(bool visited[]){
    for(int i = 1 ; i<N ;i++){
        if(visited[i] == false){
            return false;
    return true;
//获取最优路径，保存在path中,根据动态规划公式反向找出最短路径结点
void getPath(){
    //标记访问数组
    bool visited[N] = {false};
    //前驱节点编号
    int pioneer = 0 ,min = INF, S = M - 1,temp ;
    //把起点结点编号加入容器
    path.push_back(0);
    while(!isVisited(visited)){
        for(int i=1; i<N;i++){
            if(visited[i] == false && (S&(1<<(i-1))) != 0){
                if(min > g[i][pioneer] + dp[i][(S^(1<<(i-1)))]){
                    min = g[i][pioneer] + dp[i][(S^(1<<(i-1)))] ;
                    temp = i;
        pioneer = temp;
        path.push_back(pioneer);
        visited[pioneer] = true;
        S = S ^ (1<<(pioneer - 1));
        min = INF;
//输出路径
void printPath(){
    cout<<"最小路径为：";
    vector<int>::iterator  it = path.begin();
    for(it ; it != path.end();it++){
        cout<<*it<<"--->";
    //单独输出起点编号
    cout<<0;
int main()
    TSP();
    cout<<"最小值为："<<dp[0][M-1]<<endl;
    getPath();
    printPath();
    return 0;
八、测试结果及性能分析  
时间复杂度： 
空间复杂度： 
九、更多动态规划相关题目 
动态规划经典题目-数据压缩之图像压缩 
动态规划经典题目-数据压缩之文本压缩 
动态规划经典题目-矩阵链乘法 
动态规划经典题目-字符串切分 
动态规划经典题目-字符串的编辑距离 
动态规划经典题目-最长单调递增子序列 
动态规划经典题目-最长公共子串 
动态规划经典题目-最长公共子序列 
动态规划经典题目-找零钱的方案数 
动态规划经典题目-找零钱的最少硬币数 
动态规划经典题目——滑雪问题(递归+记忆化搜索) 
动态规划经典题目——0-1背包 
动态规划经典题目——最大子矩阵和 
动态规划经典题目——数塔问题 
动态规划经典题目——最大连续子序列之和 
动态规划系列——原理与思想
                    一、题目一个售货员必须访问n个城市，恰好访问每个城市一次，并最终回到出发城市。	售货员从城市i到城市j的旅行费用是一个整数，旅行所需的全部费用是他旅行经过的的各边费用之和，而售货员希望使整个旅行费用最低。	（等价于求图的最短哈密尔顿回路问题）令G=(V, E)是一个带权重的有向图，顶点集V=(v0, v1, ..., vn-1)。从图中任一顶点vi出发，经图中所有其他顶点一次且只有一次，最...
	旅行商问题（Travelling Salesman Problem, 简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[dij]，其中dij表示城市i到城市j的距离，i，j=1，2 … n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。
一、动态规划解决旅行商问题
		要使用动态规划，需要问题本身有最优子结构，我们需要找到要解决的问题的子问题。题目要求，从0(a)出发，经过[1(b),2©,3(d)]这几个城市，然后回到0，使得花费最少。要实现这个要求，需要从下面
				回溯问题适合于解由向量的形式来构成的，这个向量空间中使用搜索的方法进行搜索，搜索使用宽度优先的方法。货郎问题又名旅行商问题，但其实更多教科书中更通用的叫法叫旅行商问题，下面来对旅行商问题使用回溯算法证明。
文章目录一、问题描述二、数学建模三、实例1、传统经典做法2、回溯算法四、总结
一、问题描述
有n个城市，已知任两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小 。
有n个城市，城市与城市之前有距离的，任意两个城市之间的距离是已知的，现在需要找一条回路，经过每一个城市1次，使得总
				什么是旅行商问题
旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。
从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列...
				好的，我可以回答这个问题。旅行商问题是一个经典的组合优化问题，目标是找到一条最短的路径，使得旅行商可以经过所有的城市并回到起点。在Python中，可以使用动态规划算法来解决这个问题。具体实现可以参考以下代码：
import sys
def tsp_dp(cities):
    n = len(cities)
    dist = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            dist[i][j] = distance(cities[i], cities[j])
    memo = {}
    def dp(pos, visited):
        if (pos, visited) in memo:
            return memo[(pos, visited)]
        if visited == (1 << n) - 1:
            return dist[pos][0]
        ans = sys.maxsize
        for i in range(n):
            if visited & (1 << i) == 0:
                ans = min(ans, dist[pos][i] + dp(i, visited | (1 << i)))
        memo[(pos, visited)] = ans
        return ans
    return dp(0, 1)
def distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
if __name__ == '__main__':
    cities = [(0, 0), (1, 1), (2, 2), (3, 3)]
    print(tsp_dp(cities))
这段代码使用了记忆化搜索的方式来实现动态规划，时间复杂度为O(n^2 * 2^n)。其中，n表示城市的数量。