在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))
输入
[(0,0),(3,3),(2,10),(6,3),(8,0)]
输出
22