アルゴリズムc 第11回

都市の間に道路をつくる問題

都市がいくつか点在しており、全ての都市が連結されるように 道路を作ろうと思います。 道路の候補路線はいくつもありますが、それぞれの道路を作るには コストが発生します。最小の予算で全ての都市を連結するには 候補の中からどの道路を作ればよいでしょうか？

入力形式

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

最初の行には２個の整数 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)。

出力

全ての都市をつなぐように道路をつくる場合の最小コストを出力しなさい。 もしも全ての都市をつなぐことができない場合は -1 と出力すること。

Minimum Spanning Tree(最小連結木)の問題

ノードの集合 V 、エッジの集合 E から構成される グラフ G を考えます。 このようなグラフを G =( V , E ) と書きます。

図1:グラフの例

それぞれのエッジには重み d が付けられていて、 重み d は正の実数であるとします。 これを d : E → R₊と書きます。

「実数」は英語でReal Number または Rational Numberなので R で表します (。ちなみに虚数は Imaginary Number です)。 実数のうちで正の範囲なので+を右下につけてR₊と書きます。

「 V の要素が全て連結されるように E の部分集合を選んだとき、 選ばれたエッジの合計の重みを最小にする」問題は Minimum Spanning Treeの問題と呼ばれていて、これを数学風に書くと

連結グラフ G =( V , E )と 重み d : E → R₊ が与えられたとき、 最小木を求めよ。

ちなみに、上の「都市の間に道路を作る」問題で、「最小コストで」 という条件なので重みは「道路を作る場合の金額」になります。 もしも、「最短経路経路で」という条件であれば重みは「道路の長さ」 になります。

Minimum Spanning Treeの問題を解くには、単純に考えると、 全てのエッジについて「選ぶ」か「選ばない」という選択肢を 考えることになりますので、2^{エッジの数}の計算量 が必要です。

Minimum Spanning Treeを高速に解く方法として、Primの方法と Kruskalの方法があります。

Primの方法

1. 全てのノードを「連結木に加わっていない」状態とする。
2. 適当なノードを1個選び「連結木に加える」。
3. 全てのノードが「連結木に加えられる」まで以下のステップ4,5を繰り返す。
4. 「連結木内のノード」から「連結木外のノード」へのエッジの中で、 重みが最小のエッジを選ぶ。 最小のものが複数あった場合は、そのうちのどれを選んでもよい。
5. 選ばれたエッジがつながるノードを「連結木に加える」。

この方法でうまく行くという証明は、授業で解説します。

「『連結木内のノード』から『連結木外のノード』へのエッジの中で重みが最小のエッジ」の候補が複数ある場合、 解が複数存在する場合があるので注意が必要です。

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

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

% javac RunMSTPrim.java MSTPrim.java
% java RunMSTPrim < mstdata01.txt
#edge:[0,3,10] #edge:[0,2,15] #edge:[1,3,25] #edge:[2,5,20] #edge:[4,6,20]
 #edge:[5,6,30] 
120
% java RunMSTPrim < mstdata02.txt
#edge:[0,1,15] #edge:[0,4,1] #edge:[0,5,44] #edge:[2,6,43] #edge:[3,4,25]
 #edge:[3,7,21] #edge:[5,6,31] #edge:[7,10,7] #edge:[8,9,7] #edge:[8,11,11]
 #edge:[10,12,28] #edge:[10,14,11] #edge:[11,13,1] #edge:[13,14,8]
 #edge:[14,15,16] #edge:[15,16,51] #edge:[16,18,31] #edge:[16,19,72]
 #edge:[17,18,6] 
429

Kruskalの方法

1. graph内の node全てについて、それぞれ自分自身をrootとするtreeに属させる。
2. $S$ をグラフの全てのedgeを含む集合とする
3. 以下、$S$が空になるまで3, 4 の手順を繰り返す。
4. $S$から weight (重み) が最小の edge を取り除く。
5. 取り除いた edge が二つの異なるtreeを連結するものならば、2つのtreeをひとつにまとめる

一般に、Kruskal の方法が Prim の方法よりも高速に動作します。 edgeをどんどん減らしながら、2つの tree をマージする操作を行うだけでよいからです。 2つのtreeが別のtreeであることを確認したり、一つにまとめたりする操作は Union Find アルゴリズムで高速に実行できます。

アルゴリズムc 演習

作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoC/local/handin/ で必ず確認しておいて下さい。

〆切は次週の金曜日13:00です。

課題11a

MSTPrim.javaを完成させて下さい。

入力データのURLは http://ynitta.com/class/algoC/mstdata04.txt と http://ynitta.com/class/algoC/mstdata05.txt です。前者は 7XX, 後者は9XXが答になるはずです (Xの部分は伏せ字です)。

課題11b

Kruskal.javaを完成させて下さい。