C++で全ての3D座標を巡回する最小移動コストを求めるプログラム

問題概要

n 個の三次元座標が与えられます。ある座標 (a, b, c) から別の座標 (x, y, z) へ移動するときのコストは、次の式で定義されます。

|x − a| + |y − b| + max(0, z − c)

この式のポイントは、max(0, z − c) の部分です。z 軸方向の移動では「上方向へ登る場合のみ」追加コストが発生し、水平方向や下方向への移動にはコストがかかりません。

私たちは最初の座標から出発し、すべての座標を少なくとも一度ずつ訪問した後、再び出発点である最初の座標へ戻ります。この一連の旅全体にかかる合計コストの最小値を求めるのが目的です。座標は配列 coords として与えられます。

たとえば、入力が n = 3、coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}} の場合、出力は 12 になります。

アプローチ：ビットマスクDPで巡回セールスマン問題を解く

この問題は、「どの座標を既に訪問したか」という状態を管理しながら最適な訪問順序を決める、いわゆる巡回セールスマン問題（TSP）と同じ構造を持っています。各座標の訪問状況をビットマスク（整数の各ビット）で表現し、動的計画法（DP）で効率的に解きます。

• 2次元配列 tpa を用意します。tpa[i][j] は「訪問済みの座標集合がビットマスク i であり、現在 j 番目の座標にいるときの最小コスト」を表します。
• 初期状態として tpa[1][0] = 0 を設定します（0番目の座標から出発するため、ビット0だけが立った状態）。
• すべての状態 (i, j) について、次に訪れる座標 t を全通り試し、移動コストを加えて DP テーブルを更新します。
• なお、i が偶数（ビット0が立っていない）の状態は到達不可能なため、あらかじめ除外します。
• 最後に、すべての座標を訪問した状態（2ⁿ − 1）から出発点へ戻るコストを加え、その最小値を答えとします。

アルゴリズムの手順

2次元配列 tpa を定義する。
tpa[1][0] := 0
i := 1 から始め、i < 2^n の間、i を 1 ずつ増やしながら繰り返す：
　　j := 0 から始め、j < n の間、j を 1 ずつ増やしながら繰り返す：
　　　　もし i が偶数（i mod 2 == 0）なら、次の反復へスキップする
　　　　t := 0 から始め、t < n の間、t を 1 ずつ増やしながら繰り返す：
　　　　　　x := coords[t] の第1要素
　　　　　　y := coords[t] の第2要素
　　　　　　z := coords[t] の第3要素
　　　　　　p := coords[j] の第1要素
　　　　　　q := coords[j] の第2要素
　　　　　　r := coords[j] の第3要素
　　　　　　tpa[i OR (1 を t ビット左シフト)][t] :=
　　　　　　　　min(tpa[i|(1 << t)][t], tpa[i][j] + |x - p| + |y - q| + max(0, z - r))
res := 無限大
i := 0 から始め、i < n の間、i を 1 ずつ増やしながら繰り返す：
　　x := coords[0] の第1要素
　　y := coords[0] の第2要素
　　z := coords[0] の第3要素
　　p := coords[i] の第1要素
　　q := coords[i] の第2要素
　　r := coords[i] の第3要素
　　res := min(res, tpa[2^n - 1][i] + |x - p| + |y - q| + max(0, z - r))
res を返す

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int solve(int n, vector<tuple<int,int,int>> coords){
    vector<vector<int>> tpa(pow(2, n), vector<int>(n, INF));
    tpa[1][0] = 0;
    for(int i = 1; i < pow(2,n); i++) {
        for(int j = 0; j < n; j++){
            if(i % 2 == 0)
                continue;
            for(int t = 0; t < n; t++) {
                int x, y, z, p, q, r;
                tie(x, y, z) = coords[t];
                tie(p, q, r) = coords[j];
                tpa[i | (1 << t)][t] = min(tpa[i|(1 << t)][t], tpa[i][j] + abs(x - p) + abs(y - q) + max(0, z - r));
            }
        }
    }
    int res = INF;
    for(int i = 0; i < n; i++) {
        int x, y, z, p, q, r;
        tie(x, y, z) = coords[0];
        tie(p, q, r) = coords[i];
        res = min(res, tpa[pow(2, n) - 1][i] + abs(x - p) + abs(y - q) + max(0, z - r));
    }
    return res;
}
int main() {
    int n = 3;
    vector<tuple<int,int,int>> coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}};
    cout<< solve(n, coords);
    return 0;
}

計算量

時間計算量は O(2ⁿ × n²)、空間計算量は O(2ⁿ × n) となります。計算量が n に対して指数関数的に増加するため、この手法は n が20程度までの問題に適しています。

入力

3, {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}

出力

12