在 Python 中找到连接所有点的最低成本的程序

Z时代
2024-01-10
分类：综合

假设我们有一个名为 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。

示例

让我们看看以下实现以更好地理解 -

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