数据结构
网络
关系数据库管理系统 (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
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
旅行商问题：实际应用
TSP主要应用于以下方面：
车辆路线规划 - TSP通常用于运输和配送路线优化。对于配送公司而言，这个问题很重要，因为它有助于降低燃油消耗、减少所需的车辆数量并确保产品及时送达。
生物学 - TSP用于研究蛋白质折叠，以折叠成其最终的三维结构。
电路设计 - 它有助于确定最短路径，从而最大限度地减少电路的总电阻和电容。
结论
旅行商问题是一个广为研究的优化问题，其描述为确定一条最短路径，该路径恰好访问一组城市一次，然后返回到起点。有几种算法可以解决TSP，每种算法都具有其自身的优缺点。这些案例都突出了TSP的适应性和其用于解决各种情况的能力。
1K+ 次浏览
