数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用约减矩阵法解决旅行商问题 (TSP)
旅行商问题是人工智能和运筹学中的一个热门话题。自从它首次被提出以来，已经发表了大量的论文，提供了解决这个问题的各种方法。此外，相关的从业人员提出了一系列新的公式，试图拓宽基本TSP的应用。
旅行商问题：定义
旅行商问题 (TSP) 的正式定义如下：
给定一系列城市及其之间的距离，找到一条最短路径，这条路径恰好访问每个城市一次并返回到起始城市。
更多关于这个问题
TSP接收n个城市的集合，其中n是一个大于2的正整数。每个城市都有一个唯一的标识符，连接城市的物理距离以距离矩阵的形式提供，矩阵中的第i个元素表示从城市i到城市j的距离。
TSP生成城市的排列作为输出，指示访问每个城市的正确顺序。通过总结排列中每个连续城市对之间的长度，可以确定路径的长度。目标是找到使路线总距离缩短到最短可能的长度的排列。
为了本文的目的，我们将使用一个包含四个不同城市A、B、C和D的基本示例。该示例的距离矩阵如下：
A |
B |
C |
D |
|
|---|---|---|---|---|
A |
0 |
4 |
8 |
7 |
B |
4 |
0 |
2 |
3 |
C |
8 |
2 |
0 |
6 |
D |
7 |
3 |
6 |
0 |
在本例中，TSP需要找到一条最短路径，恰好访问每个城市一次，然后返回到起始位置。A到D到B到C到A是一条可能的路径，总长度为7 + 3 + 2 + 8 = 20。这意味着我们从城市A前往城市D，然后到城市B，接着是城市C，最后回到城市A。
约减矩阵
这种方法类似于所谓的分支限界法。在这种情况下，路径成本和边界的决策是使用矩阵约减法做出的。这些假设与约减矩阵有关：
当且仅当代价邻接矩阵的行或列至少有一个零元素，而其所有其他元素都大于或等于零时，该矩阵才是约减的。
只有当每一列和每一行都被约减时，矩阵才被约减。
“路径长度（旧） - 约减的总值 = 路径长度（新）”
我们首先将初始代价邻接矩阵中的所有对角线元素从0替换为无穷大。
使用约减矩阵法求解TSP
解决这个问题的主要原理如下：
约减矩阵的起始距离是解决“旅行商问题”的最小可行距离。
接下来，在每个阶段，必须确定如果遵循该路径的最小距离。
可以通过将第j列和第i行的距离替换为无穷大，然后约减矩阵，并将额外距离添加到之前确定的最小路径距离中来实现这一点。
当找到至少一条最小路径距离时，它将被用作应用“分支限界”方法于剩余路径的距离的“上限”，并且每次出现具有更短距离的另一条路径时，都会更新上限。
示例
以下是以上方法在各种编程语言中的实现：
#include<iostream>
using namespace std;
int tsp_g[10][10] = {
{17, 30, 33, 10, 25},
{66, 22, 19, 15, 18},
{89, 13, 8, 25, 15},
{33, 25, 16, 30, 3},
{25, 33, 35, 24, 37}
};
int visited[10], n = 5, cost = 0;
void travellingsalesman(int c){
int adj_vertex = 999;
int min_val = 999;
visited[c] = 1;
cout<<c + 1<<" ";
for(int k = 0; k<n; k++){
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 += min_val;
}
if (adj_vertex == 999){
adj_vertex = 0;
cout<<adj_vertex + 1;
cost += tsp_g[c][adj_vertex];
return;
}
travellingsalesman(adj_vertex);
}
int main(){
cout<<"Shortest Path: ";
travellingsalesman(0);
cout<<"\nMinimum Cost: ";
cout<<cost;
}
输出
根据以上代码
Shortest Path: 1 5 4 3 2 1 Minimum Cost: 129
tsp_g = [
[17, 30, 33, 10, 25],
[66, 22, 19, 15, 18],
[89, 13, 8, 25, 15],
[33, 25, 16, 30, 3],
[25, 33, 35, 24, 37]
]
visited = [0] * 10
n = 5
cost = 0
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 += tsp_g[c][adj_vertex]
return
travellingsalesman(adj_vertex)
print("Shortest Path: ", end = " ")
travellingsalesman(0)
print("\nMinimum Cost: ", cost)
输出
Shortest Path: 1 4 5 2 3 1 Minimum Cost: 154
旅行商问题：实际应用
TSP主要应用于以下方面：
车辆路线规划 - TSP通常用于运输和配送路线优化。对于配送公司而言，这个问题很重要，因为它有助于降低燃油消耗、减少所需的车辆数量并确保产品及时送达。
生物学 - TSP用于研究蛋白质折叠，以折叠成其最终的三维结构。
电路设计 - 它有助于确定最短路径，从而最大限度地减少电路的总电阻和电容。
结论
旅行商问题是一个广为研究的优化问题，其描述为确定一条最短路径，该路径恰好访问一组城市一次，然后返回到起点。有几种算法可以解决TSP，每种算法都具有其自身的优缺点。这些案例都突出了TSP的适应性和其用于解决各种情况的能力。
1K+ 次浏览
