資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
