পাইথনে সব পয়েন্ট কানেক্ট করার ন্যূনতম খরচ বের করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে points যাতে কিছু পয়েন্ট (x,y) আকারে রয়েছে। দুটি পয়েন্ট (xi,yi) এবং (xj,yj) কানেক্ট করার খরচ হল তাদের ম্যানহ্যাটান দূরত্ব: |xi-xj| + |yi-yj|। সব পয়েন্ট কানেক্ট করার ন্যূনতম খরচ বের করতে হবে।

যেমন, ইনপুট হলে points = [(0,0),(3,3),(2,10),(6,3),(8,0)], তবে আউটপুট হবে 22 কারণ (চিত্র দেখুন) মোট দূরত্ব (6+5+3+8) = 22।

সমাধানের ধাপসমূহ

points_set := set(range(len(points)))
heap := [(0, 0)]
visited_node := set(), total_distance := 0
heap ও visited_node থাকা পর্যন্ত:
- (distance, current_index) := 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]
    - 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)]