โปรแกรมหาต้นทุนน้อยที่สุดเชื่อมจุดทั้งหมดใน Python

ปัญหา

จุด points (x,y) ต้นทุนเชื่อม 2 จุด = Manhattan distance |xi-xj|+|yi-yj| หาต้นทุนน้อยที่สุดเชื่อมทุกจุด (MST)

ตัวอย่าง

points=[(0,0),(3,3),(2,10),(6,3),(8,0)] → 22

ขั้นตอนการแก้ปัญหา

1. Prim's algorithm: points_set := set(0..n-1), heap := [(0,0)]
2. visited := set(), total := 0
3. بينما heap and len(visited) < n:
   • dist, u := heappop(heap)
   • ถ้า u not in visited:
     • visited.add(u), points_set.discard(u), total += dist
     • สำหรับ v ใน points_set: push (manhattan(u,v), v) เข้า heap
4. คืน total

การนำไปใช้งาน (Python)

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

เอาต์พุต

22