旅行商问题（贪婪方法）
旅行商问题是一个图计算问题，其中销售员需要访问列表中的所有城市（用图中的节点表示）一次，并且所有这些城市之间的距离（用图中的边表示）都是已知的。这个问题需要找到的解决方案是销售员访问所有城市并返回出发城市的最短路径。
如果查看下图，假设销售员从顶点"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 出发只有一条边，即 E → F。因此，它被添加到输出图中。
同样，即使 F → C 的距离小于 F → A，F →将 A 添加到输出图中以避免形成环路，并且 C 已被访问过一次。
起始于 A 并终止于 A 的最短路径为 A → B → C → D → E → F → A
该路径的成本为：16 + 21 + 12 + 15 + 16 + 34 = 114。
尽管如果路径源自其他节点，其成本可能会降低，但问题并不在于此。
示例
使用贪婪方法的旅行商问题的完整实现如下所示 −
#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;
/* 创建一个函数来生成最短路径 */
void travellingsalesman(int c){
int k, adj_vertex = 999;
int min = 999;
/* 在指定数组中标记已访问的顶点 */
visited[c] = 1;
/* 显示最短路径 */
printf("%d ", 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;
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("Shortest Path: ");
travellingsalesman(0);
printf("
Minimum Cost: ");
printf("%d
", cost);
return 0;
}
输出
Shortest Path: 1 4 5 2 3 1 Minimum Cost: 55
#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<<"Shortest Path: ";
travellingsalesman(0);
cout<<"
Minimum Cost: ";
cout<<cost;
return 0;
}
输出
Shortest Path: 1 4 5 2 3 1 Minimum Cost: 55
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.print("Shortest Path: ");
travellingsalesman(0);
System.out.print("
Minimum Cost: ");
System.out.print(cost);
}
}
输出
Shortest Path: 1 4 5 2 3 1 Minimum Cost: 55
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("Shortest Path:", end=" ")
travellingsalesman(0)
print()
print("Minimum Cost:", end=" ")
print(cost)
输出
Shortest Path: 1 4 5 2 3 1 Minimum Cost: 55
