公式

E - Traveling Salesman among Aerial Cities 解説 by kyopro_friends


都市間の移動のコストについて三角不等式が成り立つので、ある都市から次の都市に移動するとき、別の都市を経由する必要はありません。よって各都市をちょうど1度ずつ訪問する場合についてのみ考えればよいです。

全ての訪問順を探索する場合 \(O(N!*N)\) 程度の時間が掛かるため、今回の制約では時間内に答えを得ることはできません。 次のようなDPにより解くことが出来ます。

\(DP[i][S]=\)現在地が都市 \(i\) で、訪問済みの街の集合が \(S\) であるときのコストの最小値

\(DP[i][S]=\min\{DP[j][S\setminus \{i\}]+dist(i,j) \mid j\in S\setminus\{i\}\}\)

ここで、集合 \(S\) を直接キーとして持ってもよいですが、例えば集合 \(\{0,3,5\}\)\(2^0+2^3+2^5=41\) のように2進数に対応させることで整数として扱うことができます。そのためこのようなDPは俗にbitDPとも呼ばれます。

この対応により得られた整数を \(f(S)\) とすると、 - \(i\in S \Longleftrightarrow\) \(f(S)\) のbit \(i\)\(1\) - \(T \subset S \Longleftrightarrow (f(T) \text{ bitwiseor } f(S))=f(S) \Longrightarrow f(T) \leq f(S)\)

などが成り立ち、集合に関する操作・性質をbit演算で簡潔に表現することができます。

投稿日時:
最終更新: