ビットマスク動的計画法
出発都市を0に固定します。どの巡回路も開始位置を回転させれば、都市0から出発する形で表せます。状態(current, visited)のvisitedは、出発都市0を含む訪問済み都市のビットマスクです。dp[current][visited]は、未訪問の都市をそれぞれ一度ずつ訪問してから都市0に戻るための最小追加コストを表します。
すべての都市を訪問済みなら、残りのコストは現在の都市から0への辺のコストです。その向きの辺がなければ、この状態は実現できません。それ以外の場合は、未訪問都市nextのうちcurrent → nextの辺が存在するものだけを調べ、辺のコストと次の状態のコストの合計の最小値を選びます。
dp[current][visited] = min(cost[current][next] + dp[next][visited | (1 << next)])
最小値を取る対象は、実在する辺で移動できる次の都市だけです。入力コスト0は辺が存在しないことを示すため、その遷移はスキップします。巡回路を完成できない場合、BOJ 2098では0を出力します。内部では実現不可能な状態をINFで表し、他のコストに加算しません。
状態数はN · 2^Nで、各状態から最大N都市を調べるため、時間計算量はO(N² 2^N)、空間計算量はO(N 2^N)です。コストにはlong、INFにはLong.MAX_VALUE / 4を使い、有効な経路コストを加算してもオーバーフローしないようにします。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
private static final long INF = Long.MAX_VALUE / 4;
private static int n;
private static int[][] cost;
private static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(input.readLine().trim());
cost = new int[n][n];
for (int from = 0; from < n; from++) {
String[] row = input.readLine().trim().split("\\s+");
for (int to = 0; to < n; to++) {
cost[from][to] = Integer.parseInt(row[to]);
}
}
dp = new long[n][1 << n];
for (long[] row : dp) {
Arrays.fill(row, -1);
}
long answer = visit(0, 1);
System.out.println(answer == INF ? 0 : answer);
}
private static long visit(int current, int visited) {
if (visited == (1 << n) - 1) {
return cost[current][0] == 0 ? INF : cost[current][0];
}
if (dp[current][visited] != -1) {
return dp[current][visited];
}
long best = INF;
for (int next = 0; next < n; next++) {
int bit = 1 << next;
if ((visited & bit) != 0 || cost[current][next] == 0) {
continue;
}
long remaining = visit(next, visited | bit);
if (remaining != INF) {
best = Math.min(best, cost[current][next] + remaining);
}
}
return dp[current][visited] = best;
}
}