Python程序：查找连接所有点的最小成本

假设我们有一个名为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 到 points 大小 - 1 的数字
  • heap := 创建一个堆，包含 (0, 0) 对
  • visited_node := 一个新的集合
  • total_distance := 0
  • 当堆不为空且 visited_node 的大小 < points 的大小时，执行以下操作
    • (distance, current_index) := 从堆中删除元素
    • 如果 visited_node 中不存在 current_index，则
      • 将 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))

输入

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

输出

22

更新于: 2021年10月4日

394 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告