[PR]当サイトはアフィリエイト広告を利用しています。
はじめに
今回は代表的なアルゴリズムの解説です。
グラフ理論の中に点彩色問題というのがあります。
地図を隣り合う地域が同じ色にならないように塗分ける問題として解説されます。
今回は点彩色問題の応用で、時間割編成問題というのを扱います。
担当する先生たちが授業できる科目をグラフで表して、点彩色問題を解くことで、効率的な時間割を作成することができます。
今回は点彩色問題の時間割編成問題のプログラムとその解説をしていきます。
おそらくこのサイト訪れる方は、グラフ理論の例題をいくつか解いているのではないかと思います。
グラフ理論の教科書を開けば、点彩色問題の解説のところで時間割編成問題が出てきます。
しかしながら、点彩色問題をコンピューターで解く話になってくると、アルゴリズムの解説は見受けられるのですが、具体的なプログラムの解説があまり見つかりません。
そこで今回は点彩色問題を解く貪欲法の実装とその解説に焦点を当てていきます
今回の問題
次のような教員の担当があるとします。
教員1: 科目A, C
教員2: 科目A, B
教員3: 科目B
教員4: 科目C, D
この情報から、同じ時間に開講する科目をなるべくたくさん用意して、時間割を圧縮していきたいというのが今回の問題です。
と言ったものの、この情報からこれがグラフ理論の点彩色問題だ、と見抜ける人はあまりいないような気がします。
なので、重複するとまずい科目があるような時間割を作成するときは点彩色問題が適用できるくらいに覚えておけばよいと思います。
まずこの問題をグラフで表すと次のようになります。
このグラフの点彩色を求めると、効率的な時間割が求められます。
ちなみにグラフの作り方ですが、同じ教員が一度に複数の科目を開講することはできないので、例えば科目Aに着目すると、教員1の情報から、科目AとCは同時開講無理、教員2の情報から、科目AとBは同時開講無理となります。
なので、科目Aのノードと連結するのは科目CとBということになります。
点彩色問題を解くための貪欲法
今回は貪欲法を使ってこれを解いていきます。
点彩色問題を効率的に解く方法は見つかっていないようなので、絶対に最小の色数が求まるわけではありませんが、そこそこ解ける貪欲法で解きます。
貪欲法のアルゴリズムは次のようになります。
1. 頂点集合上の全順序を1つ固定する。
2. その頂点の隣接点の色と違い，既に使った色の中で最も小さな色で塗る。
3. 既に使った色で塗れない場合は，新しい色で塗る。
単純ですが、プログラムにすると結構面倒です。
実際のプログラム
graph = [[0,1,1,0],[1,0,0,0],[1,0,0,1],[0,0,1,0]]
color = [None,None,None,None]
color[0] = 0
path = [1,2,3]
for i in path:
tempColor1 = []
for j in range(len(color)):
if(graph[i][j] == 1):
if(color[j] != None):
if(color[j] not in tempColor1):
tempColor1.append(color[j])
tempColor2 = [0]
for j in range(1,len(color)):
if(color[j] != None):
if(color[j] not in tempColor2):
tempColor2.append(color[j])
colorActive = None
for j in range(len(tempColor2)):
if(tempColor2[j] not in tempColor1):
colorActive = j
color[i] = colorActive
break
if(colorActive is None):
color[i] = max(tempColor2) + 1
print(color)出力は
[0, 1, 1, 0]
となります。
これをグラフに書き込むと
このようになります。
1時間目にAとD、２時間目にBとCを開講すれば少ない時間ですべての授業を開講できるようです。
プログラムの解説
graph = [[0,1,1,0],[1,0,0,0],[1,0,0,1],[0,0,1,0]]
color = [None,None,None,None]
color[0] = 0
path = [1,2,3]graphにグラフの隣接行列を格納します。
例えばgraph[0][1]は科目Aと科目Bが隣接しているとなり、1となります。
colorは各科目A～Dまでの色を格納します。
最初に色をどこか決めないといけないので、最初の頂点Aの色を「色0」としています。
color[0] = 0
のところです。
pathはめぐる頂点の順番です。
今回は0→1→2→3の順番でアルゴリズムを適用していきます。つまりA,B,C,Dの順番で見ていくということです。
[3,1,2]
とやると
0→3→1→2の順番でアルゴリズムを適用していきます。
tempColor1 = []
for j in range(len(color)):
if(graph[i][j] == 1):
if(color[j] != None):
if(color[j] not in tempColor1):
tempColor1.append(color[j])このtempColor1というのが、今見ている頂点の隣接点の持つ色を格納するリストです。
隣接点は隣接行列で1となっている点なので
if(graph[i][j] == 1):
で見ます。
次の
if(color[j] != None):
の部分はcolorにNoneがあったらそれを無視するという条件です。
次の
if(color[j] not in tempColor1):
では、隣接点がこれまで格納されていない頂点だけ格納するという条件です。これがないとtempColor1に[0,0,0]
とかが入ってしまい0は一つでいいのに、よろしくない格納となってしまいます。
次の
tempColor1.append(color[j])
で隣接点の色を格納します。
tempColor2 = [0]
for j in range(1,len(color)):
if(color[j] != None):
if(color[j] not in tempColor2):
tempColor2.append(color[j])このtempColor2というのが、これまで見つかった色を格納するリストです。
colorをそのまま使えばよさそうですが、Noneの処理が面倒なので、都合の良いリストを作っています。
if(color[j] != None):
この部分で、Noneを除外しています。
次の
if(color[j] not in tempColor2):
で色が重複して格納される[0,0,0]みたいなものを[0]一つにする処理をしています。
colorActive = None
for j in range(len(tempColor2)):
if(tempColor2[j] not in tempColor1):
colorActive = j
color[i] = colorActive
break
if(colorActive is None):
color[i] = max(tempColor2) + 1この部分は面倒なのですが、解説していきます。
何をやっているかというとアルゴリズムの2と3の部分です。実際に色を塗るパートです。
colorActive = None
の部分は、見つけた都合の良い色を格納する変数です。
Noneだと見つからなかったという意味で使っていきます。
次の
for j in range(len(tempColor2)):
if(tempColor2[j] not in tempColor1):
colorActive = j
color[i] = colorActive
breakこの部分ですが
for j in range(len(tempColor2)):
の部分が、既に使った色の中で最も小さな色で塗るということをやっています。
今見つかっている色の中から小さい順に見ていきます。
次の
if(tempColor2[k] not in tempColor1):
この部分は小さい順から見ていく色が隣接点の中にないなら、それをその頂点の色で決定するということをやっています。
if(colorActive is None):
color[i] = max(tempColor2) + 1この部分ですが、
if(colorActive is None):
の部分は、上で求めた最小の色の判定にヒットしないとcolorActiveはNoneのままなので、既存の色は使えないということになります。
なので、新しい色で塗ります。
まとめ
今回は点彩色問題の時間割編成問題のプログラムとその解説をしました。
アルゴリズムは単純で、紙の上で書いていくとわかるのですが、プログラムにすると色々な例外を考えなければならず、結構面倒ですね。
今回の解説で、点彩色問題の中の時間割編成問題の具体的なプログラミングに関する理解が深まれば幸いです。
