監xGe屈臆よるネッ距習醐汐計画法（3）∵．∴ ￣車・ −∴−．十・■一ご‖、
古林 隆l…‖‖‖‖‖川‖＝＝‖＝‖川＝‖‖‖‖‖＝＝＝‖‖‖‖‖＝‖＝＝‖＝‖‖＝‖‖‖＝‖州‖llllt＝‖‖‖‖‖‖‖‖‖‖‖‖＝‖＝川…l…川州Illllrl】州‖‖＝＝＝‖‖‖＝‖＝‖‖‖＝‖＝‖‖‖＝‖＝＝＝‖‖＝‖‖‖‖川Ill州＝‖‖＝‖‖＝‖‖‖‖‖‖＝川‖‖‖州‖をセルに書き込むと，ネットワークを表示し，最小木・． 薫＝・・一を求めて表示する。

今までは特に断っていないが9 すべての点が枝で連く注＞ Ⅹ，yを書き込む行やe，f，dを書き込む行結しているネットワ血クが与えられているとする。こが足りなければ，必要なだけ挿入（またはコピー）すのとき，点の数をnとすると，（n山1）本の枝をうまればよい。

く選ぶと，それらの枝だけで9 すべての点を連結する、・、−！．・・：・・′トーー．、− ノ・ことができる。このようなn個の点と（m−1）個の枝

ここでは，クラスカル法を用いる。枝を短い方からからなる部分ネットワークを木（n個の点を張る木）順に一本ずつ見て，すでに選ばれた枝と閉路ができなという。木に含まれる枝だけでは，閉路はできないが，ければ，その枝を選ぶことを繰り返し，選ばれた枝の含まれない任意の枝を一本加えると閉路ができる。さ本数がn−1になれば，終了する。このように，並んらに，枝に長さが付与されているとき，木に含まれるでいる順に，条件を満たせばどんどん選んでいく（食枝の長さの和をその木の長さといい，長さが最小であべていく）方法を貪欲法（グリーディ法）といる木を最パ、木または最短木という。最小木を求めるの初めに，枝を短い方から順に並べ変える。Excelでは，すべての点を結ぶ道路を建設したり，ケーブルをはフ ツールで簡単に並べ替えができるから，入力する設置したりするときの費用を最小にしたいときなどにときには，あまり気にする必要はない。
短い方からk番目の枝の両端の点をe（k），f（k），長必要になる。

さをd（k）とする。（枝の向きは考慮しないから，e（k）ヲ［NP5］図19に示すように，点の数n，枝の数m，f（k）の順序は結果に影響しない。）すでに選ばれた枝各点のⅩ座標，y座標，各校の両端の点e，f，長さdに付け加えると閉路ができるかどうかを判定するため＿＿＿十＿＿e ㌢∴ dⅡ＝」

図19 NP5のシート

こばやし たかし 法政大学

〒184−8584小金井市梶野町3−7【2© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
冨田偲（28）う。

オペレーションズ◎リサーチ

に，選ばれた枝で連結している点は同じグループにな

配列q，tail，neXのように，グループの先頭と末尾るように，点をグループ分けする．はじめは，枝が一および各点に対して同じグループに属する次の点を記本も選ばれていないから，一個の点だけからなるn憶する三つの配列を用意した方がよいが，ここでは，個のグループが存在する．枝が一本選ばれる毎にグル簡単に，各点のグループ番号を記憶する配列だけです

ープの数は1ずつ減っていく．いま見ている枝を選んませた．

でよいかどうかは，その両端の点のグループを比較す◆プログラムればよい．同じであれば，両端の点はすでに連結してデータの入力およびネットワークの表示の部分を図いて，この枝を加えると閉路ができるので，選べない20に示す．（サブルーチンについては，第1回の図3が，異なっていれば，選べる．選ぶと，両端のグループをどちらかに統一すればよい．手順は，次の通りで最小木の作成と表示
Fori＝1To n：grOuP（i）＝i：Next
nt ＝0：dt ＝ 0： k＝0：u＝m＋17ある．

Do（1）group（i）＝i（i＝1，2，‥・，n），nt＝0，dt＝0，k＝0（2）nt＝n−1になるまで以下を繰り返す（後判定）．

k＝ k＋1i＝e（k）：j＝f（k）

Lf group（i）く〉group（j）Then
nt ＝ nt ＋1（2．1）k＝k十1，i＝e（k），j＝（k）

