アルゴリズムc 第2回

バックトラック

次の「例題：最短経路を求める」をどのように解いたらよいか考えましょう。 (注意)次回授業でこの問題を「ダイクストラ法」で解きますが、 その準備として、今回はバックトラック法や分岐限定法で解いてみましょう。

例題: 最短経路を求める

いくつかの都市と、それらの都市をつなぐ道路の距離が与えられている。 出発地点と目的地点が与えられたとき、最短経路を探すプログラムを 作りなさい。

入力形式

N R
A1 B1 L1
A2 B2 L2
...
AR BR LR
S D

最初の行には２個の整数 N と R が含まれる。 N は都市の数(ただし1≦N≦100)を表し、 Rはそれらの都市をつなぐ道の個数を表す。

２行目以降はR行に渡って、３個の整数 A_i, B_i, L_i が含まれる(1≦i≦R)。 A_i と B_iは道の両端の都市を表し (0≦A_i≦N-1, 0≦B_i≦N-1)、 L_iは道の距離を表す(1≦S_i≦1000)。

その次の行に２個の整数 S, D が含まれる。 S は出発地点の都市を表し、Dは目的地点の都市を表す (0≦S≦N-1, 0≦D≦N-1)。

出力

答が発見された場合は次のように出力しなさい。

最初の行に「最短経路の距離」を表す整数を出力し、 次の行に「 最短経路を辿ったときの都市を、出発地点から 目的地点まで順にスペースを１個ずつあけて」出力しなさい。

最短経路が複数ある場合は、そのうちの１つの経路を答えとすればよい ものとする。

答が無い場合は、"No route"と出力しなさい。

解答例1:単なるバックトラックで解く

出発地点から、順番に隣の都市に移動するプログラムを作成すると 次のようになります。 一度訪れた都市は二度と訪れないように、訪れた都市をmemoに記録しています。

% javac RunFindRoute.java
% java RunFindRoute <routedata01.txt
45:{0 3 6}

7 10
0 1 30
0 3 10
0 2 15
1 3 25
1 4 60
2 3 40
2 5 20
3 6 35
4 6 20
5 6 30
0 6

% javac RunFindRoute.java
% java RunFindRoute <routedata02.txt
204:{0 4 3 7 10 14 15 16 19}

20 61
0 1 15
0 2 58
0 3 79
0 4 1
0 5 44
0 6 78
1 2 61
1 3 90
1 4 95

1 5 53
1 6 78
2 3 49
2 4 72
2 5 50
2 6 43
3 4 25
3 5 100
3 6 51
3 7 21

4 5 70
4 6 59
5 6 31
6 7 71
7 8 55
7 9 46
7 10 7
7 11 81
7 12 92
7 13 71

7 14 48
8 9 7
8 10 18
8 11 11
8 12 36
8 13 38
8 14 54
9 10 85
9 11 84
9 12 36

9 13 57
9 14 85
10 11 45
10 12 28
10 13 93
10 14 11
11 12 92
11 13 1
11 14 29
11 15 41

12 13 45
12 14 53
13 14 8
14 15 16
15 16 51
15 17 95
15 18 94
16 17 64
16 18 31
16 19 72

17 18 6
18 19 91
0 19

分岐限定法(branch and bound)

全ての組み合わせについて探索するのは非常に多くの計算量を 必要とし、現実には計算が不可能な場合が多いので、 「明らかに不必要な組み合わせについては途中で計算を止める (=場合分けを省略する、枝刈りをする)」 ことをします。 このような方法を「分岐限定法(branch and bound)」といいます。

「不必要な組み合わせ」を判定するには、

• 緩和問題(条件の一部を緩めた問題)を解いてみる
• すでに見つかった解と途中結果を比べる

下の例では 「探策中に、すでに見付かった解よりも悪い解になる枝を調べずに すます（枝刈りする）」だけをしています。

% javac RunFindRouteBB.java
% java RunFindRouteBB <routedata01.txt
45:{0 3 6}

