Traveling Salesman Problem(旅行商问题)
in 算法 with 0 comment

Traveling Salesman Problem(旅行商问题)

in 算法 with 0 comment

旅行商问题(TSP):给定一组城市和每对城市之间的距离,找到每个城市只访问一次并返回起点的最短路径。

注意Hamiltonian Cycle(哈密顿回路)TSP之间的区别。 Hamiltoninan Cycle问题是找出是否存在一次访问每个城市一次的旅行。 在这里我们知道Hamiltonian Cycle存在(因为graph是完整的)并且实际上存在许多这样的Cycle,问题是找到最小权重的Hamiltonian Cycle

例如,请考虑下图中所示的graph。 图中的TSP路径是1-2-4-3-1。 这次旅行的费用是10 + 25 + 30 + 15,即80

这是一个非常著名的NP难题。 对于这个问题,不存在多项式时间复杂度的解法。以下是旅行商问题的不同解决方案。

朴素的解决方案:

// implementation of traveling Salesman Problem 
int travllingSalesmanProblem(int graph[][V], int s) 
{ 
    // store all vertex apart from source vertex 
    vector<int> vertex; 
    for (int i = 0; i < V; i++) 
        if (i != s) 
            vertex.push_back(i); 
  
    // store minimum weight Hamiltonian Cycle. 
    int min_path = INT_MAX; 
    do { 
        // store current Path weight(cost) 
        int current_pathweight = 0;   
        // compute current path weight 
        int k = s; 
        for (int i = 0; i < vertex.size(); i++) { 
            current_pathweight += graph[k][vertex[i]]; 
            k = vertex[i]; 
        } 
        current_pathweight += graph[k][s]; 
  
        // update minimum 
        min_path = min(min_path, current_pathweight); 
         
    } while (next_permutation(vertex.begin(), vertex.end())); 
  
    return min_path; 
} 

这个解法在之前的Hamiltoninan Cycle中也提到过,对于较大的n来说,这种做法当然是不可取的。这个问题可以通过动态规划的方法来解决。

对于给定的顶点集合为{1,2,3,4 ......}。我们将1视为输出的起点和终点。对于每个其他顶点i(除1之外),我们找到一条到i的最短路径,其中1为起点,i为结束点,所有顶点恰好出现一次。假设这条路径的总长度为cost(i),则我们最后的路径长度将是cost(i)+dist(i,1),其中dist(i,1)是从i1的距离。最后,我们返回所有[cost(i)+dist(i,1)]值的最小值。到目前为止一切都看起来很简单,现在的问题就变成了如何获得cost(i)

我们可以使用动态规划来计算cost(i)。首先我们定义$C(S,i)$表示对于集合$S$中每个顶点i来说,从1开始到i结束的最短路径长度。我们从大小为2的所有子集开始,并计算所有子集的$C(S,i)$,其中$S$是子集,然后我们计算大小为3的所有子集$S$的$C(S,i)$,依此类推。请注意,每个子集中必须存在1

如果$S$的大小为2,那么$S$必须是$\{1,i\}$,$C(S, i) = dist(1, i)$
否则,如果$S$的大小大于2,$C(S, i) = min \{C(S - {i}, j) + dist(j, i)\}$其中$j$属于$S$,$j \neq i$且$j \neq 1$。

对于一组大小为n的集合,我们考虑n-2个子集,每个子集的大小为n-1,使得所有子集中都没有第n个数。

使用上述递归关系,我们就可以写出相应的动态规划的代码。最多有$O(n*2^n)$个子问题,每个子问题需要线性时间来解决。因此总运行时间为$O(n^2*2^n)$。时间复杂度远小于$O(n!)$,但仍然呈指数级。所需空间也是指数级的。因此,即使对于稍高数量的顶点,这种方法也是不可行的。

int n=4;
int dist[10][10] = {
        {0,20,42,25},
        {20,0,30,34},
        {42,30,0,10},
        {25,34,10,0}
};
int VISITED_ALL = (1 << n) -1;
int dp[16][4];
int cost(int mask,int pos)
{
    if (mask == VISITED_ALL){
        return dist[pos][0];
    }
    if (dp[mask][pos] != -1){
       return dp[mask][pos];
    }

    //Now from current node, we will try to go to every other node and take the min ans
    int ans = INT_MAX;

    //Visit all the unvisited cities and take the best route
    for (int city = 0; city < n; city++)
    {
        if ((mask & (1 << city)) == 0)
        {
            int newAns = dist[pos][city] + cost(mask | ( 1 << city), city);
            ans = min(ans, newAns);
        }
    }
    return dp[mask][pos] = ans;
} 

我们稍微解释一下上面这个代码,其中mask表示我们访问的节点,假设我们有4各节点,如果mask=1111的话,表示cdba都访问过了,也就是mask=1<<4 - 1=1111;如果mask=0001,表示只有a访问过了,以此类推。那么我们就可以通过(mask & (1 << city)) == 0判断当前节点是不是被访问过。例如,对于节点a

city = 0
1 << 0 = 0001
mask = 0001
mask & (1 << city) == true

如果当前的节点没有被访问过,我们才进行后续操作。也就是递归调用cost。其中mask | ( 1 << city)表示对city进行访问,例如

city = 0
1 << 0 = 0001
mask = 0000
mask | (1 << city) = 0001

最后我们只要取每次结果的最小值即可。

前面已经说过,这个问题没有多项式时间的解决方法。但是有一些近似的算法来解决这个问题。仅当问题实例满足Triangle-Inequality(三角不等式)时,近似算法才有效。

三角不等式:从i到达顶点j的最远路径总是直接从i到达j,而不是通过其他一些顶点k(或顶点),即dist(i,j)总是小于或等于到dist(i,k) + dist(k,j)。三角不等式在许多实际情况中都有。

cost函数满足三角不等式时,我们可以为TSP设计一个近似算法,该算法返回一个最短路径长度不超过最优解的两倍。我们的想法是使用最小生成树(MST)。以下是基于MST的算法。

考虑以下示例。图中显示了以1为根构造的MSTMST的前序遍历为1-2-4-3。最后添加1给出1-2-4-3-1,这是该算法的输出。

在这种情况下,近似算法产生最佳路径,但它可能无法在所有情况下产生最佳路径。这个算法如何近似?上述算法产生的输出路径绝不会超过最佳路径的两倍。让我们看看上述算法如何保证这一点。

在理解这个问题之前,我们首先要知道full walkfull walk是指在先序遍历访问树的全部节点时列出的所有走的步骤。上面树的full walk将是1-2-1-4-1-3-1

从上述三个陈述中,我们可以得出结论,近似算法产生的输出结果绝不会超过最佳解决方案的两倍。

我们已经讨论了一个非常简单的2倍近似算法来解决旅行商问题。对于该问题还有其他更好的近似算法。例如,Christofides算法是1.5倍近似算法。

reference:

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

https://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/

https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/

https://codingblocks.com/resources/travelling-salesman/

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses