Chương trình tìm chi phí nhỏ nhất để nối các tọa độ Descartes trong C++

Giả sử chúng ta có một danh sách các điểm tọa độ Descartes 2D (x, y). Chi phí để nối (x0, y0) và (x1, y1) là |x0 - x1| + |y0 - y1|. Nếu được phép nối bất kỳ số điểm nào, chúng ta phải tìm chi phí tối thiểu sao cho mọi điểm đều được nối bởi một đường đi.

Ví dụ, với points = [[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2, -3]], kết quả là 14. Từ (0, 0) đến (0, 2), (0, -2), (2, 0), (-2, 0) chi phí lần lượt là 2, tổng 8. (2, 3) gần (0, 2) nhất, chi phí |2| + |1| = 3. (2, -3) gần (0, -2) nhất, chi phí cũng 3. Tổng = 8 + 6 = 14.

Giải thuật

Đây là bài toán cây bao trùm tối thiểu (MST) với khoảng cách Manhattan. Sử dụng thuật toán Prim:

• MAX := vô cực
• Hàm interval(i, j, p) trả về khoảng cách Manhattan giữa p[i] và p[j]
• n := kích thước p
• Nếu n < 2, trả về 0
• Mảng distance kích thước n, khởi tạo MAX; mảng visited kích thước n
• distance[0] := 0
• Vòng lặp n lần:
  • Tìm đỉnh node chưa thăm có distance nhỏ nhất
  • Đánh dấu visited[node] = true
  • cost += distance[node]
  • Cập nhật distance cho các đỉnh chưa thăm: distance[j] = min(distance[j], interval(node, j, p))
• Trả về cost

Ví dụ minh họa

#include <iostream> 
#include <vector> 
#define MAX 99999 
using namespace std; 

int interval(int i, int j, vector<vector<int>>& p) { 
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]); 
} 

int solve(vector<vector<int>>& p) { 
    int n = p.size(), cost = 0; 
    if (n < 2) return 0; 
    vector<int> distance(n, MAX); 
    vector<bool> visited(n); 
    distance[0] = 0; 
    for (int i = 0; i < n; i++) { 
        int min_d = MAX, node = 0; 
        for (int j = 0; j < n; j++) { 
            if (!visited[j] && distance[j] < min_d) { 
                min_d = distance[j]; 
                node = j; 
            } 
        } 
        visited[node] = true; 
        cost += distance[node]; 
        for (int j = 0; j < n; j++) { 
            if (!visited[j]) { 
                int d = interval(node, j, p); 
                distance[j] = min(distance[j], d); 
            } 
        } 
    } 
    return cost; 
} 

int main(){ 
    vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}; 
    cout << solve(points); 
} 

Đầu vào

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}

Đầu ra

14