旅行商问题

旅行商问题是一个图计算问题，其中推销员需要访问列表中的所有城市（使用图中的节点表示）一次，并且所有这些城市之间的距离（使用图中的边表示）是已知的。该问题需要找到的解决方案是推销员访问所有城市并返回出发城市的最短路径。

如果您看下图，考虑到推销员从顶点“a”开始，他们需要遍历所有剩余的顶点 b、c、d、e、f 并返回到“a”，同时确保所花费的成本是最小的。

有多种方法可以找到旅行商问题的解决方案：朴素方法、贪心方法、动态规划方法等。在本教程中，我们将学习如何使用贪心方法解决旅行商问题。

旅行推销员算法

正如贪婪方法的定义所述，我们需要在局部找到最佳最优解来找出全局最优解。该算法采用的输入是图 G {V, E}，其中 V 是顶点集，E 是边集。得到图G从一个顶点出发到同一顶点的最短路径作为输出。

算法

旅行推销员问题采用图 G {V, E} 作为输入，并声明另一个图作为输出（例如 G'），该输出将记录推销员从一个节点到另一个节点的路径。
该算法首先对输入图 G 中的所有边进行从最小距离到最大距离的排序。
选择的第一条边是距离最小的边，两个顶点（例如 A 和 B）之一是原点（例如 A）。
然后在除原点（B）之外的节点的相邻边中，找到成本最小的边并将其添加到输出图上。
使用更多节点继续该过程，确保输出图中没有循环并且路径返回到原始节点 A。
但是，如果给定问题中提到了原点，则解决方案必须始终仅从该节点开始。让我们看一些示例问题以更好地理解这一点。

例子

考虑下图，其中有六个城市以及它们之间的距离 -

从给定的图中，由于已经提到了原点，因此解决方案必须始终从该节点开始。在从 A 引出的边中，A → B 的距离最短。

然后，B → C 之间具有最短且唯一的边，因此它包含在输出图中。

C → D 之间只有一条边，因此它被添加到输出图中。

从 D 有两条向外的边。尽管 D → B 的距离比 D → E 的距离短，但 B 已经被访问过一次，如果添加到输出图中，它将形成一个循环。因此，D→E被添加到输出图中。

e 只有一条边，即 E → F。因此，它被添加到输出图中。

同样，即使 F → C 的距离比 F → A 的距离短，F → A 也会被添加到输出图中，以避免形成循环并且 C 已经被访问过一次。

起点和终点为 A 的最短路径为 A → B → C → D → E → F → A

该路径的成本为：16 + 21 + 12 + 15 + 16 + 34 = 114。

尽管如此，如果路径源自其他节点，则路径的成本可能会降低，但并没有提出与此相关的问题。

例子

使用贪心法的旅行商问题的完整实现如下 -

C C++ Java Python

