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 になります。これは、各辺の距離がそれぞれ 6 + 5 + 3 + 8 = 22 となるように点同士を接続できるからです。

解決のアプローチ

この問題は、プリム法（Prim's Algorithm）と呼ばれる最小全域木（MST）のアルゴリズムを使うことで効率的に解けます。優先度付きキュー（ヒープ）を活用し、常に現時点で最もコストの低い接続を選び取っていくのがポイントです。

具体的な手順は以下の通りです。

• points_set: 0 から points のサイズ − 1 までのインデックスを持つ集合を作成する
• heap: ペア (0, 0) を含むヒープを作成する
• visited_node: 訪問済みノードを記録する空の集合を作成する
• total_distance: 合計距離を格納する変数を 0 で初期化する
• ヒープが空でなく、かつ訪問済みノード数が points のサイズ未満である間、以下を繰り返す
  • (distance, current_index) をヒープから取り出す
  • current_index が訪問済みでない場合：
    • current_index を visited_node に追加し、points_set から削除する
    • total_distance に distance を加算する
    • (x0, y0) := points[current_index] とする
    • points_set 内の各 next_index について：
      • (x1, y1) := points[next_index] とする
      • (|x0 − x1| + |y0 − y1|, next_index) をヒープに挿入する
• 最後に total_distance を返す

実装例

以下にPythonでの実装例を示します。

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

計算量について

この実装では、各点を訪問するたびに残りのすべての点との距離を計算してヒープに追加するため、時間計算量は O(N² log N) となります。N は点の数です。より大規模なデータセットに対しては、Kruskal法やボロノイ図を利用した最適化なども検討できますが、中規模程度の問題であればこのシンプルなプリム法の実装で十分に高速に動作します。