Минимизируйте длину веревки, чтобы соединить заданные точки в 3D-плоскости

Опубликовано: 26 Февраля, 2023

Дан двумерный массив A[][] размера N × 3 , где каждый элемент массива имеет вид {x, y, z}, где x, y и z — координаты точки в трехмерном пространстве. Задача состоит в том, чтобы соединить все точки так, чтобы общая длина веревки была минимальной.

Примечание. Длина веревки, используемой для соединения двух точек A1(x1, y1, z1) и A2(x2, y2, z2), определяется как: min( |x1-x2|, |y1-y2|, |z1-z2 | )

Примеры:

Input: A[][] = { {1, 2, 3}, {6, 8, 1}, {5, 3, 4}, {8, 5, 6} }
Output: 4
Explanation: Minimum edges use to connect all edge
Distance of P1 and P3 is 1.
Distance of P2 and P3 is 1.
Distance of P4 and P3 is 2.
Total length of rope used = 1 + 1 + 2 = 4

Input: A[][] = { {0, 5, 0}, {8, 5, 0}, {0, 1, 56} }
Output: 0
Explanation: Minimum edges use to connect all edge
Distance of P1 and P2 is 0.
Distance of P1 and P3 is 0. 
Total length of rope used = 0 + 0 = 0

Наивный подход: основная идея состоит в том, чтобы соединить все точки и сформировать график. Затем проверьте все возможные комбинации ребер и найдите среди них минимальное.

Временная сложность: O( N^2 C N ), так как всего может быть N(N-1) ребер, и нам понадобится только (N-1) ребер из них для соединения графа.
Вспомогательное пространство: O(N)

Минимизируйте стоимость веревки для соединения точек с помощью минимального остовного дерева.

Эта проблема также может быть решена на основе концепции минимального остовного дерева (MST).

We will need to make a graph where the weight of each edge is the same as the distance between the points. The MST formed from that graph will have the minimum total distance among the points and so the required rope length will also be minimum.

Instead of connecting all the points we can build three separate graphs from the distances among the coordinates of each of the axis separately because of the special property of the distance. Consider those edges and use the concept of MST.

Для реализации идеи выполните следующие шаги:

  • Длина веревки, необходимая для соединения двух точек, зависит только от одной оси, разность которых минимальна.
  • Таким образом, все оси могут быть оценены отдельно.
  • Отсортируйте все три координаты отдельно.
  • Построить ребра с весом ребра, равным разности последовательных координат по всем трем осям отдельно.
  • Запустите алгоритм минимального остовного дерева на графе, чтобы найти минимальную длину необходимой веревки.

Кодовая реализация вышеуказанного подхода:

C++




// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > edges;
 
int findparent(int a, vector<int>& parentOf)
{
    if (parentOf[a] == -1)
        return a;
    return parentOf[a] = findparent(parentOf[a], parentOf);
}
 