C81ls（u＋nt，4）＝i（2．2）group（i）≠group（j）であれば，以下のOe】ls（u＋nt，5〉 ＝j
Cell＄（u＋nt．6）＝d（k）（2．2．1）から（2．2．4）を行う．

Call＄egment（x（i），y（i）．x（j），y（j）．ct）
dt＝dt＋d（k）（2．2．1）nt＝nt＋1

gj＝group（j）（2．2．2）i，j，d（k）をセルに出力し，枝の色を変え

For h＝1To n

lf group（h）＝gj Then group（h）＝group（i）

る．

Next hEnd tf（2．2．3）dt＝dt＋d（k）

Loop Unt‖ nt＝n−1（2．2．4）group（h）＝grOup（j）であるすべてのhに対して，

C◎l】s（u十n，6）＝dt
Fori＝1To ngroup（h）＝grOup（i）とする．
group（i）は，点iが属しているグループの番号，nt

C8IInod8（i，X（i），y（り．「，8n）
Nexti

図21最小木の作成と表示は，選んだ枝の数，dtは，それらの長さの和を示している．グループを記憶するのには，前回のNP4のDim n As Lnteger，n＾s Lnteger，iAslnteger，j Aslnteger，k Aslnteger
Dim x（10）AsInt8ger．y（10）Aslnteger
Dim e（20）＾s Fnteger，f（ZO）Aslnteger，d（20）Aslnteger
Dim rÅslnteger，Gn As tnt8ger，CS Aslnt8ger，Ct Aslnt8g8r
DilTlgrOuP（10）As［nt8ger．nt AsInteger，dt As［ntegere

Dim u Aslnteger．h Aslnteger．gj AsJnteger
データの入力n＝Cells（4，1）：m＝Ce−ls（4．2）
Fori＝1To n円x（i）＝Cetls（i＋3，4）：y（i）＝Cells（i＋3．5）
N8Xti
For k ＝1To m

8（k）＝a引＝s（k＋3，7）：f（k）＝（kIIs（k＋3，8）d（k）＝Cells（k＋3，9）
Next kネットワークの表示
r ＝10： Gn ＝ 5：CS ＝ 4：et ＝ 2
For k ＝1To m

i＝8（k）：j＝f（k）
CaIJsegment（x（i）．y（i），X（j）．y（j），CS）
Next kFori＝1To n

Ca‖ n。de（i．x（i）．y（i），「．en）e f d 6 7 20 山 3 30 4 6 35 3 6 50 2 5 60 2 3 75

Nextid（T）＝ 270

図20 データの入力とネットワークの表示
1999年6月号

図22 NP5の実行例© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）305

を参照されたい。）点および枝の色は，前回のNP3てられているときは，その色を割り当てることができと同じで，それぞれ，黄（色番号cm＝5），青（色番ないので9【−−1とする匂号cs＝4）である。変数ctは，ここでは使用してい隣接点をとりだすために，第1回のNP2で求めたないが，後で最小木を示す枝の色番号に用いている中接続行列g（i，j）を用いる偽 データ入力のときに，e＜f最」、木を求めて，表示する部分を図2＝ニ示す。枝がとするので，i＞jであれば，g（i，j）＝0であることに一本選ばれ毎に，その両端の点と長さをセルに出力す注意されたい。

るとともに，枝の色を赤（色番号ct＝2）に変えてい手順は，次のとおりである。

る。

（1）color（i）＝0（i＝1，2，…，n），np＝0，Cn＝0とす

実行例を図22に示す。ディスプレイでは9 最小本る。に含まれる枝（6，7），（1タ3），（4，6）9（3，6），（2，5）9（2，（2）np＝nになるまで以下を繰り返す（後判定）。

3）は9 赤で表示されている。

（2．1）cn＝Cm＋ユとする。
（2．2）i＝1，2タ…，nの順に，COlor（i）＝0であれば，6。点の彩色

以Fを実行する￠

ここでは，隣接している二点（一本の枝の両端の（2．2。1）color（i）＝Cn，np＝np＋1とする8点）の色が異なるように，点を彩色する（点に色を割（2．2．2）j＝i＋1，。0・，nの順に，g（i，j）＝1でり当てる）ことを考える。最小の数の色で点を彩色す

cok汀（j）＝0であれば，COlor（j）＝−1とする。

るのは9 同じグループに入れてはいけないもの（品物，（2．3）i＝1，2，d‥，nの順に，COlor（i）＜0であれば，地域など）の対がいくつか与えられている集合の分割

color（i）＝0とする。
なお9 この方法では，最通解が得られる（色の数がに必要になる。

最小になる）とは限らない。

