数模matlab入门教程-003-TSP问题通用建模方法与C++求解方法

文章目录

• 1 TSP求解方法-暴力,动规
• 2 动态规划
• 3 暴力

最近有点忙，所以搁置了该部分的更新；

上篇文章来的，就直接。这次的主要是针对C++来讲解TSP的求解；

为什么讲C++而不用matlab？

我个人觉得了解c++的思想，有助于理解求解tsp问题的思想；

如果觉得理解起来有点费力气，也要坚持一下

下一篇就会是用matlab来解决这个问题，这次我一定会在两周内把这篇和下篇文章更新出来；

1 TSP求解方法-暴力,动规

C++来求解的话，一般涉及到两种方法：暴力（递归+回溯） ，动态规划

暴力的话 一般适用于数据规模较小的情况，暴力引起的问题也显而易见，其时间复杂度增长非常快；
这个方法不是非常优，所以放在第三章末尾介绍，

所以一般求解tsp问题，是使用动态规划来进行解决，其中还涉及到二进制优化，放在第二章介绍。

本篇还是以上一篇文章中的试题作为例题：
四个城市之间的距离邻接矩阵G为：

	G0	G1	G2	G3
G0	-	30	6	4
G1	30	-	5	10
G2	6	5	-	20
G3	4	10	20	-

2 动态规划

---

2.1 动态规划思想

假设我们找到了一条最短路径为： G0->G1->G2->G3->G0

则可以确定，G1->G2->G3->G0 必然是 G1->G0通过其他个点的一条最短路径；

Dis(总回路) = Dis(G0,G1) + Dis（G1,G2,G3,G0）;

进而上述问题可以化为：
通用公式
Dis(回路) =Min{ Dis(G0,G1)+Dis(G1,…,0)， Dis(G0,G2)+Dis(G2,…,G0)，Dis(G0,G3)+Dis(G3,…,G0),…} ;
此例题
Dis(回路) =Min{ Dis(G0,G1)+Dis(G1,…,G0)， Dis(G0,G2)+Dis(G2,…,G0)，Dis(G0,G3)+Dis(G3,…,G0)} ;

注*：
上述公式中Dis(G1,…,G0)，代表的是一个最短距离，需要递归继续求解得到；并不是一个确切的顺序，并不是上面提到的Dis（G1,G2,G3,G0）;

规范化地表达上面的公式

• 将V定义为一个点集；
• d(i,V) 表示从i点经过点集Ｖ各点一次之后回到出发点的最短距离;*

例如d(0, {1, 2, 3})表示的是从0点出发，经过点1,2,3后再回到0的最短距离，也就是上述TSP问题就可以用d(0, {1, 2, 3})来表示。

例如d(1, { 2, 3})表示的是从1点出发，经过点2,3后再回到0的最短距离;
这样定义的目的是为了方便理解，没有码错字！

• 定义 d(i,V’) ＝ min {Cik+d(k,V－{k})} (k∈V’)
• d(k，{ }) ＝ Cik (k≠i)
• Ｃik表示i到k的距离

从城市0出发，经城市1、2、3然后回到城市0的最短路径长度是：
d(0, {1, 2, 3}) = min { C01 + d(1, {2,3}), C02+ d(2,{1,3}),C03+ d(3, {1, 2})}
这是最后一个阶段的决策，它必须依据d(1, { 2, 3})、
d(2, {1, 3})和d(3, {1, 2})的计算结果
划分子问题
而：
d(1, {2, 3})=min{C12+d(2, {3}), 　C13+ d(3, {2})}
d(2, {1, 3})=min{C21+d(1, {3}), 　C23+ d(3, {1})}
d(3, {1, 2})=min{C31+d(1, {2}), 　C32+ d(2, {1})}
继续写下去：
d(1, {2})= C12+d(2, {}) ；d(2, {3})=C23+d(3, {}) ；d(3, {2})= C32+d(2, {})
d(1, {3})= C13+d(3, {})；d(2, {1})=C21+d(1, {})；d(3, {1})= C31+d(1, {})

建立dp表

