C++で2次元デカルト座標点をすべて接続する最小コストを求めるプログラム

問題の概要

2次元デカルト座標上の点のリスト(x, y)が与えられたとします。点(x0, y0)と(x1, y1)を接続するときのコストは、|x0 − x1| + |y0 − y1|(マンハッタン距離)で表されます。任意の数の点を接続できる場合、すべての点がひとつのパスでつながるようにするために必要な最小コストを求めます。

例えば、入力が points = [[0, 0], [0, 2], [0, -2], [2, 0], [-2, 0], [2, 3], [2, -3]] の場合を考えてみましょう。

このとき出力は 14 になります。その理由は以下の通りです。

• (0, 0) から (0, 2)、(0, -2)、(2, 0)、(-2, 0) への接続コストはそれぞれ 2 で、合計は 8
• (2, 3) は (0, 2) に最も近く、コストは 3
• (2, -3) は (0, -2) に最も近く、コストも 3
• したがって合計コストは 8 + 6 = 14 となります

解法のアプローチ

この問題は、各点をグラフのノード、2点間のコストをエッジの重みとみなした最小全域木(MST)の構築問題として捉えることができます。ここではプリム法(Prim's algorithm)を用いて解きます。

手順は以下の通りです。

• MAX := 無限大(inf)
• 関数 interval(i, j, p) を定義します。点 i と点 j のマンハッタン距離 |p[i][x] − p[j][x]| + |p[i][y] − p[j][y]| を返します。
• メイン処理では以下を行います。
• n := 点の数(p のサイズ)。n < 2 の場合は 0 を返します。
• n 個の要素を持つ配列 distance を定義し、すべて MAX で初期化します。
• サイズ n の配列 visited を定義します。
• distance[0] := 0 とします。
• i を 0 から n 未満まで 1 ずつ増やしながら、以下を繰り返します。
  • min_d := MAX、node := 0 で初期化します。
  • j を 0 から n 未満まで走査し、visited[j] が false かつ distance[j] < min_d ならば、min_d := distance[j]、node := j と更新します。
  • visited[node] := true とし、cost += distance[node] を行います。
  • 再び j を走査し、visited[j] が false の場合は d := interval(node, j, p) を計算し、distance[j] := min(distance[j], d) と更新します。
• 最後に cost を返します。

このアルゴリズムの計算量は O(n²) であり、点の数がそれほど多くない場合には十分に高速に動作します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <iostream>
#include <vector>
#define MAX 99999
using namespace std;

int interval(int i, int j, vector<vector<int>>& p) {
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}

int solve(vector<vector<int>>& p) {
    int n = p.size(), cost = 0;
    if (n < 2) return 0;

    vector<int> distance(n, MAX);
    vector<bool> visited(n);

    distance[0] = 0;

    for (int i = 0; i < n; i++) {
        int min_d = MAX, node = 0;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && distance[j] < min_d) {
                min_d = distance[j];
                node = j;
            }
        }

        visited[node] = true;
        cost += distance[node];

        for (int j = 0; j < n; j++) {
            if (!visited[j]) {
                int d = interval(node, j, p);
                distance[j] = min(distance[j], d);
            }
        }
    }
    return cost;
}

int main(){
    vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}};
cout << solve(points);
}

入力

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}

出力

14