［NP6］図23に示すように，点の数n，枝の数m，㊥プ8グラム

各点のⅩ座標，y座標，各枝の両端の点e，fをセル

デ血タをセルから読みとって，ネットワ岬クを表示に書き込むと9 ネットワークを表示し，点の彩色を行し，接続行列を求める部分は，NP2と同じであるかう。ただし，e＜fとする。

ら省略する。点の色番号の決定とそれらの色で点を表㊨アル要旨』ズム示する部分を図24に示す。ここで，色番号は，1から順につけているが，色番号1は，自であるため，表いろいろなアルゴリズムが提案されているが，ここ示するときには，それに1を加えた番号を用いている。

では9 一つ色を選んでは，その色を割り当てられる点（color（i）が1である点は，赤，2である点は，緑でを番号順に見つけて次々割り当てていくことを繰り返表示される。）すことにする。
点iに割り当てる色の番号をcolor（i）に記憶するが，実行例を図25に示す。

初期値（割り当てられていないとき）は，0とする。
ただし，いま選んでいる色が隣接している点に割り当

図23 NP6グ）シート© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

3窃6（30）オペレーションズ匂リサーチ

シートを指定するときは，Cellsの前に，シート名

点の色番号の決定
Fori＝1To n：￠Olor（i）＝0：Nextiを付ける．たとえば，

np＝0：Cn＝O
Do

n＝Sheetl．Cells（4，1）

cn ＝ cn ＋1
Fori＝1To n

Sheet2．Cells（u，2＋i）＝Cnlf oolor（i）＝O Thon
color（i）＝cn：nP＝np＋1とすればよい．サブルーチンで点や杖を表示するシー

For j ＝i＋1To n

トが，ActiveSheetになっているので，プログラムでlf（g（i，j）＝1And color（j）＝0）Th8n COIor（j）＝r1
日extJ

は，入力のときだけシートを指定しておいて，出力用

End け
Nextiのシート（たとえば，Sheet2）を開いて，そこでマFori＝1To n

クロを実行すれば，ネットワークと計算結果だけが，lf eolor（i）くO Th8n OOlor（i）＝O

そのシートに表示される．

Next t
L00P Unt‖ np＝n

8．おわりに点の彩色
u ＝m ＋18

この解説では，Excelのマクロを使うことに主眼をFori＝1To nおいたので，用いたアルゴリズムには，無駄が多いもon＝color（i）
C81l＄（u，2＋i〉 ＝Gn
CalInode（i，X（i）．y（i），「，On＋1）
Nextiのもある．計算時間をもっと短縮したいと思われるかたは，アルゴリズムの解説書（Excelの解説書ではな

図24 点の色番号の決定い）を参照して，プログラムを改良されたい．
Excelでは，いろいろなことが計算できて，その結果を出力（表示）することができるが，自分がしたいことに対して，どのようなプログラムを書けばよいかを教えてくれる文献がすぐに見つかるとは限らない．
第1回にも書いたが，自分の目的に合う文献を探すのに時間をかけるよりは，マクロの記録をとって，それを改良していく方がよい．
皆さんの新たな発見を期待しています．
■訂正

第1回（4月号）の図2，図7のプログラムの中の変数の型宣言文に誤りがありましたので，訂正します．

図2のdim文で，次のように，すべての変数の後にAsIntegerを付けてください．

DimxIAsInteger，ylAsInteger，（途中省略）csAsInteger，CaAsInteger
図7の上の二つのdim文についても同様に，すべての変数または配列の後にAsIntegerを付けてください．AsIntegerなどの型の指定は，直前の一つの

図25 NP6の実行例変数（配列を含む）だけに有効です．省略すると，実7．入力シートと出力シート数でも文字列でも格納できるバリアント型（16バイ

これまでに示したプログラムでは，入力（データ）と出力（ネットワーク，計算結果）の関係がわかりやすいように，入力用のシートと出力用のシートを同じ（ActiveSheet）にしている．そのために，枝の数mト）になりますので，すべての変数を整数型にするときは，上に記したように，すべての変数にAsInte−gerを付ける必要があります．

本解説で紹介したマクロでは，数値を実数型で記憶しても，不都合は起こらないようですが，バリアントによって出力する位置（行番号）をずらせる煩わしさ

型の変数は，メモリーを多くとる（整数型の8倍）だが生じたが，これは，入力用のシートと出力用のシーけでなく，処理時間も大きくなりますから，面倒でもすべて整数型の宣言をしましょう．

トを別にすることによって除かれる．
1999年6月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）307