c语言旅行商问题_C和C ++中的旅行商问题

ゞ浴缸里的玫瑰 2022-12-07 13:57 360阅读 0赞

c语言旅行商问题

Here you will learn about Travelling Salesman Problem (TSP) with example and also get a program that implements Travelling Salesman Problem in C and C++.

在这里，您将通过示例了解有关旅行推销员问题(TSP)的信息，并获得一个用C和C ++实现旅行推销员问题的程序。

Let say there are some villages (1, 2, 3, 4, 5). To work with worst case let assume each villages connected with every other villages. And there is a Salesman living in village 1 and he has to sell his things in all villages by travelling and he has to come back to own village 1.

假设有一些村庄(1、2、3、4、5)。 为了在最坏的情况下工作，假设每个村庄都与其他每个村庄相连。 并且有一个推销员住在村庄1，他必须通过旅行在所有村庄出售他的东西，他必须回到自己的村庄1。

He has to travel each village exactly once, because it is waste of time and energy that revisiting same village. This is same as visiting each node exactly once, which is **Hamiltonian Circuit**. But our problem is bigger than Hamiltonian cycle because this is not only just finding Hamiltonian path, but also we have to find shortest path.

他必须每个村只旅行一次，因为重新访问同一村是浪费时间和精力。 这与只访问每个节点一次( **汉密尔顿电路)相同** 。 但是我们的问题比哈密顿循环更大，因为这不仅要找到哈密顿路径，而且还必须找到最短路径。

Finally the problem is we have to visit each vertex exactly once with minimum edge cost in a graph.

最后的问题是，我们必须以最小的边成本在图形中精确地访问每个顶点一次。

Brute Force Approach takes O (nn) time, because we have to check (n-1)! paths (i.e all permutations) and have to find minimum among them.

蛮力进近需要O(n n )时间，因为我们必须检查(n-1)！ 路径(即所有排列)，并且必须在其中找到最小值。

The correct approach for this problem is solving using Dynamic Programming.

解决此问题的正确方法是使用动态编程解决。

Dynamic Programming can be applied only if main problem can be divided into sub-problems. Let’s check that.

只有将主要问题划分为子问题时，才能应用动态编程。 让我们检查一下。

## 使用动态规划的旅行商问题(TSP) **(**Travelling Salesman Problem (TSP) Using Dynamic Programming**)** ##

### 示例问题 **(**Example Problem**)** ###

![Travelling Salesman Problem (TSP)][Travelling Salesman Problem _TSP]

Above we can see a complete directed graph and cost matrix which includes distance between each village. We can observe that cost matrix is symmetric that means distance between village 2 to 3 is same as distance between village 3 to 2.

在上方，我们可以看到一个完整的有向图和成本矩阵，其中包括每个村庄之间的距离。 我们可以看到成本矩阵是对称的，这意味着村庄2到3之间的距离与村庄3到2之间的距离相同。

Here problem is travelling salesman wants to find out his tour with minimum cost.

这里的问题是旅行推销员希望以最少的费用找到自己的旅行。

Say it is T (1,\{2,3,4\}), means, initially he is at village 1 and then he can go to any of \{2,3,4\}. From there to reach non-visited vertices (villages) becomes a new problem. Here we can observe that main problem spitted into sub-problem, this is property of dynamic programming.

假设它是T(1，\{2,3,4\})，意味着，最初他在村庄1中，然后他可以去\{2,3,4\}中的任何一个。 从那里到达未访问的顶点(村庄)成为一个新问题。 在这里，我们可以观察到主要问题分解为子问题，这是动态编程的特性。

**Note:** While calculating below right side values calculated in bottom-up manner. Red color values taken from below calculations.

**注意：**在右下方计算时，以自底向上的方式计算值。 红色值来自以下计算。

T ( 1, \{2,3,4\} ) = minimum of

T(1，\{2,3,4\})=最小值