#include <stdio.h>
int tsp_g[10][10] = {
   {12, 30, 33, 10, 45},
   {56, 22, 9, 15, 18},
   {29, 13, 8, 5, 12},
   {33, 28, 16, 10, 3},
   {1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */
void travellingsalesman(int c){
   int k, adj_vertex = 999;
   int min = 999;
   
   /* marking the vertices visited in an assigned array */
   visited[c] = 1;
   
   /* displaying the shortest path */
   printf("%d ", c + 1);
   
   /* checking the minimum cost edge in the graph */
   for(k = 0; k < n; k++) {
      if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
         if(tsp_g[c][k] < min) {
            min = tsp_g[c][k];
         }
         adj_vertex = k;
      }
   }
   if(min != 999) {
      cost = cost + min;
   }
   if(adj_vertex == 999) {
      adj_vertex = 0;
      printf("%d", adj_vertex + 1);
      cost = cost + tsp_g[c][adj_vertex];
      return;
   }
   travellingsalesman(adj_vertex);
}

/* main function */
int main(){
   int i, j;
   n = 5;
   for(i = 0; i < n; i++) {
      visited[i] = 0;
   }
   printf("\nShortest Path: ");
   travellingsalesman(0);
   printf("\nMinimum Cost: ");
   printf("%d\n", cost);
   return 0;
}

输出

Shortest Path: 1 5 4 3 2 1
Minimum Cost: 99

#include <iostream>
using namespace std;
int tsp_g[10][10] = {{12, 30, 33, 10, 45},
{56, 22, 9, 15, 18},
{29, 13, 8, 5, 12},
{33, 28, 16, 10, 3},
{1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */
void travellingsalesman(int c){
   int k, adj_vertex = 999;
   int min = 999;
   
   /* marking the vertices visited in an assigned array */
   visited[c] = 1;
   
   /* displaying the shortest path */
   cout<<c + 1<<" ";
   
   /* checking the minimum cost edge in the graph */
   for(k = 0; k < n; k++) {
      if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
         if(tsp_g[c][k] < min) {
            min = tsp_g[c][k];
         }
      adj_vertex = k;
      }
   }
   if(min != 999) {
      cost = cost + min;
   }
   if(adj_vertex == 999) {
      adj_vertex = 0;
      cout<<adj_vertex + 1;
      cost = cost + tsp_g[c][adj_vertex];
      return;
   }
   travellingsalesman(adj_vertex);
}

/* main function */
int main(){
   int i, j;
   n = 5;
   for(i = 0; i < n; i++) {
      visited[i] = 0;
   }
   cout<<endl;
   cout<<"Shortest Path: ";
   travellingsalesman(0);
   cout<<endl;
   cout<<"Minimum Cost: ";
   cout<<cost;
   return 0;
}

输出

Shortest Path: 1 5 4 3 2 1
Minimum Cost: 99

import java.util.*;
public class Main {
    static int[][] tsp_g = {{12, 30, 33, 10, 45},
                            {56, 22, 9, 15, 18},
                            {29, 13, 8, 5, 12},
                            {33, 28, 16, 10, 3},
                            {1, 4, 30, 24, 20}};
    static int[] visited;
    static int n, cost;
    public static void travellingsalesman(int c) {
        int k, adj_vertex = 999;
        int min = 999;
        visited[c] = 1;
        System.out.print((c + 1) + " ");
        for (k = 0; k < n; k++) {
            if ((tsp_g[c][k] != 0) && (visited[k] == 0)) {
                if (tsp_g[c][k] < min) {
                    min = tsp_g[c][k];
                }
                adj_vertex = k;
            }
        }
        if (min != 999) {
            cost = cost + min;
        }
        if (adj_vertex == 999) {
            adj_vertex = 0;
            System.out.print((adj_vertex + 1));
            cost = cost + tsp_g[c][adj_vertex];
            return;
        }
        travellingsalesman(adj_vertex);
    }
    public static void main(String[] args) {
        int i, j;
        n = 5;
        visited = new int[n];
        Arrays.fill(visited, 0);
        System.out.println();
        System.out.print("Shortest Path: ");
        travellingsalesman(0);
        System.out.println();
        System.out.print("Minimum Cost: ");
        System.out.print(cost);
    }
}

输出

Shortest Path: 1 5 4 3 2 1
Minimum Cost: 99

import numpy as np
def travellingsalesman(c):
    global cost
    adj_vertex = 999
    min_val = 999
    visited[c] = 1
    print((c + 1), end=" ")
    for k in range(n):
        if (tsp_g[c][k] != 0) and (visited[k] == 0):
            if tsp_g[c][k] < min_val:
                min_val = tsp_g[c][k]
                adj_vertex = k
    if min_val != 999:
        cost = cost + min_val
    if adj_vertex == 999:
        adj_vertex = 0
        print((adj_vertex + 1), end=" ")
        cost = cost + tsp_g[c][adj_vertex]
        return
    travellingsalesman(adj_vertex)
n = 5
cost = 0
visited = np.zeros(n, dtype=int)
tsp_g = np.array([[12, 30, 33, 10, 45],
                  [56, 22, 9, 15, 18],
                  [29, 13, 8, 5, 12],
                  [33, 28, 16, 10, 3],
                  [1, 4, 30, 24, 20]])
print()
print("Shortest Path:", end=" ")
travellingsalesman(0)
print()
print("Minimum Cost:", end=" ")
print(cost)

输出

Shortest Path: 1 4 5 2 3 1 
Minimum Cost: 55