C++ में कार्टेशियन निर्देशांकों को जोड़ने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास 2D कार्टेशियन निर्देशांक बिंदुओं (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+1| = 3 और (2, -3) (0, -2) के निकटतम है, लागत भी 3। तो कुल लागत 8 + 6 = 14 है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम प्रिम के एल्गोरिदम (न्यूनतम स्पैनिंग ट्री) का उपयोग करते हैं:

MAX := INF
एक फंक्शन interval() परिभाषित करें जो i, j, और बिंदु सरणी p लेता है,
- |p[i][0] - p[j][0]| + |p[i][1] - p[j][1]| लौटाएं
मुख्य विधि से:
- n := p का आकार
- यदि n < 2, तो 0 लौटाएं
- आकार n का एक सरणी distance परिभाषित करें और MAX से भरें
- आकार n का एक सरणी visited परिभाषित करें
- distance[0] := 0
- i := 0 से n-1 तक:
  - min_d := MAX, node := 0
  - j := 0 से n-1 तक:
    - यदि visited[j] गलत है और distance[j] < min_d:
      - min_d := distance[j]
      - node := j
  - visited[node] := true
  - cost := cost + distance[node]
  - j := 0 से n-1 तक:
    - यदि visited[j] गलत है:
      - d := interval(node, j, p)
      - distance[j] := min(distance[j], d)
- 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}}