用 Python 编写程序，查找连接所有点的最低成本

pythonserver side programmingprogramming更新于 2025/11/26 11:24:17

假设我们有一个名为 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 := 一个新的集合，其中包含从 0 到点大小 - 1 的数字
heap := 用 (0, 0)
visited_node := 一个新的集合
total_distance := 0
当堆不为空且visited_node的大小<点的大小，执行
- (distance, current_index) := 从堆中删除元素
- 如果 current_index 不在 Visited_node 中，则
  - 将 current_index 插入 Visited_node
  - 从 points_set 中删除 current_index
  - total_distance := total_distance + distance
  - (x0, y0) := points[current_index]
  - 对于 points_set 中的每个 next_index，执行
    - (x1, y1) := points[next_index]
    - 将 (|x0 - x1| + |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))