% javac RunFindRouteBB.java
% java RunFindRouteBB <routedata02.txt
204:{0 4 3 7 10 14 15 16 19}

枝刈りをすると、実用的な時間で答えが得られているのがわかります。 ただし、最悪の場合は（答えが長い順に得られたとき）、 全解探策と同じだけの時間がかかってしまうことには注意が必要です。

アルゴリズムc 演習

作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。 提出した後は、正しく提出されていることを http://ynitta.com/class/algoC/local/handin/ で必ず確認しておいて下さい。 提出〆切は次回の講義の開始時刻です。

課題2a

FindRoute.java を変更して、「FindRouteクラス中の5引数のsolveメソッドが 何回呼び出されたか」を結果の表示のときに表示するように変更して下さい。

routedata02.txt を http://ynitta.com/class/algoC/routedata02.txt からダウンロードして下さい。 routedata02.txtを入力としたとき、5引数のsolveは何回呼び出されるでしょうか？ その回数を答えて下さい。 (正解は7XXXXXXXになるはずです。Xの部分の数字は自分で調べて下さい。)

課題2b

FindRouteBB.java を変更して、「FindRouteBBクラス中の5引数のsolveメソッドが 何回呼び出されたか」を結果の表示のときに表示するように変更して下さい。

routedata02.txtを入力としたとき、5引数のsolveは何回呼び出されるでしょうか？ その回数を答えて下さい。 (正解は6XXXXになるはずです。Xの部分の数字は自分で調べて下さい。)

課題2c

以下の問題を解く分岐限定法のプログラムを作成しなさい。 ただし、計算センターのiMacでdpsum02.txtの処理が2分以内に終わる プログラムであること。

(注意)課題7bで動的計画法(Dynamic Programming)で解くべき問題として 同じ問題が出題されます。 「どれだけ高速化されるか、まず課題2cで分岐限定法で解いておこう」 というのが出題の趣旨です。

棒が何本か与えられた時、その棒の中からいくつかを選んで継ぎ足して (継ぎ足しに必要な長さは0とする)「指定された長さ」ちょうどにする問題を 考えよう。 あなたの仕事は、この問題を解いて何本の棒で「指定された長さ」にできるかを 答えるプログラムを書くことである。 答が何通りかある場合は、そのうちの最小の本数を答えること。 もし、与えられた棒を使って「指定された長さ」ちょうどにできない場合は -1と答えなさい。

入力形式

入力データは複数のデータセットから成る。 データセットの終わりは2つの 0 で表される。

Dataset1
Dataset2
...
Dataset2
0 0

各データセットは次のような正の整数から成る。

M  N
D1  D2 ... DN

Mは「指定された長さ」である(1≦M≦10000)。 Nは棒の総数(1≦N≦1000)で、 D_i は各棒の長さを表す(1≦D_i≦1000)。

出力形式

各データセットに対して、答えとなる整数1個を含んだ1行を 出力すること。

44 10
3 5 7 9 11 13 17 19 23 29
441 10
13 26 38 39 52 65 78 91 104 117
3989 21
19 38 57 76 95 114 133 152 171 190 209 228 247 260 266 285 304 323 342 361 380
0 0

4
6
-1

3950 30
11 17 29 51 58 68 85 102 119 136 
153 170 187 204 221 238 255 272 289 306 
323 357 374 391 408 425 442 459 476 493
3951 30
11 17 29 51 58 68 85 102 119 136 
153 170 187 204 221 238 255 272 289 306 
323 357 374 391 408 425 442 459 476 493
3952 30
11 17 29 51 58 68 85 102 119 136 
153 170 187 204 221 238 255 272 289 306 
323 357 374 391 408 425 442 459 476 493
1200 33
3 5 7 8 13 15 16 17 19 20 21 23 
25 26 27 30 31 33 35 37 40 41 49 
50 61 64 67 70 71 73 76 77 78
66 33
15 19 23 27 30 33 37 40 41 49 
50 55 61 64 67 70 71 73 76 77 78
83 85 87 88 93 95 97
120 131 135 140 146 
0 0