Bài toán người bán hàng (TSP) dùng để tính lộ trình ngắn nhất đi qua tất cả các thành phố và quay lại thành phố xuất phát. Phương pháp này dùng để tìm đường đi ngắn nhất bao phủ tất cả các nút của đồ thị.
Đây là chương trình tìm lộ trình ngắn nhất của đồ thị không trọng số.
Thuật toán
Bắt đầu
Định nghĩa biến vr = 4 toàn cục.
Khai báo hàm nguyên TSP triển khai bài toán người bán hàng.
Khai báo đồ thị grph[][] dạng ma trận 2D và biến p kiểu nguyên.
Truyền chúng làm tham số.
Khai báo biến ver kiểu vector.
for (int i = 0; i < vr; i++)
if (i != p) thì
Gọi push_back(i) để lưu giá trị tất cả đỉnh trừ đỉnh nguồn.
Khởi tạo m_p = INT_MAX để lưu trọng số nhỏ nhất của đồ thị.
do
Khai báo cur_pth, k kiểu nguyên.
Khởi tạo cur_pth = 0.
Khởi tạo k = p.
for (int i = 0; i < ver.size(); i++)
cur_pth += grph[k][ver[i]].
k = ver[i].
cur_pth += grph[k][p].
m_p = min(m_p, cur_pth) để cập nhật trọng số nhỏ nhất.
while (next_permutation(ver.begin(), ver.end())).
Trả về m_p.
Khai báo đồ thị grph[][] dạng ma trận 2D kiểu nguyên.
Khởi tạo giá trị grph[][].
Khai báo biến p kiểu nguyên.
Khởi tạo p = 0.
In "The result is: ".
In giá trị trả về của hàm TSP().
Kết thúc.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define vr 4
int TSP(int grph[][vr], int p) // triển khai bài toán người bán hàng.
{
vector<int> ver; //
for (int i = 0; i < vr; i++)
if (i != p)
ver.push_back(i);
int m_p = INT_MAX; // lưu trọng số nhỏ nhất của đồ thị
do {
int cur_pth = 0;
int k = p;
for (int i = 0; i < ver.size(); i++) {
cur_pth += grph[k][ver[i]];
k = ver[i];
}
cur_pth += grph[k][p];
m_p = min(m_p, cur_pth); // cập nhật giá trị trọng số nhỏ nhất
}
while (next_permutation(ver.begin(), ver.end()));
return m_p;
}
int main() {
int grph[][vr] = { { 0, 5, 10, 15 }, // giá trị đồ thị dạng ma trận
{ 5, 0, 20, 30 },
{ 10, 20, 0, 35 },
{ 15, 30, 35, 0 }
};
int p = 0;
cout << "\n The result is: " << TSP(grph, p) << endl;
return 0;
}
Kết quả
The result is: 75