問題概要
3 次元空間 $\mathbb R^3$ 上に都市 $1$ から都市 $N$ の $N$ 個の都市がある.都市 $i$ の座標は $( X_i, Y_i, Z_i )$ で与えられる.
都市 $i$ から都市 $j$ に移動するときにかかるコストは $| X_i - X_j | + | Y_i - Y_j | + \max( 0, Z_j - Z_i )$ である.
都市 $1$ を出発して,すべての都市を 一度以上通って都市 $1$ に戻ってくるときに必要なコストの最小値を求めよ.
制約
- $2 \leq N \leq 17$
- $-10^6 \leq X_i, Y_i, Z_i 10^6$
- 与えられる都市の座標は相異なる
解法
距離関数が特殊な形をしていることと,各都市を「丁度一度」ではなく「一度以上」訪問できる点が,よくある TSP (Traveling Salesman Problem) とは異なります.ちょっと気にしてあげないといけないのは,同じ都市を何度も通るようなルートを考慮する必要性の有無です.距離を求める式を $| X_i - X_j | + | Y_i - Y_j |$ の部分(単なる Manhattan 距離)と $\max( 0, Z_j - Z_i )$ に分けてみると見通しがよいかと思いますが,この距離関数は三角不等式を満たします.すなわち,2 点間の距離を $d( *, * )$ で表すとすれば,空間上の 3 点 $a, b, c$ について,$d( a, b ) + d( b, c ) \geq d( a, c )$ が成り立ちます.つまり,ある点からある点に移動するとき,どこか遠回りをして得をすることはありません.結果として,各都市は丁度一度ずつ訪問するという制約でもよいことになり,通常の TSP と同じになります.
通常の TSP に対しては,$O( 2^N N^2 )$ 時間で解くアルゴリズムが知られて [1] おり,今回もそのアルゴリズムで解くことができます.具体的には,都市の集合を $S$ で表すことにすると,
- $dp[S][i] \overset{def}{ \Longleftrightarrow } $ $S$ に含まれる都市は訪問済みで,現在地は $i$ な状態に至る最小コスト
という DP をします.初期化は
- $dp[ \emptyset ][0] = 0$
- $dp[S][i] = \infty$
です.ここで各状態 $dp[S][i]$ からの遷移は,次に行く都市 $j$ をすべて試して,$dp[ S \cup \{ j \} ][j]$ を $dp[S][i] + d( i, j )$ との $\min$ で更新します.最後に $dp[S][0]$ を読むと答えが求まっています.
配列添字としての集合をどう扱うかですが,集合はビット表現(=整数)としてエンコードできます.すなわち,
- $i$ 番目の要素が集合に入っている $\Leftrightarrow$ 整数の $i$ 番目のビットが立っている
というような整数で集合を表すことができ,配列の添字に使えます.
参考文献
[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).
コード
constexpr auto INF = LIM< LL >::max() / 2; int main() { IN( int, N ); VI X( N ), Y( N ), Z( N ); REP( i, N ) { cin >> X[i] >> Y[i] >> Z[i]; } static LL dp[ 1 << 17 ][ 32 ]; fill( AALL( dp ), INF ); dp[0][0] = 0; REP( s, 1 << N ) { REP( i, N ) { REP( j, N ) { const int d = abs( X[i] - X[j] ) + abs( Y[i] - Y[j] ) + max( 0, Z[j] - Z[i] ); chmin( dp[ s | 1 << j ][j], dp[s][i] + d ); } } } cout << dp[ ( 1 << N ) - 1 ][0] << endl; return 0; }