Cài đặt thuật toán Nearest Neighbour trong C++

Thuật toán Nearest Neighbour (láng giềng gần nhất) dùng để giải xấp xỉ bài toán TSP: bắt đầu từ một đỉnh, lặp lại chọn đỉnh chưa thăm gần nhất cho đến khi thăm hết.

Ví dụ minh họa (tương tự TSP)

#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);
    }
}

int main() {
    int a[] = {0,1,2};
    permute(a, 0, 2);
    cout << "Chi phi toi thieu: " << cost << endl;
    return 0;
}

Kết quả

Chi phi toi thieu: 13