i \ j	{ }	{1}	{2}	{3}	{1,2}	{1,3}	{2,3}	{1,2,3}
0								min(59,25,41) = 25
1	30		11	14			min(29,36) = 29
2	6	35		24		min(19,60) = 19
3	4	40	26		min(21,55)=21

有人可能会问为什么都是从0点出发：
经过的路线是一条经过所有城市的闭合回路, 因此从哪一点出发是无所谓的, 因此不妨设从城市0出发。

---

2.2 状态压缩优化+动态规划代码

其中状态压缩呢就是一种表示集合V的方法；简单来讲就是用二进制将集合表示出来比如：
共有四个点，则有可以用四位来表示，这四位分别是0000。表示方法如下：
{1} - 0001 -
{2} - 0010
{3} - 0100
{1,2} - 0011
{1,3} - 0101
{2,3} - 0110
{1,2,3} - 0111

---

用此方法可以节省空间复杂度：n个城市下，城市距离二维矩阵表空间复杂度是n*n，计算过程DP表空间复杂度

---

借用此方法则状态转移方程变为：
dp[ i ][ j]=min( dp[ i ^ (1<<j) ][ k ] + Ckj );

i ^ (1<<j)的意思是将j这个城市从i状态中去掉。

const int MAX = 0x0fffffff;
int TSPCOOM(vector<vector<int>> &mmap){
    
    int n = mmap.size();
    int stateNum = 1 << (n-1);  对1进行左移n-1位，值刚好等于2^(n-1)
   
    vector<vector<int> > dp(n,vector<int>(stateNum,MAX)); // dp表，n行, stateNum列
    dp[1][0] = 0; 

    //更新第一列
    for (int i = 0; i < n;i++)
        dp[i][0] = mmap[i][0];

    // dp[i][j]中的i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2
    // dp[i][j]表示经过了i中的城市，并且以j结尾的路径长度

    //从城市0出发，所以经过城市0，以城市0结尾的路径为0
    //从城市0出发，更新和其他城市的距离
        
    for (int j = 1; j < stateNum; j++)
    {
        for (int i = 0; i < n; i++) //这个i不仅代表城市号，还代表第i次迭代
        {
            //为了方便求最小值,初始化时已将dp[i][j] 其设为最大值
            if ( ((j >> (i - 1)) & 1) == 0) 
            {
                // 因为j就代表城市子集V[j],((j >> (i - 1))是把第i号城市取出来
                // 并位与上1，等于0，说明是从i号城市出发，经过城市子集V[j]，回到起点0号城市
                for (int k = 0; k < n; k++) // 这里要求经过子集V[j]里的城市回到0号城市的最小距离
                {
                    if (((j >> (k - 1)) & 1) == 1) 
                    { 
                        //遍历城市子集V[j]
                        //设s=j ^ (1 << (k - 1))
                        //dp[k][j ^ (1 << (k - 1))，是将dp定位到，从k城市出发，经过城市子集V[s]，回到0号城市所花费的最小距离
                        //怎么定位到城市子集V[s]呢，因为如果从k城市出发的，经过城市子集V[s]的话
                        //那么V[s]中肯定不包含k了，那么在j中把第k个城市置0就可以了，而j ^ (1 << (k - 1))的功能就是这个
                        //没有访问过k，且从这里到k的距离小于原来的距离，则更新
                        //dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + mmap[j][k]);
                        dp[i][j] = min(dp[i][j], mmap[i][k] + dp[k][j ^ (1 << (k - 1))]); //^异或
                        //还有怎么保证dp[k][j ^ (1 << (k - 1))]的值已经得到了呢，
                        //注意所有的计算都是以dp表为准，从左往右从上往下的计算的，每次计算都用到左边列的数据
                        //而dp表是有初试值的，所以肯定能表格都能计算出来
                    }
                }
            }
        }
    }
    int res = MAX;
    cout << dp[0][stateNum - 1] << endl;
    return res;
}



int main(int argc, char const *argv[])
{
   int n;
   vector<vector<int>> edges = {
       {0, 30, 6, 4},
       {30, 0, 5, 10},
       {6, 5, 0, 20},
       {4, 10, 20, 0}};

   cout << TSPCOOM(edges) << endl;
   return 0;
}

3 暴力