Nearest Neighbour Algorithm ใน C++: การประยุกต์กับ TSP

Nearest Neighbour Algorithm เป็น heuristic แบบ Greedy สำหรับหาเส้นทางประมาณการใน Traveling Salesman Problem (TSP) โดยเลือกเมืองที่ใกล้ที่สุดซ้ำๆ

อัลกอริทึม

1. เริ่มจากเมืองหนึ่ง (start city)
2. หาเมืองที่ยังไม่ได้เยี่ยมชมและมีระยะทางสั้นที่สุดจากเมืองปัจจุบัน
3. ย้ายไปเมืองนั้น ทำเครื่องหมายว่าเยี่ยมชมแล้ว
4. ทำซ้ำจนครบทุกเมือง
5. กลับไปเมืองเริ่มต้น

ตัวอย่างโค้ด (Complete)

#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>

using namespace std;

class NearestNeighbourTSP {
    vector<vector<double>> dist;
    int n;
    
public:
    NearestNeighbourTSP(const vector<vector<double>>& matrix) 
        : dist(matrix), n(matrix.size()) {}
    
    struct Result {
        vector<int> tour;
        double cost;
    };
    
    Result solve(int start = 0) {
        vector<bool> visited(n, false);
        vector<int> tour;
        tour.reserve(n + 1);
        
        int current = start;
        tour.push_back(current);
        visited[current] = true;
        double totalCost = 0.0;
        
        for (int step = 1; step < n; ++step) {
            int nextCity = -1;
            double minDist = numeric_limits<double>::infinity();
            
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && dist[current][i] < minDist) {
                    minDist = dist[current][i];
                    nextCity = i;
                }
            }
            
            if (nextCity == -1) {
                cerr << "Graph not fully connected!" << endl;
                break;
            }
            
            tour.push_back(nextCity);
            visited[nextCity] = true;
            totalCost += minDist;
            current = nextCity;
        }
        
        // Return to start
        totalCost += dist[current][start];
        tour.push_back(start);
        
        return {tour, totalCost};
    }
    
    Result solveBest() {
        Result best;
        best.cost = numeric_limits<double>::infinity();
        
        for (int start = 0; start < n; ++start) {
            Result r = solve(start);
            if (r.cost < best.cost) best = r;
        }
        return best;
    }
};

void printMatrix(const vector<vector<double>>>> mat) {
    cout << "Distance Matrix:" << endl;
    for (const auto& row : mat) {
        for (double d : row) {
            cout << setw(6) << d;
        }
        cout << endl;
    }
}

int main() {
    // Example: 5 cities
    vector<vector<double>> distances = {
        {0,  10, 15, 20, 25},
        {10, 0,  35, 25, 30},
        {15, 35, 0,  30, 20},
        {20, 25, 30, 0,  15},
        {25, 30, 20, 15, 0}
    };
    
    printMatrix(distances);
    
    NearestNeighbourTSP solver(distances);
    
    cout << "\n--- Starting from city 0 ---" << endl;
    auto result = solver.solve(0);
    cout << "Tour: ";
    for (int c : result.tour) cout << c << " ";
    cout << "\nCost: " << result.cost << endl;
    
    cout << "\n--- Best starting city ---" << endl;
    auto best = solver.solveBest();
    cout << "Tour: ";
    for (int c : best.tour) cout << c << " ";
    cout << "\nCost: " << best.cost << endl;
    
    return 0;
}

ผลลัพธ์

Distance Matrix:
     0    10    15    20    25
    10     0    35    25    30
    15    35     0    30    20
    20    25    30     0    15
    25    30    20    15     0

--- Starting from city 0 ---
Tour: 0 1 3 4 2 0
Cost: 85

--- Best starting city ---
Tour: 2 4 3 1 0 2
Cost: 80

การสร้าง Distance Matrix จากพิกัด

#include <cmath>

vector<vector<double>> createDistanceMatrix(const vector<pair<double,double>>>> coords) {
    int n = coords.size();
    vector<vector<double>> dist(n, vector<double>(n));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            double dx = coords[i].first - coords[j].first;
            double dy = coords[i].second - coords[j].second;
            dist[i][j] = sqrt(dx*dx + dy*dy);  // Euclidean distance
        }
    }
    return dist;
}

ข้อดี/ข้อเสีย

เมื่อไหร่ควรใช้

• ต้องการคำตอบเร็ว (real-time routing)
• n ใหญ่มาก (exact algorithms ไม่ทัน)
• เป็น baseline ก่อนปรับปรุงด้วย local search (2-opt, 3-opt)
• Metric TSP (triangle inequality holds)