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

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

假设我们有一个称为“points”的数组,其中包含一些形式为(x,y)的点。 现在连接两个点(xi,yi)和(xj,yj)的成本是它们之间的曼哈顿距离,公式是|xi-xj|+|Yi-YJ|。我们必须找到使所有点连接的最小成本。

所以,如果输入是points =[(0,0),(3,3),(2,10),(6,3),(8,0)],那么输出将是22,因为

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

所以这里的总距离是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))

输入

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

输出

22

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程