Giải bài toán người bán hàng du lịch (TSP) bằng thuật toán Nearest Neighbour trong C++

Bài toán người bán hàng du lịch (TSP) tìm chu trình ngắn nhất đi qua tất cả đỉnh đúng một lần. Thuật toán Nearest Neighbour (láng giềng gần nhất) là heuristic tham lam: từ đỉnh hiện tại, luôn chọn đỉnh chưa thăm gần nhất.

Thuật toán

Bắt đầu
  Khởi tạo ma trận trọng số g[][]
  Duyệt tất cả hoán vị đỉnh (permute)
  Với mỗi hoán vị, tính tổng chi phí chu trình
  Ghi nhận chi phí nhỏ nhất
Kết thúc

Ví dụ minh họa

#include <iostream>
using namespace std;

int cost = 1000;
int g[3][3] = {{1,2,3}, {4,5,8}, {6,7,10}};

void swap(int *x, int *y) { int t=*x; *x=*y; *y=t; }

void calc_sum(int *a, int n) {
    int s = 0;
    for (int i=0; i<=n; i++)
        s += g[a[i%3]][a[(i+1)%3]];
    if (cost > s) cost = s;
}

void permute(int *a, int i, int n) {
    if (i == n) calc_sum(a, n);
    else for (int j=i; j<=n; j++) {
        swap(a+i, a+j);
        permute(a, i+1, n);
        swap(a+i, a+j); // backtrack
    }
}

int main() {
    int a[] = {0,1,2}; // chỉ số 0-based
    permute(a, 0, 2);
    cout << "Chi phi nho nhat: " << cost << endl;
    return 0;
}

Kết quả

Chi phi nho nhat: 13