はじめに
欲張り法の続きです。今回はグラフ関連のアルゴリズムを紹介します。それから、ナップザック問題を例題に 動的計画法 を説明します。
●コスト最小のグラフ
今回は閉路が存在しない無向グラフを考えてみましょう。次の図を見てください。
無向グラフの場合、頂点を自分自身と連結するような長さ 3 以上の経路を「閉路」といいます。上図 (1) では、A - B - C - A と B - C - D - B と A - B - C - D - A という 3 つの閉路が存在します。A - C - A のような経路は閉路として考えません。これに対して、(2) では閉路は存在しません。
いま、n 個の頂点を全てつなぐようなグラフを考えると、最低 n - 1 本の辺が必要になります。最小の辺の本数で全ての頂点を接続したグラフを「展張木 (spanning tree)」と呼ぶます。(2) も展張木となっていますが、6 個の頂点を全てつなげばいいので、このほかにも展張木となる接続パターンが多数存在します。このとき、辺に重みを与えて、その合計が最小となる展張木を MST (Minimum Spanning tree) といいます。
簡単な例を示しましょう。次の図を見てください。
上の経路図は、各地点をケーブルでつなぐ場合にかかるコストを表しています。各地点をケーブルでつなぐ場合、7 個の頂点を全てつなげばいいので、展張木として考えることができます。
たとえば、上図に示すような展張木を考えることができます。この場合、最も安いコストでケーブルを接続する経路は MST で表すことができます。上の 2 つの例は MST ではありません。
MST を求める方法では「プリム (R. C. Prim) のアルゴリズム」と「クラスカル (J. B. Kruskal) のアルゴリズム」の 2 つが有名です。この 2 つは、「欲張り法」に基づいたアルゴリズムです。最初に、プリムのアルゴリズムから説明しましょう。
●プリムのアルゴリズム
基本的な考え方は、MST に属する頂点とそうでないものとに分け、まだ MST に属していない頂点から、最もコストの安く済む頂点を付け加えていく、という欲張り法になります。最初に選ぶ頂点はどれでもかまいません。どの頂点でも最後は MST に属するで、どの頂点からスタートしても大丈夫です。
問題は最小のコストになる頂点の選び方です。MST に属する頂点が複数あり、まだ選んでいない頂点も複数ある場合、その中から最小コストの辺を選ばなくてはいけません。このあたりの工夫が、このアルゴリズムを実装する上でのポイントになります。
それでは、具体的にプログラミングしていきましょう。グラフは隣接行列を使って表すことにします。
リスト : 隣接行列
weight = [
[INF, 8, 5, 1, INF, INF, INF],
[ 8, INF, INF, 6, 2, INF, INF],
[ 5, INF, INF, 6, INF, 4, INF],
[ 1, 6, 6, INF, 4, 3, 5],
[INF, 2, INF, 4, INF, INF, 3],
[INF, INF, 4, 3, INF, INF, 7],
[INF, INF, INF, 5, 3, 7, INF]
]
INF はつながっていないことを示すグローバル変数で、値は MAX_VALUE - 1 (0xffffff) としました。あとは各辺の重みを設定するだけです。
次に、グローバル変数を定義します。
リスト : グローバル変数の定義 # 定数 MAX_VALUE = 0x1000000 INF = MAX_VALUE - 1 MAX_SIZE = 7 # グローバル変数 closest = [0] * MAX_SIZE low_cost = [0] * MAX_SIZE
プリムのアルゴリズムの場合、まだ MST に属していない頂点の中から、最小コストの辺とつながっている頂点を選択しなくてはなりません。それを管理するために、その頂点につながっている辺の中で最小コストを変数 low_cost に格納し、対応する頂点を変数 closest に格納します。頂点を選択するたびに、この 2 つのグローバル変数を更新していくことで、プリムのアルゴリズムは動作します。
それでは、本題である探索アルゴリズムを見ていきましょう。
リスト : 探索（プリムのアルゴリズム）
def search():
# 初期化
for i in range(MAX_SIZE):
low_cost[i] = weight[0][i]
# 頂点の選択
for i in range(1, MAX_SIZE):
min = low_cost[1]
k = 1
for j in range(2, MAX_SIZE):
if min > low_cost[j]:
min = low_cost[j]
k = j
print('{:c} - {:c}'.format(k + ord('A'), closest[k] + ord('A')))
low_cost[k] = MAX_VALUE
for j in range(1, MAX_SIZE):
if low_cost[j] < MAX_VALUE and low_cost[j] > weight[k][j]:
low_cost[j] = weight[k][j]
closest[j] = k
最初に、グローバル変数 low_cost を初期化します。頂点 A からスタートするので、low_cost には A と各頂点を結ぶ辺の重みをセットします。closest には接続されている頂点をセットしますが、最初は頂点 A を対象とするので 0 に初期化しておきます。
次の for ループで頂点を一つずつ選択していきます。その次の for ループで、low_cost の中から最小コストの辺とつながっている頂点を選びます。変数 k に選択した頂点をセットし、変数 min にそのコストをセットします。頂点 A からスタートするので、最初に B の値を k と min にセットして、C から G までの値と比較します。
最小コストの頂点を見つけたら、それと対応する頂点 colsest[k] をいっしょに表示します。そして、low_cost[k] に MAX_VALUE をセットして、頂点 k が選択されて MST に属したことを表します。
最後の for ループで low_cost と closest を更新します。今、頂点 k が MST に加えられたので、その頂点とほかの頂点の接続を調べて low_cost の値を更新します。まず、調べる頂点が MST に属していないことを確認します。それから、重み weight[k][j] と最小コスト low_cost[j] を比較して、重みの方が小さければ low_cost[j] と closest[j] の値を更新します。これで low_cost には常に最小コストが格納されていることになります。
●実行結果
実際に実行してみると、結果は次のようになりました。
この場合、総コストは 13 になります。プリムのアルゴリズムは、頂点の個数を N とすると N - 1 回のループの中に N - 1 回のループがあるので、実行時間は N の 2 乗に比例します。したがって N が大きくなると、このアルゴリズムでは効率が不十分になります。そのような場合、次に説明するクラスカルのアルゴリズムを使った方がよいでしょう。クラスカルのアルゴリズムは、辺の本数を M とすると実行時間は M * log2 M に比例します。
●クラスカルのアルゴリズム
次はクラスカルのアルゴリズムを説明します。基本的な考え方は、辺が一本もない状態から始めて、一本ずつ辺を追加していくことで MST を構成します。このとき、重みの小さい辺から加えていく「欲張り法」を使うのですが、単純に辺を追加していくだけでは、途中で閉路ができてしまって展張木の条件を満たさなくなる可能性があります。そこで、「MST にならないような辺は追加しない」という条件を付け加えます。
具体的には、次のように考えます。
たとえば、上図 (1) のように辺 A - B を選んだとします。これを一つのグループとして管理します。このとき、各頂点に自分の属するグループ番号をつけておきます。最初は頂点に別々の番号をつけておき、辺を選んだときに両端のグループ番号をチェックします。違う番号であれば、その辺を選択して頂点のグループ番号を統一します。同じグループ番号ならば、閉路を形成するので、その辺は選択しません。
たとえば、(2) の場合では AB と D は違うグループなので、辺 B - D を追加できます。そして、D を AB と同じグループ番号に統一します。次に、(3) のように辺 A - D を追加しようとした場合、A と D は同じグループ番号だから、この辺を追加することはできないことがわかります。
(4) のように、まず辺 A - B を選択し、次に辺 C - D を選択した場合は、AB と CD は違うグループ番号になります。したがって、(5) のように B と D では番号が違うので、辺 B - D を選択することができます。そして、頂点の個数 n に対して n - 1 本の辺を選択した時点で、MST の作成は終了です。
●プログラムのポイント
それでは、クラスカルのアルゴリズムを実装してみましょう。このアルゴリズムでは、重みが最小である辺を探す処理で、MST に属していない辺を線形探索するようでは、その真価を発揮することはできません。ここは、最小の重みを持つ辺を、簡単に取り出せるようなデータ構造を採用すべきでしょう。この条件にぴったりのデータ構造が「ヒープ」です。ヒープについては拙作のページ 二分木とヒープ をお読みください。
それから、もう一つ考えておかなくてはならない問題があります。それは、二つのグループを一つにまとめる併合（マージ）処理です。いちばん簡単な方法は、次のようにプログラムできます。
リスト : グループの併合 (力任せバージョン)
def merge(g1, g2):
for i in range(NODE_SIZE):
if group[i] == g2: group[i] = g1
配列 group に各頂点のグループ番号を格納します。グループ g1 と g2 を併合する場合、g2 に属する頂点を全て g1 に書き換えるだけです。この方法はとても簡単ですが、頂点の個数が多くなると効率が悪くなるのが欠点です。
そこで、今回はグループを Python の set で表すことにしましょう。set のメソッド update() を使うと、グループを簡単に併合することができます。ただし、このままでは頂点からグループ番号を簡単に求めることができません。たとえば、頂点 3 のグループ番号を調べるには、グループ番号 0 から順番に set の要素をチェックする必要があります。
この欠点を補うため配列 group を用意し、そこに頂点のグループ番号を格納することにします。グループを一つに併合するときに group を書き換えておけば、頂点が属するグループ番号を group から直ぐに求めることができます。
●プログラムの作成
それでは、プログラムを作りましょう。辺の重みを基準にヒープを作成するので、隣接行列を使わずに、ずばり「辺」そのものをデータ構造として定義します。
リスト : 辺の定義
class Edge:
def __init__(self, p1, p2, weight):
self.p1 = p1
self.p2 = p2
self.weight = weight
def __gt__(x, y): return x.weight > y.weight
def __le__(x, y): return x.weight <= y.weight
クラス名は Edge としました。インスタンス変数 p1 と p2 は両端の頂点を格納します。変数 weight は、その辺の重みを格納します。それから、Edge に特殊メソッド __gt__() と __le__() を定義します。これで 二分木とヒープ で作成したプライオリティキュー (PQueue) をそのまま利用することができます。
次は辺のデータを定義します。
リスト : 辺のデータ (p1, p2, weight)
edge_data = [
(0, 1, 8), (0, 2, 5), (0, 3, 1),
(1, 3, 6), (1, 4, 2), (2, 3, 6),
(2, 5, 4), (3, 4, 4), (3, 5, 3),
(3, 6, 5), (4, 6, 3), (5, 6, 7)
]
タプルの要素 (p1, p2, weight) は Edge のインスタンス変数 p1, p2, weight と同じで、両端の頂点と重みを表しています。
次はグループ用のグローバル変数を定義します。
リスト : グループ用グローバル変数
group = list(range(NODE_SIZE))
group_set = [{x} for x in range(NODE_SIZE)]
group は各頂点のグループ番号を格納します。最初は、全て異なる番号を割り当てておきます。ここでは、自分自身の番号で初期化しています。処理が進むとグループ番号は書き換えられていき、最後には一つのグループ番号に統合されます。group_set はグループを表す set を格納します。最初は頂点番号とグループ番号が一致するので、set は頂点番号で初期化します。
次は Edge のオブジェクトを生成してプライオリティキューを初期化する関数 make_edge() を作ります。
リスト : Edge のオブジェクトを生成
def make_edge():
global edges
edges = PQueue()
for p1, p2, w in edge_data:
edges.push(Edge(p1, p2, w))
グローバル変数 edge_data から Edge のオブジェクトを生成して、プライオリティキュー (ヒープ) に追加します。プライオリティキューはグローバル変数 edges にセットします。あとは、Edge(p1, p2, w) で Edge のオブジェクトを生成して、プライオリティキューのメソッド push() で追加します。これで edges には重みを基準にしたヒープが構成されます。
それでは、探索本体を行う関数 search() を作りましょう。
リスト : クラスカルのアルゴリズムによる探索
def search():
i = 0
while i < NODE_SIZE - 1:
e = edges.pop()
if group[e.p1] != group[e.p2]:
merge(e.p1, e.p2)
print('{:c} - {:c}'.format(e.p1 + ord('A'), e.p2 + ord('A')))
i += 1
while ループで辺を一つずつ選択していきます。変数 i は選択した辺の個数を管理し、i が NODE_SIZE - 1 になったら while ループを終了します。まず、edges から最小の重みを持つ辺をメソッド pop() で取り出して変数 e にセットします。それから、両端のグループ番号をチェックします。違う番号であれば、その辺を選択することができます。関数 merge を呼び出してグループ番号を一つにまとめます。そのあと、選択した辺を print() で表示し、変数 i の値を一つ増やします。PQueue を使っているので、プログラムはとても簡単になりました。
次は、グループの併合を行う関数 merge() を作ります。
リスト : グループを併合する
def merge(node1, node2):
gs1 = group_set[group[node1]]
gs2 = group_set[group[node2]]
if len(gs1) <= len(gs2):
gs1.update(gs2)
gs3 = gs2
g = group[node1]
else:
gs2.update(gs1)
gs3 = gs1
g = group[node2]
for x in gs3:
group[x] = g
gs3.clear()
頂点 node1 が属するグループを gs1 に、頂点 node2 が属するグループを gs2 にセットします。そして、個数の少ないグループを多いほうに併合します。これは set のメソッド update を使うと簡単です。個数の少ないグループを gs3 に、多いグループの番号を g にセットします。最後に、gs3 のグループ番号を g に書き換えて、gs3 をメソッド clear で空にします。
最後に、make_edge() でデータを作成してから search() を呼び出します。
●実行結果
実行結果は次のようになりました。
プリムのアルゴリズムと違い、辺を追加して一つのグループにまとめていく様子がよくわかると思います。
●アルゴリズムの証明
それでは、プリムとクラスカルのアルゴリズムを証明してみましょう。これらのアルゴリズムでは、展張木が作られるのは自明なので、これが MST になることを示します。
頂点を 2 つの集合 U と V に分けます。この 2 つの集合を連結する辺 e は、展張木の特性から 1 本しかありません。もし、辺 e が MST に属するのならば、その重みは U と V を接続する辺の中で、最小でなければなりません。
この証明は簡単です。辺 f を含む MST が存在すると仮定します。辺 f の重みが辺 e よりも大きいのであれば、その重みの総和は辺 e を含む MST よりも大きくなるので、仮定に反することになります。つまり、2 つのグループを連結する辺の中で、最小の重みを持つ辺を使って展張木を構成すれば、それは MST になるのです。
プリムのアルゴリズムの場合、MST に属する頂点とそうでない頂点に分けて、その中で最小の重みを持つ辺を選択しているので、構成された展張木は MST になります。クラスカルのアルゴリズムでは 2 つの違うグループ同士を統合するときに、最小の重みを持つ辺を使って連結しているので、これも MST となるのです。
●補足
クラスカルのアルゴリズムは Union-Find というデータ構造を使うともっと簡単に実装することができます。Union-Find の詳しい説明は拙作のページ Union-Find をお読みください。
プログラムは次のようになります。
リスト : クラスカルのアルゴリズムによる探索
def search():
i = 0
u = UnionFind(NODE_SIZE)
while i < NODE_SIZE - 1:
e = edges.pop()
if u.find(e.p1) != u.find(e.p2):
u.union(e.p1, e.p2)
print('{:c} - {:c}'.format(e.p1 + ord('A'), e.p2 + ord('A')))
i += 1
最初に UnionFind で NODE_SIZE 個の集合を生成します。メソッド find() は集合を表す値を返します。返り値が同じ値であれば、e.p1 と e.p2 は同じ集合に属していることがわかります。そうでなければ、メソッド union() で e.p1 と e.p2 を併合します。Union-Find は find() と union() の処理を高速に行うことができるデータ構造なので、今回作成した merge() よりも効率的に処理することができます。
●プログラムリスト１
#
# prim.py : プリムのアルゴリズム
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
# 定数
MAX_VALUE = 0x1000000
INF = MAX_VALUE - 1
MAX_SIZE = 7
# グローバル変数
closest = [0] * MAX_SIZE
low_cost = [0] * MAX_SIZE
# 隣接行列
weight = [
[INF, 8, 5, 1, INF, INF, INF],
[ 8, INF, INF, 6, 2, INF, INF],
[ 5, INF, INF, 6, INF, 4, INF],
[ 1, 6, 6, INF, 4, 3, 5],
[INF, 2, INF, 4, INF, INF, 3],
[INF, INF, 4, 3, INF, INF, 7],
[INF, INF, INF, 5, 3, 7, INF]
]
# 探索
def search():
# 初期化
for i in range(MAX_SIZE):
low_cost[i] = weight[0][i]
# 頂点の選択
for i in range(1, MAX_SIZE):
min = low_cost[1]
k = 1
for j in range(2, MAX_SIZE):
if min > low_cost[j]:
min = low_cost[j]
k = j
print('{:c} - {:c}'.format(k + ord('A'), closest[k] + ord('A')))
low_cost[k] = MAX_VALUE
for j in range(1, MAX_SIZE):
if low_cost[j] < MAX_VALUE and low_cost[j] > weight[k][j]:
low_cost[j] = weight[k][j]
closest[j] = k
# 実行
search()
●プログラムリスト２
#
# krus.py : クラスカルのアルゴリズム
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from pqueue import *
# 定数
NODE_SIZE = 7
EDGE_SIZE = 12
# 辺のデータ (p1, p2, weight)
edge_data = [
(0, 1, 8), (0, 2, 5), (0, 3, 1),
(1, 3, 6), (1, 4, 2), (2, 3, 6),
(2, 5, 4), (3, 4, 4), (3, 5, 3),
(3, 6, 5), (4, 6, 3), (5, 6, 7)
]
# グループ用変数
group = list(range(NODE_SIZE))
group_set = [{x} for x in range(NODE_SIZE)]
# 辺の定義
class Edge:
def __init__(self, p1, p2, weight):
self.p1 = p1
self.p2 = p2
self.weight = weight
def __gt__(x, y): return x.weight > y.weight
def __le__(x, y): return x.weight <= y.weight
# 辺のデータを作成
def make_edge():
global edges
edges = PQueue()
for p1, p2, w in edge_data:
e = Edge(p1, p2, w)
edges.push(e)
# 併合
def merge(node1, node2):
gs1 = group_set[group[node1]]
gs2 = group_set[group[node2]]
if len(gs1) <= len(gs2):
gs1.update(gs2)
gs3 = gs2
g = group[node1]
else:
gs2.update(gs1)
gs3 = gs1
g = group[node2]
for x in gs3:
group[x] = g
gs3.clear()
# 探索
def search():
i = 0
while i < NODE_SIZE - 1:
e = edges.pop()
if group[e.p1] != group[e.p2]:
merge(e.p1, e.p2)
print('{:c} - {:c}'.format(e.p1 + ord('A'), e.p2 + ord('A')))
i += 1
# 実行
make_edge()
search()
●プログラムリスト３
#
# krus.py : クラスカルのアルゴリズム (Union-Find 版)
#
# Copyright (C) 2012-2022 Makoto Hiroi
#
from pqueue import *
from unionfind import *
# 定数
NODE_SIZE = 7
EDGE_SIZE = 12
# 辺のデータ (p1, p2, weight)
edge_data = [
(0, 1, 8), (0, 2, 5), (0, 3, 1),
(1, 3, 6), (1, 4, 2), (2, 3, 6),
(2, 5, 4), (3, 4, 4), (3, 5, 3),
(3, 6, 5), (4, 6, 3), (5, 6, 7)
]
# 辺の定義
class Edge:
def __init__(self, p1, p2, weight):
self.p1 = p1
self.p2 = p2
self.weight = weight
def __gt__(x, y): return x.weight > y.weight
def __le__(x, y): return x.weight <= y.weight
# 辺のデータを作成
def make_edge():
global edges
edges = PQueue()
for p1, p2, w in edge_data:
e = Edge(p1, p2, w)
edges.push(e)
# 探索
def search():
i = 0
u = UnionFind(NODE_SIZE)
while i < NODE_SIZE - 1:
e = edges.pop()
if u.find(e.p1) != u.find(e.p2):
u.union(e.p1, e.p2)
print('{:c} - {:c}'.format(e.p1 + ord('A'), e.p2 + ord('A')))
i += 1
# 実行
make_edge()
search()
