在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大小的数字的新集合
heap：用一对（0，0）生成堆
visited_node：一个新的集合
total_distance：0
当堆不为空且被访问节点的大小小于点的大小时，执行以下操作
- （距离，current_index）：从堆中删除元素
- 如果当前索引未出现在visited_node中，那么
  - 将当前索引插入visited_node中
  - 从points_set中删除当前索引
  - total_distance：total_distance + distance
  - （x0，y0）：points[current_index]
  - 对于每个points_set中的下一个索引，执行以下操作
  - （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))