void union_set(int a, int b, vector<int>& parentOf,
               vector<int>& rank)
{
    int s1 = findparent(a, parentOf);
    int s2 = findparent(b, parentOf);
 
    if (s1 != s2) {
        int r1 = rank[s1];
        int r2 = rank[s2];
        if (r1 >= r2) {
            parentOf[s2] = s1;
            rank[s1] = r1 + r2;
        }
        else {
            parentOf[s1] = s2;
            rank[s2] = r1 + r2;
        }
    }
}
int calculatemst(int N)
{
    int cost = 0;
    vector<int> rank(N + 1, -1);
    vector<int> parentOf(N + 1, -1);
    for (int i = 0; i < edges.size(); i++) {
        int wt = edges[i][0], a = edges[i][1],
            b = edges[i][2];
        if (findparent(a, parentOf)
            != findparent(b, parentOf)) {
            cost += wt;
            union_set(a, b, parentOf, rank);
        }
    }
    return cost;
}
void graph(vector<pair<int, int> > v)
{
    for (int i = 0; i < v.size() - 1; i++) {
        int dist = v[i + 1].first - v[i].first;
        int nodeone = v[i].second;
        int nodesecond = v[i + 1].second;
        edges.push_back({ dist, nodeone, nodesecond });
    }
}
void solve(int a[][3], int N)
{
    vector<pair<int, int> > x, y, z;
    for (int i = 0; i < N; i++) {
        x.push_back({ a[i][0], i + 1 });
        y.push_back({ a[i][1], i + 1 });
        z.push_back({ a[i][2], i + 1 });
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    sort(z.begin(), z.end());
    graph(x);
    graph(y);
    graph(z);
    sort(edges.begin(), edges.end());
    return;
}
 
// Drivers code
int main()
{
    int arr[][3] = {
        { 1, 2, 3 }, { 6, 8, 1 }, { 5, 3, 4 }, { 8, 5, 6 }
    };
 
    // Function Call
    solve(arr, 4);
    cout << calculatemst(4) << endl;
}

Java



// Java code for the above approach:
import java.util.*;
 
class GFG {
  static ArrayList<ArrayList<Integer> > edges
    = new ArrayList<>();
 
  static int findparent(int a, int[] parentOf)
  {
    if (parentOf[a] == -1)
      return a;
    return parentOf[a]
      = findparent(parentOf[a], parentOf);
  }
 
  static void union_set(int a, int b, int[] parentOf,
                        int[] rank)
  {
    int s1 = findparent(a, parentOf);
    int s2 = findparent(b, parentOf);
 
    if (s1 != s2) {
      int r1 = rank[s1];
      int r2 = rank[s2];
      if (r1 >= r2) {
        parentOf[s2] = s1;
        rank[s1] = r1 + r2;
      }
      else {
        parentOf[s1] = s2;
        rank[s2] = r1 + r2;
      }
    }
  }
  static int calculatemst(int N)
  {
    int cost = 0;
    int[] rank = new int[N + 1];
    int[] parentOf = new int[N + 1];
    Arrays.fill(rank, -1);
    Arrays.fill(parentOf, -1);
 
    for (int i = 0; i < edges.size(); i++) {
      int wt = edges.get(i).get(0);
      int a = edges.get(i).get(1);
      int b = edges.get(i).get(2);
      if (findparent(a, parentOf)
          != findparent(b, parentOf)) {
        cost += wt;
        union_set(a, b, parentOf, rank);
      }
    }
    return cost;
  }
  static void graph(ArrayList<pair> v)
  {
    for (int i = 0; i < v.size() - 1; i++) {
      int dist = v.get(i + 1).first - v.get(i).first;
      int nodeone = v.get(i).second;
      int nodesecond = v.get(i + 1).second;
      ArrayList<Integer> al = new ArrayList<>();
      al.add(dist);
      al.add(nodeone);
      al.add(nodesecond);
      edges.add(al);
    }
  }
  static void solve(int a[][], int N)
  {
    ArrayList<pair> x = new ArrayList<>();
    ArrayList<pair> y = new ArrayList<>();
    ArrayList<pair> z = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      x.add(new pair(a[i][0], i + 1));
      y.add(new pair(a[i][1], i + 1));
      z.add(new pair(a[i][2], i + 1));
    }
    Collections.sort(x, (pair A, pair B) -> {
      return A.first - B.first;
    });
    Collections.sort(y, (pair A, pair B) -> {
      return A.first - B.first;
    });
    Collections.sort(z, (pair A, pair B) -> {
      return A.first - B.first;
    });
    graph(x);
    graph(y);
    graph(z);
    Collections.sort(edges,
                     (ArrayList<Integer> A,
                      ArrayList<Integer> B) -> {
                       return A.get(0) - B.get(0);
                     });
    return;
  }
  static class pair {
    int first;
    int second;
    pair(int a, int b)
    {
      first = a;
      second = b;
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[][] = { { 1, 2, 3 },
                   { 6, 8, 1 },
                   { 5, 3, 4 },
                   { 8, 5, 6 } };
 
    // Function Call
    solve(arr, 4);
    System.out.println(calculatemst(4));
  }
}
 
// This code is contributed by karandeep1234.
Python3



# Python code for the above approach
edges = []
 
def findparent(a, parentOf):
    if (parentOf[a] == -1):
        return a
    parentOf[a] = findparent(parentOf[a], parentOf)
    return parentOf[a]
 
def union_set(a, b, parentOf, rank):
    s1 = findparent(a, parentOf)
    s2 = findparent(b, parentOf)
 
    if (s1 != s2):
        r1 = rank[s1]
        r2 = rank[s2]
        if (r1 >= r2):
            parentOf[s2] = s1
            rank[s1] = r1 + r2
        else:
            parentOf[s1] = s2
            rank[s2] = r1 + r2
 
def calculatemst(N):
    cost = 0
    rank = [-1] * (N + 1)
    parentOf = [-1] * (N + 1)
    for i in range(len(edges)):
        wt = edges[i][0]
        a = edges[i][1]
        b = edges[i][2]
        if (findparent(a, parentOf) != findparent(b, parentOf)):
            cost += wt
            union_set(a, b, parentOf, rank)
 
    return cost
 
def graph(v):
    for i in range(len(v) - 1):
        dist = v[i + 1][0] - v[i][0]
        nodeone = v[i][1]
        nodesecond = v[i + 1][1]
        edges.append([dist, nodeone, nodesecond])
 
def solve(a, N):
    x = []
    y = []
    z = []
    for i in range(N):
        x.append([a[i][0], i + 1])
        y.append([a[i][1], i + 1])
        z.append([a[i][2], i + 1])
 
    x.sort()
    y.sort()
    z.sort()
    graph(x)
    graph(y)
    graph(z)
    edges.sort()
    return
 
# Drivers code
arr = [[1, 2, 3], [6, 8, 1], [5, 3, 4], [8, 5, 6]]
 
# Function Call
solve(arr, 4)
print(calculatemst(4))
 
# This code is contributed by Saurabh Jaiswal
Javascript



<script>
        // JavaScript code for the above approach
        let edges = [];
 
        function findparent(a, parentOf) {
            if (parentOf[a] == -1)
                return a;
            return parentOf[a] = findparent(parentOf[a], parentOf);
        }
 
        function union_set(a, b, parentOf,
            rank) {
            let s1 = findparent(a, parentOf);
   &n
            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