Traveling Salesman Problem (TSP) ด้วย Nearest Neighbour Algorithm ใน C++

Traveling Salesman Problem (TSP) เป็นปัญหา optimization หาเส้นทางสั้นที่สุดที่ผ่านทุกเมืองครั้งละครั้งและกลับมาที่เริ่มต้น Nearest Neighbour เป็น heuristic แบบ greedy ให้คำตอบประมาณการรวดเร็ว

อัลกอริทึม Nearest Neighbour

1. เริ่มจากเมืองใดเมืองหนึ่ง
2. หาเมืองที่ใกล้ที่สุดที่ยังไม่ได้ไป
3. ไปที่เมืองนั้น ทำซ้ำจนครบทุกเมือง
4. กลับไปเมืองเริ่มต้น

Complexity: O(n²) ให้คำตอบไม่เกิน 2× optimal (สำหรับ metric TSP)

ตัวอย่างโค้ด (ปรับปรุงจากต้นฉบับ)

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

struct TSPResult {
    vector<int> path;
    double totalDistance;
};

class TSPSolver {
    vector<vector<double>> distMatrix;
    int n;
    
public:
    TSPSolver(const vector<vector<double>>& matrix) 
        : distMatrix(matrix), n(matrix.size()) {}
    
    TSPResult nearestNeighbour(int start = 0) {
        vector<bool> visited(n, false);
        vector<int> path;
        path.reserve(n + 1);
        
        int current = start;
        path.push_back(current);
        visited[current] = true;
        double totalDist = 0.0;
        
        // หา nearest neighbor ซ้ำ n-1 ครั้ง
        for (int step = 1; step < n; ++step) {
            int next = -1;
            double minDist = numeric_limits<double>::max();
            
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && distMatrix[current][i] < minDist) {
                    minDist = distMatrix[current][i];
                    next = i;
                }
            }
            
            if (next == -1) break; // ไม่มีทางไปต่อ (disconnected)
            
            path.push_back(next);
            visited[next] = true;
            totalDist += minDist;
            current = next;
        }
        
        // กลับไปจุดเริ่มต้น
        totalDist += distMatrix[current][start];
        path.push_back(start);
        
        return {path, totalDist};
    }
    
    // ลองเริ่มจากทุกเมือง หาค่าที่ดีที่สุด
    TSPResult bestNearestNeighbour() {
        TSPResult best;
        best.totalDistance = numeric_limits<double>::max();
        
        for (int start = 0; start < n; ++start) {
            TSPResult result = nearestNeighbour(start);
            if (result.totalDistance < best.totalDistance) {
                best = result;
            }
        }
        return best;
    }
};

int main() {
    // Distance matrix (symmetric)
    vector<vector<double>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    TSPSolver solver(dist);
    
    // เริ่มจากเมือง 0
    auto result = solver.nearestNeighbour(0);
    
    cout << "Path: ";
    for (int city : result.path) {
        cout << city << " ";
    }
    cout << "\nTotal Distance: " << result.totalDistance << endl;
    
    // หาค่าที่ดีที่สุดจากทุกจุดเริ่มต้น
    auto best = solver.bestNearestNeighbour();
    cout << "\nBest start city: " << best.path[0] << endl;
    cout << "Best Distance: " << best.totalDistance << endl;
    
    return 0;
}

ผลลัพธ์

Path: 0 1 3 2 0
Total Distance: 80

Best start city: 0
Best Distance: 80

การปรับปรุง: 2-Opt Local Search

Nearest Neighbour ให้คำตอบเร็วแต่อาจไม่ดีพอ ใช้ 2-Opt ปรับปรุง:

void twoOpt(vector<int>& path, const vector<vector<double>>>> dist) {
    bool improved = true;
    while (improved) {
        improved = false;
        for (int i = 1; i < path.size() - 2; ++i) {
            for (int k = i + 1; k < path.size() - 1; ++k) {
                double current = dist[path[i-1]][path[i]] + dist[path[k]][path[k+1]];
                double swapped = dist[path[i-1]][path[k]] + dist[path[i]][path[k+1]];
                if (swapped < current) {
                    reverse(path.begin() + i, path.begin() + k + 1);
                    improved = true;
                }
            }
        }
    }
}

ข้อจำกัดของ Nearest Neighbour

• ไม่ guarantee optimal solution
• ผลลัพธ์ขึ้นกับ starting city
• ไม่คำนึงถึง global structure

อัลกอริทึม TSP อื่นๆ