数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Travelling Salesman Problem (Dynamic Approach)


Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n−1)! number of possibilities. Thus, maintaining a higher complexity.

However, instead of using brute-force, using the dynamic programming approach will obtain the solution in lesser time, though there is no polynomial time algorithm.

Travelling Salesman Dynamic Programming Algorithm

Let us consider a graph G = (V,E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.

Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don't repeat any of them. Hence, this is an appropriate sub-problem.

For a subset of cities S $\epsilon$ {1,2,3,...,n} that includes 1, and j $\epsilon$ S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.

When |S|> 1 , we define 𝑪C(S,1)= $\propto$ since the path cannot start and end at 1.

Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that

$$C\left ( S,j ight )\, =\, min\, C\left ( S\, -\, \left\{j ight\},i ight )\, +\, d\left ( i,j ight )\: where\: i\: \epsilon \: S\: and\: i eq j$$

Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
   for all subsets S є {1, 2, 3, … , n} of size s and containing 1
      C (S, 1) = ∞
   for all j є S and j ≠ 1
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Analysis

There are at the most 2n.n sub-problems and each one takes linear time to solve. Therefore, the total running time is O(2n.n2).

Example

In the following example, we will illustrate the steps to solve the travelling salesman problem.

travelling_salesman_problem

From the above graph, the following table is prepared.

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0

S = $\Phi$

$$Cost\left ( 2,\Phi ,1 ight )\, =\, d\left ( 2,1 ight )\,=\,5$$

$$Cost\left ( 3,\Phi ,1 ight )\, =\, d\left ( 3,1 ight )\, =\, 6$$

$$Cost\left ( 4,\Phi ,1 ight )\, =\, d\left ( 4,1 ight )\, =\, 8$$

S = 1

$$Cost(i,s)=min\left\{Cos\left ( j,s-(j) ight )\, +\,d\left [ i,j ight ] ight\}$$

$$Cost(2,\left\{3 ight\},1)=d[2,3]\, +\, Cost\left ( 3,\Phi ,1 ight )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(2,\left\{4 ight\},1)=d[2,4]\, +\, Cost\left ( 4,\Phi ,1 ight )\, =\, 10\, +\, 8\, =\, 18$$

$$Cost(3,\left\{2 ight\},1)=d[3,2]\, +\, Cost\left ( 2,\Phi ,1 ight )\, =\, 13\, +\, 5\, =\, 18$$

$$Cost(3,\left\{4 ight\},1)=d[3,4]\, +\, Cost\left ( 4,\Phi ,1 ight )\, =\, 12\, +\, 8\, =\, 20$$

$$Cost(4,\left\{3 ight\},1)=d[4,3]\, +\, Cost\left ( 3,\Phi ,1 ight )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(4,\left\{2 ight\},1)=d[4,2]\, +\, Cost\left ( 2,\Phi ,1 ight )\, =\, 8\, +\, 5\, =\, 13$$

S = 2

$$Cost(2,\left\{3,4 ight\},1)=min\left\{\begin{matrix} d\left [ 2,3 ight ]\,+ \,Cost\left ( 3,\left\{ 4 ight\},1 ight )\, =\, 9\, +\, 20\, =\, 29 \ d\left [ 2,4 ight ]\,+ \,Cost\left ( 4,\left\{ 3 ight\},1 ight )\, =\, 10\, +\, 15\, =\, 25 \ \end{matrix} ight.\, =\,25$$

$$Cost(3,\left\{2,4 ight\},1)=min\left\{\begin{matrix} d\left [ 3,2 ight ]\,+ \,Cost\left ( 2,\left\{ 4 ight\},1 ight )\, =\, 13\, +\, 18\, =\, 31 \ d\left [ 3,4 ight ]\,+ \,Cost\left ( 4,\left\{ 2 ight\},1 ight )\, =\, 12\, +\, 13\, =\, 25 \ \end{matrix} ight.\, =\,25$$

$$Cost(4,\left\{2,3 ight\},1)=min\left\{\begin{matrix} d\left [ 4,2 ight ]\,+ \,Cost\left ( 2,\left\{ 3 ight\},1 ight )\, =\, 8\, +\, 15\, =\, 23 \ d\left [ 4,3 ight ]\,+ \,Cost\left ( 3,\left\{ 2 ight\},1 ight )\, =\, 9\, +\, 18\, =\, 27 \ \end{matrix} ight.\, =\,23$$

S = 3

$$Cost(1,\left\{2,3,4 ight\},1)=min\left\{\begin{matrix} d\left [ 1,2 ight ]\,+ \,Cost\left ( 2,\left\{ 3,4 ight\},1 ight )\, =\, 10\, +\, 25\, =\, 35 \ d\left [ 1,3 ight ]\,+ \,Cost\left ( 3,\left\{ 2,4 ight\},1 ight )\, =\, 15\, +\, 25\, =\, 40 \ d\left [ 1,4 ight ]\,+ \,Cost\left ( 4,\left\{ 2,3 ight\},1 ight )\, =\, 20\, +\, 23\, =\, 43 \ \end{matrix} ight.\, =\, 35$$

The minimum cost path is 35.

Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards.

When s = 1, we get the minimum value for d [4, 2] but 2 and 4 is already selected. Therefore, we select d [4, 3] (two possible values are 15 for d [2, 3] and d [4, 3], but our last node of the path is 4). Select path 4 to 3 (cost is 9), then go to s = ϕ step. We get the minimum value for d [3, 1] (cost is 6).

get_minimum_value

Implementation

Following are the implementations of the above approach in various programming languages −

#include <stdio.h>
#include <limits.h>
#define MAX 9999
int n = 4;
int distan[20][20] = {
   {0, 22, 26, 30},
   {30, 0, 45, 35},
   {25, 45, 0, 60},
   {30, 35, 40, 0}};
int DP[32][8];
int TSP(int mark, int position) {
   int completed_visit = (1 << n) - 1;
   if (mark == completed_visit) {
       return distan[position][0];
   }
   if (DP[mark][position] != -1) {
       return DP[mark][position];
   }
   int answer = MAX;
   for (int city = 0; city < n; city++) {
      if ((mark & (1 << city)) == 0) {
         int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);
         answer = (answer < newAnswer) ? answer : newAnswer;
      }
   }
   return DP[mark][position] = answer;
}
int main() {
   for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < n; j++) {
         DP[i][j] = -1;
      }
   }
   printf("Minimum Distance Travelled -> %d
", TSP(1, 0));
   return 0;
}

Output

Minimum Distance Travelled -> 122
#include<iostream>
using namespace std;
#define MAX 9999
int n=4;
int distan[20][20] = {{0, 22, 26, 30},
   {30, 0, 45, 35},
   {25, 45, 0, 60},
   {30, 35, 40, 0}
};
int completed_visit = (1<<n) -1;
int DP[32][8];
int TSP(int mark, int position){
   if(mark==completed_visit) {
      return distan[position][0];
   }
   if(DP[mark][position]!=-1) {
      return DP[mark][position];
   }
   int answer = MAX;
   for(int city=0; city<n; city++) {
      if((mark&(1<<city))==0) {
         int newAnswer = distan[position][city] + TSP( mark|(1<<city),city);
         answer = min(answer, newAnswer);
      }
   }
   return DP[mark][position] = answer;
}
int main(){
   for(int i=0; i<(1<<n); i++) {
      for(int j=0; j<n; j++) {
         DP[i][j] = -1;
      }
   }
   cout << "Minimum Distance Travelled -> " << TSP(1,0);
   return 0;
}

Output

Minimum Distance Travelled -> 122 
public class Main {
   static int n = 4;
   static int[][] distan = {
      {0, 22, 26, 30},
      {30, 0, 45, 35},
      {25, 45, 0, 60},
      {30, 35, 40, 0}
   };
   static int completed_visit = (1 << n) - 1;
   static int[][] DP = new int[32][8];
   static int TSP(int mark, int position) {
      if (mark == completed_visit) {
         return distan[position][0];
      }
      if (DP[mark][position] != -1) {
         return DP[mark][position];
      }
      int answer = Integer.MAX_VALUE;
      for (int city = 0; city < n; city++) {
         if ((mark & (1 << city)) == 0) {
            int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);
            answer = Math.min(answer, newAnswer);
         }
      }
      DP[mark][position] = answer;
      return answer;
   }
   public static void main(String[] args) {
      for (int i = 0; i < (1 << n); i++) {
         for (int j = 0; j < n; j++) {
             DP[i][j] = -1;
         }
      }
      System.out.println("Minimum Distance Travelled -> " + TSP(1, 0));
   }
}

Output

Minimum Distance Travelled -> 122
import sys
n = 4
distan = [[0, 22, 26, 30],
          [30, 0, 45, 35],
          [25, 45, 0, 60],
          [30, 35, 40, 0]]
completed_visit = (1 << n) - 1
DP = [[-1 for _ in range(n)] for _ in range(2 ** n)]
def TSP(mark, position):
    if mark == completed_visit:
        return distan[position][0]
    if DP[mark][position] != -1:
        return DP[mark][position]
    answer = sys.maxsize
    for city in range(n):
        if (mark & (1 << city)) == 0:
            new_answer = distan[position][city] + TSP(mark | (1 << city), city)
            answer = min(answer, new_answer)
    DP[mark][position] = answer
    return answer
for i in range(1 << n):
    for j in range(n):
        DP[i][j] = -1
print("Minimum Distance Travelled ->", TSP(1, 0))

Output

Minimum Distance Travelled -> 122