= \{ (1,2) + T (2,  \{3,4\} )     4+**6**=10

= \{(1,2)+ T(2，\{3,4\})4+ **6** = 10

= \{ (1,3)  + T (3, \{2,4\} )     1+**3**=4

= \{(1,3)+ T(3，\{2,4\})1+ **3** = 4

= \{ (1,4) + T (4, \{2,3\} )     3+**3**=6

= \{(1,4)+ T(4，\{2,3\})3+ **3** = 6

Here minimum of above 3 paths is answer but we know only values of (1,2) , (1,3) , (1,4) remaining thing which is T ( 2, \{3,4\} ) …are new problems now. First we have to solve those and substitute here.

在这里，以上3条路径中的最小值是答案，但是我们只知道(1,2)，(1,3)，(1,4)剩下的值为T(2，\{3,4\})的值…现在是新问题。 首先，我们必须解决这些问题并在这里替代。

T (2, \{3,4\} )   = minimum of

T(2，\{3,4\})=最小值

=  \{ (2,3) + T (3, \{4\} )     2+**5**=7

= \{(2,3)+ T(3，\{4\})2+ **5** = 7

= \{ (2,4) + T \{4, \{3\} )     1+**5**=6

= \{(2,4)+ T \{4，\{3\})1+ **5** = 6

T (3, \{2,4\} )   = minimum of

T(3，\{2,4\})=最小值

=  \{ (3,2) + T (2, \{4\} )     2+**1**=3

= \{(3,2)+ T(2，\{4\})2 + **1** = 3

= \{ (3,4) + T \{4, \{2\} )     5+**1**=6

= \{(3,4)+ T \{4，\{2\})5 + **1** = 6

T (4, \{2,3\} )   = minimum of

T(4，\{2,3\})=最小值

=  \{ (4,2) + T (2, \{3\} )     1+**2**=3

= \{(4,2)+ T(2，\{3\})1+ **2** = 3

= \{ (4,3) + T \{3, \{2\} )     5+**2**=7

= \{(4,3)+ T \{3，\{2\})5+ **2** = 7

T ( 3, \{4\} ) =  (3,4) + T (4, \{\} )     5+0=5

T(3，\{4\})=(3,4)+ T(4，\{\})5 + 0 = 5

T ( 4, \{3\} ) =  (4,3) + T (3, \{\} )     5+0=5

T(4，\{3\})=(4,3)+ T(3，\{\})5 + 0 = 5

T ( 2, \{4\} ) =  (2,4) + T (4, \{\} )     1+0=1

T(2，\{4\})=(2,4)+ T(4，\{\})1 + 0 = 1

T ( 4, \{2\} ) =  (4,2) + T (2, \{\} )     1+0 = 1

T(4，\{2\})=(4,2)+ T(2，\{\})1 + 0 = 1

T ( 2, \{3\} ) =  (2,3) + T (3, \{\} )     2+0 = 2

T(2，\{3\})=(2,3)+ T(3，\{\})2 + 0 = 2

T ( 3, \{2\} ) =  (3,2) + T (2, \{\} )     2+0=2

T(3，\{2\})=(3,2)+ T(2，\{\})2 + 0 = 2

Here T ( 4, \{\} ) is reaching base condition in recursion, which returns 0 (zero ) distance.

在此T(4，\{\})递归达到基本条件，该条件返回0(零)距离。

This is where we can find final answer,

在这里我们可以找到最终答案，

T ( 1, \{2,3,4\} ) = minimum of

T(1，\{2,3,4\})=最小值

= \{ (1,2) + T (2,  \{3,4\} )     4+**6**=10 in this path we have to add +1 because this path ends with 3. From there we have to reach 1 so 3->1 distance 1 will be added total distance is 10+1=11

= \{(1,2)+ T(2，\{3,4\})4+ **6** = 10在此路径中，我们必须添加+1，因为此路径以3结尾。从那里我们必须达到1，所以3-> 1距离1将被添加总距离为10 + 1 = 11

= \{ (1,3)  + T (3, \{2,4\} )     1+**3**=4 in this path we have to add +3 because this path ends with 3. From there we have to reach 1 so 4->1 distance 3 will be added total distance is 4+3=7

= \{(1,3)+ T(3，\{2,4\})1+ **3** = 4在此路径中我们必须加上+3，因为此路径以3结尾。从那里我们必须达到1，所以4->将添加1个距离3，总距离为4 + 3 = 7

= \{ (1,4) + T (4, \{2,3\} )     3+**3**=6 in this path we have to add +1 because this path ends with 3. From there we have to reach 1 so 3->1 distance 1 will be added total distance is 6+1=7

= \{(1,4)+ T(4，\{2,3\})3+ **3** = 6在此路径中，我们必须添加+1，因为此路径以3结尾。从那里我们必须达到1，所以3-> 1距离1将被添加总距离为6 + 1 = 7

Minimum distance is **7** which includes path **1->3->2->4->1.**

最小距离为**7** ，其中包括路径**1-> 3-> 2-> 4-> 1。**

After solving example problem we can easily write recursive equation.

解决示例问题后，我们可以轻松地编写递归方程。

### 递归方程 **(**Recursive Equation**)** ###

T (i , s) = min ( ( i , j) + T ( j , S – \{ j \}) ) ;  S!= Ø   ; j € S ;

T(i，s)= min((i，j)+ T(j，S – \{j\})))； S！=Ø; j€S;

S is set that contains non visited vertices

设置的S包含未访问的顶点

=  ( i, 1 ) ;  S=Ø, This is base condition for this recursive equation.

=(i，1); S =Ø，这是该递归方程的基本条件。

Here,

这里，

T (i, S) means We are travelling from a vertex “i” and have to visit set of non-visited vertices  “S” and have to go back to vertex 1 (let we started from vertex 1).

T(i，S)表示我们从顶点“ i”行进，不得不访问一组未访问的顶点“ S”，并且必须返回顶点1(让我们从顶点1开始)。

( i, j ) means cost of path from node i  to node j

(i，j)表示从节点i到节点j的路径成本

If we observe the first recursive equation from a node we are finding cost to all other nodes (i,j) and from that node to remaining using recursion ( T (j , \{S-j\}))

如果我们观察到某个节点的第一个递归方程，则发现所有其他节点(i，j)以及使用递归(T(j，\{Sj\}))从该节点到其余节点的成本

But it is not guarantee that every vertex is connected to other vertex then we take that cost as infinity. After that we are taking minimum among all so the path which is not connected get infinity in calculation and won’t be consider.

但这不能保证每个顶点都与其他顶点相连，那么我们将成本视为无穷大。 之后，我们在所有路径中采用最小值，因此未连接的路径在计算中将变为无穷大，因此不会考虑。

If S is empty that means we visited all nodes, we take distance from that last visited node to node 1 (first node). Because after visiting all he has to go back to initial node.

如果S为空，则意味着我们访问了所有节点，我们从最后访问的节点到节点1(第一个节点)的距离为。 因为访问完所有东西后，他必须回到初始节点。

### 时间复杂度 **(**Time Complexity**)** ###

Since we are solving this using Dynamic Programming, we know that Dynamic Programming approach contains sub-problems.

由于我们使用动态编程解决了这一问题，因此我们知道动态编程方法包含一些子问题。

Here after reaching ith node finding remaining minimum distance to that ith node is a sub-problem.

在到达第 i 个节点之后，找到到该第 i 个节点的剩余最小距离是一个子问题。

If we solve recursive equation we will get total **(n-1) 2(n-2)  **sub-problems, which is **O (n2n)**.

如果我们求解递归方程，我们将得到总计**(n-1)2 (n-2)**个子问题，即**O(n2 n )** 。

Each sub-problem will take ** O (n)** time (finding path to remaining **(n-1)** nodes).

每个子问题将花费**O(n)**时间(寻找到剩余**(n-1)个**节点的路径)。

Therefore total time complexity is **O (n2n) \* O (n) = O (n22n)**

因此，总时间复杂度为**O(n2 n )\* O(n)= O(n 2 2 n )**

Space complexity is also number of sub-problems which is **O (n2n)**

空间复杂度也是子问题的数量，它是**O(n2 n )**

### C语言中的旅行推销员问题程序 **(**Program for Travelling Salesman Problem in C**)** ###

\#include<stdio.h> int ary\[10\]\[10\],completed\[10\],n,cost=0; void takeInput() \{ int i,j; printf("Enter the number of villages: "); scanf("%d",&n); printf("\\nEnter the Cost Matrix\\n"); for(i=0;i < n;i++) \{ printf("\\nEnter Elements of Row: %d\\n",i+1); for( j=0;j < n;j++) scanf("%d",&ary\[i\]\[j\]); completed\[i\]=0; \} printf("\\n\\nThe cost list is:"); for( i=0;i < n;i++) \{ printf("\\n"); for(j=0;j < n;j++) printf("\\t%d",ary\[i\]\[j\]); \} \} void mincost(int city) \{ int i,ncity; completed\[city\]=1; printf("%d--->",city+1); ncity=least(city); if(ncity==999) \{ ncity=0; printf("%d",ncity+1); cost+=ary\[city\]\[ncity\]; return; \} mincost(ncity); \} int least(int c) \{ int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) \{ if((ary\[c\]\[i\]!=0)&&(completed\[i\]==0)) if(ary\[c\]\[i\]+ary\[i\]\[c\] < min) \{ min=ary\[i\]\[0\]+ary\[c\]\[i\]; kmin=ary\[c\]\[i\]; nc=i; \} \} if(min!=999) cost+=kmin; return nc; \} int main() \{ takeInput(); printf("\\n\\nThe Path is:\\n"); mincost(0); //passing 0 because starting vertex printf("\\n\\nMinimum cost is %d\\n ",cost); return 0; \} \#include<stdio.h> int ary\[10\]\[10\],completed\[10\],n,cost=0; void takeInput() \{ int i,j; printf("Enter the number of villages: "); scanf("%d",&n); printf("\\nEnter the Cost Matrix\\n"); for(i=0;i < n;i++) \{ printf("\\nEnter Elements of Row: %d\\n",i+1); for( j=0;j < n;j++) scanf("%d",&ary\[i\]\[j\]); completed\[i\]=0; \} printf("\\n\\nThe cost list is:"); for( i=0;i < n;i++) \{ printf("\\n"); for(j=0;j < n;j++) printf("\\t%d",ary\[i\]\[j\]); \} \} void mincost(int city) \{ int i,ncity; completed\[city\]=1; printf("%d--->",city+1); ncity=least(city); if(ncity==999) \{ ncity=0; printf("%d",ncity+1); cost+=ary\[city\]\[ncity\]; return; \} mincost(ncity); \} int least(int c) \{ int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) \{ if((ary\[c\]\[i\]!=0)&&(completed\[i\]==0)) if(ary\[c\]\[i\]+ary\[i\]\[c\] < min) \{ min=ary\[i\]\[0\]+ary\[c\]\[i\]; kmin=ary\[c\]\[i\]; nc=i; \} \} if(min!=999) cost+=kmin; return nc; \} int main() \{ takeInput(); printf("\\n\\nThe Path is:\\n"); mincost(0); //passing 0 because starting vertex printf("\\n\\nMinimum cost is %d\\n ",cost); return 0; \}

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div>
       1 
     </div> 
     <div>
       2 
     </div> 
     <div>
       3 
     </div> 
     <div>
       4 
     </div> 
     <div>
       5 
     </div> 
     <div>
       6 
     </div> 
     <div>
       7 
     </div> 
     <div>
       8 
     </div> 
     <div>
       9 
     </div> 
     <div>
       10 
     </div> 
     <div>
       11 
     </div> 
     <div>
       12 
     </div> 
     <div>
       13 
     </div> 
     <div>
       14 
     </div> 
     <div>
       15 
     </div> 
     <div>
       16 
     </div> 
     <div>
       17 
     </div> 
     <div>
       18 
     </div> 
     <div>
       19 
     </div> 
     <div>
       20 
     </div> 
     <div>
       21 
     </div> 
     <div>
       22 
     </div> 
     <div>
       23 
     </div> 
     <div>
       24 
     </div> 
     <div>
       25 
     </div> 
     <div>
       26 
     </div> 
     <div>
       27 
     </div> 
     <div>
       28 
     </div> 
     <div>
       29 
     </div> 
     <div>
       30 
     </div> 
     <div>
       31 
     </div> 
     <div>
       32 
     </div> 
     <div>
       33 
     </div> 
     <div>
       34 
     </div> 
     <div>
       35 
     </div> 
     <div>
       36 
     </div> 
     <div>
       37 
     </div> 
     <div>
       38 
     </div> 
     <div>
       39 
     </div> 
     <div>
       40 
     </div> 
     <div>
       41 
     </div> 
     <div>
       42 
     </div> 
     <div>
       43 
     </div> 
     <div>
       44 
     </div> 
     <div>
       45 
     </div> 
     <div>
       46 
     </div> 
     <div>
       47 
     </div> 
     <div>
       48 
     </div> 
     <div>
       49 
     </div> 
     <div>
       50 
     </div> 
     <div>
       51 
     </div> 
     <div>
       52 
     </div> 
     <div>
       53 
     </div> 
     <div>
       54 
     </div> 
     <div>
       55 
     </div> 
     <div>
       56 
     </div> 
     <div>
       57 
     </div> 
     <div>
       58 
     </div> 
     <div>
       59 
     </div> 
     <div>
       60 
     </div> 
     <div>
       61 
     </div> 
     <div>
       62 
     </div> 
     <div>
       63 
     </div> 
     <div>
       64 
     </div> 
     <div>
       65 
     </div> 
     <div>
       66 
     </div> 
     <div>
       67 
     </div> 
     <div>
       68 
     </div> 
     <div>
       69 
     </div> 
     <div>
       70 
     </div> 
     <div>
       71 
     </div> 
     <div>
       72 
     </div> 
     <div>
       73 
     </div> 
     <div>
       74 
     </div> 
     <div>
       75 
     </div> 
     <div>
       76 
     </div> 
     <div>
       77 
     </div> 
     <div>
       78 
     </div> 
     <div>
       79 
     </div> 
     <div>
       80 
     </div> 
     <div>
       81 
     </div> 
     <div>
       82 
     </div> 
     <div>
       83 
     </div> 
     <div>
       84 
     </div> 
     <div>
       85 
     </div> 
     <div>
       86 
     </div> 
     <div>
       87 
     </div> 
     <div>
       88 
     </div> 
    </div> </td> 
   <td> 
    <div> 
     <div>
       #include&lt;stdio.h&gt; 
     </div> 
     <div>
       int ary[10][10],completed[10],n,cost=0; 
     </div> 
     <div>
       void takeInput() 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,j; 
     </div> 
     <div>
       printf("Enter the number of villages: "); 
     </div> 
     <div>
       scanf("%d",&amp;n); 
     </div> 
     <div>
       printf("\nEnter the Cost Matrix\n"); 
     </div> 
     <div>
       for(i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       printf("\nEnter Elements of Row: %d\n",i+1); 
     </div> 
     <div>
       for( j=0;j &lt; n;j++) 
     </div> 
     <div>
       scanf("%d",&amp;ary[i][j]); 
     </div> 
     <div>
       completed[i]=0; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       printf("\n\nThe cost list is:"); 
     </div> 
     <div>
       for( i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       printf("\n"); 
     </div> 
     <div>
       for(j=0;j &lt; n;j++) 
     </div> 
     <div>
       printf("\t%d",ary[i][j]); 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       void mincost(int city) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,ncity; 
     </div> 
     <div>
       completed[city]=1; 
     </div> 
     <div>
       printf("%d---&gt;",city+1); 
     </div> 
     <div>
       ncity=least(city); 
     </div> 
     <div>
       if(ncity==999) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       ncity=0; 
     </div> 
     <div>
       printf("%d",ncity+1); 
     </div> 
     <div>
       cost+=ary[city][ncity]; 
     </div> 
     <div>
       return; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       mincost(ncity); 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int least(int c) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,nc=999; 
     </div> 
     <div>
       int min=999,kmin; 
     </div> 
     <div>
       for(i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       if((ary[c][i]!=0)&amp;&amp;(completed[i]==0)) 
     </div> 
     <div>
       if(ary[c][i]+ary[i][c] &lt; min) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       min=ary[i][0]+ary[c][i]; 
     </div> 
     <div>
       kmin=ary[c][i]; 
     </div> 
     <div>
       nc=i; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       if(min!=999) 
     </div> 
     <div>
       cost+=kmin; 
     </div> 
     <div>
       return nc; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int main() 
     </div> 
     <div>
       { 
     </div> 
     <div>
       takeInput(); 
     </div> 
     <div>
       printf("\n\nThe Path is:\n"); 
     </div> 
     <div>
       mincost(0); //passing 0 because starting vertex 
     </div> 
     <div>
       printf("\n\nMinimum cost is %d\n ",cost); 
     </div> 
     <div>
       return 0; 
     </div> 
     <div>
       } 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div>
       1 
     </div> 
     <div>
       2 
     </div> 
     <div>
       3 
     </div> 
     <div>
       4 
     </div> 
     <div>
       5 
     </div> 
     <div>
       6 
     </div> 
     <div>
       7 
     </div> 
     <div>
       8 
     </div> 
     <div>
       9 
     </div> 
     <div>
       10 
     </div> 
     <div>
       11 
     </div> 
     <div>
       12 
     </div> 
     <div>
       13 
     </div> 
     <div>
       14 
     </div> 
     <div>
       15 
     </div> 
     <div>
       16 
     </div> 
     <div>
       17 
     </div> 
     <div>
       18 
     </div> 
     <div>
       19 
     </div> 
     <div>
       20 
     </div> 
     <div>
       21 
     </div> 
     <div>
       22 
     </div> 
     <div>
       23 
     </div> 
     <div>
       24 
     </div> 
     <div>
       25 
     </div> 
     <div>
       26 
     </div> 
     <div>
       27 
     </div> 
     <div>
       28 
     </div> 
     <div>
       29 
     </div> 
     <div>
       30 
     </div> 
     <div>
       31 
     </div> 
     <div>
       32 
     </div> 
     <div>
       33 
     </div> 
     <div>
       34 
     </div> 
     <div>
       35 
     </div> 
     <div>
       36 
     </div> 
     <div>
       37 
     </div> 
     <div>
       38 
     </div> 
     <div>
       39 
     </div> 
     <div>
       40 
     </div> 
     <div>
       41 
     </div> 
     <div>
       42 
     </div> 
     <div>
       43 
     </div> 
     <div>
       44 
     </div> 
     <div>
       45 
     </div> 
     <div>
       46 
     </div> 
     <div>
       47 
     </div> 
     <div>
       48 
     </div> 
     <div>
       49 
     </div> 
     <div>
       50 
     </div> 
     <div>
       51 
     </div> 
     <div>
       52 
     </div> 
     <div>
       53 
     </div> 
     <div>
       54 
     </div> 
     <div>
       55 
     </div> 
     <div>
       56 
     </div> 
     <div>
       57 
     </div> 
     <div>
       58 
     </div> 
     <div>
       59 
     </div> 
     <div>
       60 
     </div> 
     <div>
       61 
     </div> 
     <div>
       62 
     </div> 
     <div>
       63 
     </div> 
     <div>
       64 
     </div> 
     <div>
       65 
     </div> 
     <div>
       66 
     </div> 
     <div>
       67 
     </div> 
     <div>
       68 
     </div> 
     <div>
       69 
     </div> 
     <div>
       70 
     </div> 
     <div>
       71 
     </div> 
     <div>
       72 
     </div> 
     <div>
       73 
     </div> 
     <div>
       74 
     </div> 
     <div>
       75 
     </div> 
     <div>
       76 
     </div> 
     <div>
       77 
     </div> 
     <div>
       78 
     </div> 
     <div>
       79 
     </div> 
     <div>
       80 
     </div> 
     <div>
       81 
     </div> 
     <div>
       82 
     </div> 
     <div>
       83 
     </div> 
     <div>
       84 
     </div> 
     <div>
       85 
     </div> 
     <div>
       86 
     </div> 
     <div>
       87 
     </div> 
     <div>
       88 
     </div> 
    </div> </td> 
   <td> 
    <div> 
     <div>
       #include&lt;stdio.h&gt; 
     </div> 
     <div>
       int ary [ 10 ] [ 10 ] , completed [ 10 ] , n , cost = 0 ; 
     </div> 
     <div>
       void takeInput ( ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i , j ; 
     </div> 
     <div>
       printf ( "Enter the number of villages: " ) ; 
     </div> 
     <div>
       scanf ( "%d" , &amp; n ) ; 
     </div> 
     <div>
       printf ( "\nEnter the Cost Matrix\n" ) ; 
     </div> 
     <div>
       for ( i = 0 ; i &lt; n ; i ++ ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       printf ( "\nEnter Elements of Row: %d\n" , i + 1 ) ; 
     </div> 
     <div>
       for ( j = 0 ; j &lt; n ; j ++ ) 
     </div> 
     <div>
       scanf ( "%d" , &amp; ary [ i ] [ j ] ) ; 
     </div> 
     <div>
       completed [ i ] = 0 ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       printf ( "\n\nThe cost list is:" ) ; 
     </div> 
     <div>
       for ( i = 0 ; i &lt; n ; i ++ ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       printf ( "\n" ) ; 
     </div> 
     <div>
       for ( j = 0 ; j &lt; n ; j ++ ) 
     </div> 
     <div>
       printf ( "\t%d" , ary [ i ] [ j ] ) ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       void mincost ( int city ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i , ncity ; 
     </div> 
     <div>
       completed [ city ] = 1 ; 
     </div> 
     <div>
       printf ( "%d---&gt;" , city + 1 ) ; 
     </div> 
     <div>
       ncity = least ( city ) ; 
     </div> 
     <div>
       if ( ncity == 999 ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       ncity = 0 ; 
     </div> 
     <div>
       printf ( "%d" , ncity + 1 ) ; 
     </div> 
     <div>
       cost += ary [ city ] [ ncity ] ; 
     </div> 
     <div>
       return ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       mincost ( ncity ) ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int least ( int c ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i , nc = 999 ; 
     </div> 
     <div>
       int min = 999 , kmin ; 
     </div> 
     <div>
       for ( i = 0 ; i &lt; n ; i ++ ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       if ( ( ary [ c ] [ i ] != 0 ) &amp;&amp; ( completed [ i ] == 0 ) ) 
     </div> 
     <div>
       if ( ary [ c ] [ i ] + ary [ i ] [ c ] &lt; min ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       min = ary [ i ] [ 0 ] + ary [ c ] [ i ] ; 
     </div> 
     <div>
       kmin = ary [ c ] [ i ] ; 
     </div> 
     <div>
       nc = i ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       if ( min != 999 ) 
     </div> 
     <div>
       cost += kmin ; 
     </div> 
     <div>
       return nc ; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int main ( ) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       takeInput ( ) ; 
     </div> 
     <div>
       printf ( "\n\nThe Path is:\n" ) ; 
     </div> 
     <div>
       mincost ( 0 ) ; //passing 0 because starting vertex 
     </div> 
     <div>
       printf ( "\n\nMinimum cost is %d\n " , cost ) ; 
     </div> 
     <div>
       return 0 ; 
     </div> 
     <div>
       } 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

**Output**

**输出量**

*Enter the number of villages: 4*

*输入村庄数：4*

*Enter the Cost Matrix*

*输入成本矩阵*

*Enter Elements of Row: 1* *0 4 1 3*

*输入行元素：1* *0 4 1 3*

*Enter Elements of Row: 2* *4 0 2 1*

*输入行元素：2* *4 0 2 1*

*Enter Elements of Row: 3* *1 2 0 5*

*输入行元素：3* *1 2 0 5*

*Enter Elements of Row: 4* *3 1 5 0* *The cost list is:*  *0 4 1 3*  *4 0 2 1*  *1 2 0 5*  *3 1 5 0*

*输入行元素：4* *3 1 5 0* *成本列表为：* *0 4 1 3* *4 0 2 1* *1 2 0 5* *3 1 5 0*

*The Path is:* *1—>3—>2—>4—>1*

*路径为：* *1—> 3—> 2—> 4—> 1*

*Minimum cost is 7*

*最低费用为7*

### C ++中的旅行推销员问题程序 **(**Program for Travelling Salesman Problem in C++**)** ###

\#include<iostream> using namespace std; int ary\[10\]\[10\],completed\[10\],n,cost=0; void takeInput() \{ int i,j; cout<<"Enter the number of villages: "; cin>>n; cout<<"\\nEnter the Cost Matrix\\n"; for(i=0;i < n;i++) \{ cout<<"\\nEnter Elements of Row: "<<i+1<<"\\n"; for( j=0;j < n;j++) cin>>ary\[i\]\[j\]; completed\[i\]=0; \} cout<<"\\n\\nThe cost list is:"; for( i=0;i < n;i++) \{ cout<<"\\n"; for(j=0;j < n;j++) cout<<"\\t"<<ary\[i\]\[j\]; \} \} int least(int c) \{ int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) \{ if((ary\[c\]\[i\]!=0)&&(completed\[i\]==0)) if(ary\[c\]\[i\]+ary\[i\]\[c\] < min) \{ min=ary\[i\]\[0\]+ary\[c\]\[i\]; kmin=ary\[c\]\[i\]; nc=i; \} \} if(min!=999) cost+=kmin; return nc; \} void mincost(int city) \{ int i,ncity; completed\[city\]=1; cout<<city+1<<"--->"; ncity=least(city); if(ncity==999) \{ ncity=0; cout<<ncity+1; cost+=ary\[city\]\[ncity\]; return; \} mincost(ncity); \} int main() \{ takeInput(); cout<<"\\n\\nThe Path is:\\n"; mincost(0); //passing 0 because starting vertex cout<<"\\n\\nMinimum cost is "<<cost; return 0; \}

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div>
       1 
     </div> 
     <div>
       2 
     </div> 
     <div>
       3 
     </div> 
     <div>
       4 
     </div> 
     <div>
       5 
     </div> 
     <div>
       6 
     </div> 
     <div>
       7 
     </div> 
     <div>
       8 
     </div> 
     <div>
       9 
     </div> 
     <div>
       10 
     </div> 
     <div>
       11 
     </div> 
     <div>
       12 
     </div> 
     <div>
       13 
     </div> 
     <div>
       14 
     </div> 
     <div>
       15 
     </div> 
     <div>
       16 
     </div> 
     <div>
       17 
     </div> 
     <div>
       18 
     </div> 
     <div>
       19 
     </div> 
     <div>
       20 
     </div> 
     <div>
       21 
     </div> 
     <div>
       22 
     </div> 
     <div>
       23 
     </div> 
     <div>
       24 
     </div> 
     <div>
       25 
     </div> 
     <div>
       26 
     </div> 
     <div>
       27 
     </div> 
     <div>
       28 
     </div> 
     <div>
       29 
     </div> 
     <div>
       30 
     </div> 
     <div>
       31 
     </div> 
     <div>
       32 
     </div> 
     <div>
       33 
     </div> 
     <div>
       34 
     </div> 
     <div>
       35 
     </div> 
     <div>
       36 
     </div> 
     <div>
       37 
     </div> 
     <div>
       38 
     </div> 
     <div>
       39 
     </div> 
     <div>
       40 
     </div> 
     <div>
       41 
     </div> 
     <div>
       42 
     </div> 
     <div>
       43 
     </div> 
     <div>
       44 
     </div> 
     <div>
       45 
     </div> 
     <div>
       46 
     </div> 
     <div>
       47 
     </div> 
     <div>
       48 
     </div> 
     <div>
       49 
     </div> 
     <div>
       50 
     </div> 
     <div>
       51 
     </div> 
     <div>
       52 
     </div> 
     <div>
       53 
     </div> 
     <div>
       54 
     </div> 
     <div>
       55 
     </div> 
     <div>
       56 
     </div> 
     <div>
       57 
     </div> 
     <div>
       58 
     </div> 
     <div>
       59 
     </div> 
     <div>
       60 
     </div> 
     <div>
       61 
     </div> 
     <div>
       62 
     </div> 
     <div>
       63 
     </div> 
     <div>
       64 
     </div> 
     <div>
       65 
     </div> 
     <div>
       66 
     </div> 
     <div>
       67 
     </div> 
     <div>
       68 
     </div> 
     <div>
       69 
     </div> 
     <div>
       70 
     </div> 
     <div>
       71 
     </div> 
     <div>
       72 
     </div> 
     <div>
       73 
     </div> 
     <div>
       74 
     </div> 
     <div>
       75 
     </div> 
     <div>
       76 
     </div> 
     <div>
       77 
     </div> 
     <div>
       78 
     </div> 
     <div>
       79 
     </div> 
     <div>
       80 
     </div> 
     <div>
       81 
     </div> 
     <div>
       82 
     </div> 
     <div>
       83 
     </div> 
     <div>
       84 
     </div> 
     <div>
       85 
     </div> 
     <div>
       86 
     </div> 
     <div>
       87 
     </div> 
     <div>
       88 
     </div> 
     <div>
       89 
     </div> 
     <div>
       90 
     </div> 
    </div> </td> 
   <td> 
    <div> 
     <div>
       #include&lt;iostream&gt; 
     </div> 
     <div>
       using namespace std; 
     </div> 
     <div>
       int ary[10][10],completed[10],n,cost=0; 
     </div> 
     <div>
       void takeInput() 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,j; 
     </div> 
     <div>
       cout&lt;&lt;"Enter the number of villages: "; 
     </div> 
     <div>
       cin&gt;&gt;n; 
     </div> 
     <div>
       cout&lt;&lt;"\nEnter the Cost Matrix\n"; 
     </div> 
     <div>
       for(i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       cout&lt;&lt;"\nEnter Elements of Row: "&lt;&lt;i+1&lt;&lt;"\n"; 
     </div> 
     <div>
       for( j=0;j &lt; n;j++) 
     </div> 
     <div>
       cin&gt;&gt;ary[i][j]; 
     </div> 
     <div>
       completed[i]=0; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       cout&lt;&lt;"\n\nThe cost list is:"; 
     </div> 
     <div>
       for( i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       cout&lt;&lt;"\n"; 
     </div> 
     <div>
       for(j=0;j &lt; n;j++) 
     </div> 
     <div>
       cout&lt;&lt;"\t"&lt;&lt;ary[i][j]; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int least(int c) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,nc=999; 
     </div> 
     <div>
       int min=999,kmin; 
     </div> 
     <div>
       for(i=0;i &lt; n;i++) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       if((ary[c][i]!=0)&amp;&amp;(completed[i]==0)) 
     </div> 
     <div>
       if(ary[c][i]+ary[i][c] &lt; min) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       min=ary[i][0]+ary[c][i]; 
     </div> 
     <div>
       kmin=ary[c][i]; 
     </div> 
     <div>
       nc=i; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       if(min!=999) 
     </div> 
     <div>
       cost+=kmin; 
     </div> 
     <div>
       return nc; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       void mincost(int city) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       int i,ncity; 
     </div> 
     <div>
       completed[city]=1; 
     </div> 
     <div>
       cout&lt;&lt;city+1&lt;&lt;"---&gt;"; 
     </div> 
     <div>
       ncity=least(city); 
     </div> 
     <div>
       if(ncity==999) 
     </div> 
     <div>
       { 
     </div> 
     <div>
       ncity=0; 
     </div> 
     <div>
       cout&lt;&lt;ncity+1; 
     </div> 
     <div>
       cost+=ary[city][ncity]; 
     </div> 
     <div>
       return; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       mincost(ncity); 
     </div> 
     <div>
       } 
     </div> 
     <div>
       int main() 
     </div> 
     <div>
       { 
     </div> 
     <div>
       takeInput(); 
     </div> 
     <div>
       cout&lt;&lt;"\n\nThe Path is:\n"; 
     </div> 
     <div>
       mincost(0); //passing 0 because starting vertex 
     </div> 
     <div>
       cout&lt;&lt;"\n\nMinimum cost is "&lt;&lt;cost; 
     </div> 
     <div>
       return 0; 
     </div> 
     <div>
       } 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

Comment below if you found any information incorrect or have doubts regarding Travelling Salesman Problem algorithm.

如果您发现任何信息不正确或对旅行商问题算法有疑问，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/05/travelling-salesman-problem.html][https_www.thecrazyprogrammer.com_2017_05_travelling-salesman-problem.html]

c语言旅行商问题

[Travelling Salesman Problem _TSP]: /images/20221123/d5745b70ef7f4fb79492a2aef45b4d05.png
[https_www.thecrazyprogrammer.com_2017_05_travelling-salesman-problem.html]: https://www.thecrazyprogrammer.com/2017/05/travelling-salesman-problem.html