Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम

मान लीजिए हमारे पास points नामक एक ऐरे है जिसमें कुछ पॉइंट्स (x, y) के रूप में हैं। अब दो पॉइंट्स (xi, yi) और (xj, yj) को जोड़ने की लागत उनके बीच की मैनहट्टन दूरी है, सूत्र है |xi - xj| + |yi - yj|। हमें सभी पॉइंट्स को जोड़ने की न्यूनतम लागत ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है points = [(0,0),(3,3),(2,10),(6,3),(8,0)], तो आउटपुट 22 होगा क्योंकि: Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम तो यहां कुल दूरी (6+5+3+8) = 22 है।

समाधान के चरण

points_set := set(range(len(points)))
heap := [(0, 0)] (जोड़ी के साथ हीप)
visited_node := set()
total_distance := 0
while heap and len(visited_node) < len(points):
- (distance, current_index) := heapq.heappop(heap)
- यदि current_index not in visited_node:
  - visited_node.add(current_index)
  - points_set.discard(current_index)
  - total_distance += distance
  - (x0, y0) := points[current_index]
  - points_set में प्रत्येक next_index के लिए:
    - (x1, y1) := points[next_index]
    - heapq.heappush(heap, (abs(x0-x1) + abs(y0-y1), next_index))
total_distance वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

import heapq

def solve(points):
    points_set = set(range(len(points)))
    heap = [(0, 0)]
    visited_node = set()
    total_distance = 0
    while heap and len(visited_node) < len(points):
        distance, current_index = heapq.heappop(heap)
        if current_index not in visited_node:
            visited_node.add(current_index)
            points_set.discard(current_index)
            total_distance += distance
            x0, y0 = points[current_index]
            for next_index in points_set:
                x1, y1 = points[next_index]
                heapq.heappush(heap, (abs(x0 - x1) + abs(y0 - y1), next_index))
    return total_distance

points = [(0,0),(3,3),(2,10),(6,3),(8,0)]
print(solve(points))

इनपुट

[(0,0),(3,3),(2,10),(6,3),(8,0)]