สมมติว่าเรามีรายการพิกัด 2D แบบ Cartesian (x, y) เราสามารถเชื่อม (x0, y0) และ (x1, y1) ได้ โดยต้นทุนคือ |x0 - x1| + |y0 - y1| (ระยะทางแมนฮัตตัน) หากเราได้เชื่อมจุดได้ไม่จำกัดจำนวน เราต้องหาต้นทุนขั้นต่ำที่ทำให้ทุกจุดเชื่อมต่อกันโดยมีพาธ
เช่น หาก points = [[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2, -3]]
ผลลัพธ์คือ 14 เพราะจาก (0,0) ไป (0,2), (0,-2), (2,0), (-2,0) ต้นทุนแต่ละคู่คือ 2 รวม 8 และ (2,3) ใกล้ (0,2) ต้นทุน |2-0|+|3-2|=3 และ (2,-3) ใกล้ (0,-2) ต้นทุน 3 รวม 8+6=14
ขั้นตอนการแก้ปัญหา (อัลกอริทึม Prim)
- MAX := ค่ามากที่สุด (infinity)
- ฟังก์ชัน interval(i, j, p) คืนค่า |p[i][0]-p[j][0]| + |p[i][1]-p[j][1]|
- n := ขนาดของ p, ถ้า n < 2 คืนค่า 0
- อาเรย์ distance ขนาด n เติม MAX, visited ขนาด n
- distance[0] := 0
- วนลูป i จาก 0 ถึง n-1:
- หาจุด node ที่ยังไม่ visited และ distance น้อยที่สุด
- visited[node] := true, cost += distance[node]
- อัปเดต distance ของจุดที่ยังไม่ visited: distance[j] = min(distance[j], interval(node, j, p))
- คืนค่า cost
ตัวอย่างโค้ด
#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); }
อินพุต
{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}
เอาต์พุต
14
