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

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

इसलिए, यदि इनपुट पॉइंट्स की तरह है =[(0,0),(3,3),(2,10),(6,3),(8,0)], तो आउटपुट 22 होगा क्योंकि

तो यहाँ कुल दूरी है (6+5+3+8) =22.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

points_set :=0 से लेकर पॉइंट्स के आकार तक की संख्या - 1 के लिए एक नया सेट होल्डिंग नंबर - 1
ढेर:=जोड़ी के साथ ढेर बनाएं (0, 0)
विज़िट_नोड:=एक नया सेट
कुल_दूरी:=0
जबकि ढेर खाली नहीं है और विज़िट किए गए_नोड का आकार <अंकों का आकार, करते हैं
- (दूरी, current_index):=ढेर से तत्व हटाएं
- यदि current_index विज़िट किए गए_नोड में मौजूद नहीं है, तो
  - current_index को विज़िट किए गए_नोड में डालें
  - प्वाइंट_सेट से current_index हटाएं
  - कुल_दूरी:=कुल_दूरी+दूरी
  - (x0, y0) :=अंक [current_index]
  - प्वाइंट_सेट में प्रत्येक अगले_इंडेक्स के लिए, करें
    - (x1, y1) :=अंक [next_index]
    - हीप में डालें (|x0 - x1| + |y0 - y1| , next_index)
वापसी कुल_दूरी

उदाहरण

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

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)]