Pythonですべてのポイントを接続するための最小コストを見つけるためのプログラム

（x、y）の形式のいくつかの点を持つpointsという配列があるとします。ここで、2つのポイント（xi、yi）と（xj、yj）を接続するコストは、それらの間のマンハッタン距離であり、式は| xi--xj|です。 + | yi--yj|。すべてのポイントを接続するための最小コストを見つける必要があります。

したがって、入力がpoints =[（0,0）、（3,3）、（2,10）、（6,3）、（8,0）]のようである場合、出力は22になります。 P>

したがって、ここでの合計距離は（6 + 5 + 3 + 8）=22です。

これを解決するには、次の手順に従います-

• points_set：=範囲0からポイントのサイズ-1までの数値を保持する新しいセット
• ヒープ：=ペア（0、0）でヒープを作成します
• visited_node：=新しいセット
• total_distance：=0
• ヒープが空ではなく、visited_nodeのサイズ<ポイントのサイズ、do
  • （distance、current_index）：=ヒープから要素を削除
  • current_indexがvisited_nodeに存在しない場合、
    • 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）を挿入します
• return 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