都市がいくつか点在しており、全ての都市が連結されるように 道路を作ろうと思います。 道路の候補路線はいくつもありますが、それぞれの道路を作るには コストが発生します。最小の予算で全ての都市を連結するには 候補の中からどの道路を作ればよいでしょうか?
N R A1 B1 L1 A2 B2 L2 ... AR BR LR
最初の行には2個の整数 N と R が含まれる。 N は都市の数(ただし1≦N≦100)を表し、 Rはそれらの都市をつなぐ道の個数を表す。
2行目以降はR行に渡って、3個の整数 Ai, Bi, Li が含まれる(1≦i≦R)。 Ai と Biは道の両端の都市を表し (0≦Ai≦N-1, 0≦Bi≦N-1)、 Liは道路を作るためのコストを表す(1≦Si≦1000)。
全ての都市をつなぐように道路をつくる場合の最小コストを出力しなさい。 もしも全ての都市をつなぐことができない場合は -1 と出力すること。
ノードの集合 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の方法があります。
この方法でうまく行くという証明は、授業で解説します。
「『連結木内のノード』から『連結木外のノード』へのエッジの中で重みが最小のエッジ」の候補が複数ある場合、 解が複数存在する場合があるので注意が必要です。
mstdata01.txt | mstdata02.txt | |||
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 |
RunMSTPrim.javaの実行例 |
|
一般に、Kruskal の方法が Prim の方法よりも高速に動作します。 edgeをどんどん減らしながら、2つの tree をマージする操作を行うだけでよいからです。 2つのtreeが別のtreeであることを確認したり、一つにまとめたりする操作は Union Find アルゴリズムで高速に実行できます。
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。
提出した後は、正しく提出されていることを http://ynitta.com/class/algoC/local/handin/ で必ず確認しておいて下さい。
〆切は次週の金曜日13:00です。
提出ファイル | MSTPrim.java |
---|---|
コメント欄: | mstdata04.txt と mstdata05.txt を入力としたときのRunMSTPrim.javaの出力(最小の合計値のみで構わない) |
提出先: | 「宿題提出Web:アルゴリズムB:課題11a」 http://ynitta.com/class/algoC/local/handin/up.php?id=2013/algoC/kadai11a |
MSTPrim.javaを完成させて下さい。
入力データのURLは http://ynitta.com/class/algoC/mstdata04.txt と http://ynitta.com/class/algoC/mstdata05.txt です。前者は 7XX, 後者は9XXが答になるはずです (Xの部分は伏せ字です)。
提出ファイル | Kruskal.java |
---|---|
コメント欄: | mstdata04.txt と mstdata05.txt を入力としたときのRunKruskal.javaの出力(最小の合計値のみで構わない) |
提出先: | 「宿題提出Web:アルゴリズムB:課題11b」 http://ynitta.com/class/algoC/local/handin/up.php?id=2013/algoC/kadai11b |
Kruskal.javaを完成させて下さい。