￣＿こ二∴…・−・￣￣ −、．．1．∵・．． 、＿：．￣こ∵こl浅野 哲夫，小保万 事次9 KⅥrtMehlho『n‖＝‖‖＝＝‖‖＝‖‖‖‖‖＝‖‖‖‖‖＝＝＝‖‖‖‖‖‖‖‖‖＝‖＝‖‖‖‖‖‖川…川＝＝＝‖川‖‖削＝＝＝＝‖‖＝‖＝＝＝‖‖‖‖＝‖刷＝‖＝＝＝‖‖＝‖‖‖＝‖＝＝‖‖‖‖＝＝＝＝＝＝＝‖‖‖＝‖＝‖‖＝‖‖＝‖＝＝‖‖＝＝‖＝‖＝‖＝‖‖＝‖‖＝‖＝＝‖＝＝‖＝＝‖‖＝‖州‖

且① はじめに
r．111トノ1八アルゴリズムの重要性はよく分かっていても，自分・・∴のプログラムに組み込むまでの労力を考えると，素朴∴な方法で我慢してしまうことが多い。教科書にアルゴ／

せ 一／メ、＼＼ ／一／／／・八＼＼＼＼、、／／／

リズムの記述はあっても，そもそもがアルゴリズムのノハ∴「／

基礎を理解している人向けに記述されていることが／、、／、一般的なので，たとえば最も基本的なデータ構造であ、＼／ ／。

∠ 一一一一・／、、−、、るスタックの実現方法などは常識として片付けられて−→−＼、
1 ＼＼いる．抽象的なアルゴリズムだけ理解できても，具体＼、的にどんなデータ構造を用いるかが分かっていないと＼ 、、プログラムが書けないのが実情であるbこの辺りの事＼ 、＼情を分かりやすく解説している教科書が「アルゴリズ

ム＋データ構造＝プログラム」［2〕である。しかし実

図1：ボロノイ図（mEDAの画面）際にはこれでも十分ではない。データ構造として平衡2分探索木を使うとよいことが分かっても，今度はそのデ山夕構造のプログラムが必要になるからである。

差なし計算をサポートする仕掛けなどを用意することでユーザの様々な意味での負担を著しく軽減するこ

ドイツのザールブリユッケンにあるマックスプランク研究所で開発されたmEDAlは，「アルゴリズム＋mEⅢA＝プログラム」の実現を目指したソフトウェアライブラリである。まず，最初の目標は，アルゴリズ
ムとプログラムの差を縮めることであるむ LEDAはC＋＋言語で書かれたライブラリであるが，教科書でアルゴリズムが記述されているのとほぼ同じ感じでプログラムが書らナるように工夫されている。詳細は後で述べるがタ様々な繰り返し構造ヤクラスが用意されている。次の目標は，豊富なデータ構造を実現して置いておくことでタブログラマーが既存のデー一夕構造を使いやすくしていることである。これ以外にも，誤とに成功している。

具体的な例をあげて説明しよう。都市工学では都市の商圏に相当するボロノイ図（図1参照）をサブルーティンとしてよく使うが，このボロノイ図を計算するプログラムを組もうとすると，修士レベルの学生でも1週間で組むのは相当困難であるが，LEⅢAなら1日でボロノイ図を計算する関数の呼び出し方が習得できてしまう中具体的には，VORONOI（）という名前の関数を呼び出すだけでボロノイ図の計算ができる。図1は，デモ用のプログラムvoronoi＿demo．cを実行して作成したものである．今までアルゴリズムというと，新たなアルゴリズムを設計し，解析するものだという考え方が一般的だと思われるが，今では効率の良いア

あさの てつお，おぼかた こうじ 北陸先端科学技

ルゴリズムを如何に利用するかの方が重要になってき

術大学院大学情報科学研究科ている。アルゴリズムを理解していなくても，入力と〒923−且292石川県能美郡辰口町旭台…

出力の関係が分かっていれば，誰でもアルゴリズムはタルト メルホーンヲ MaxPlanck互nsti七ute払r‡nfoト使える￠ そのための道具の一つとしてLEDAを考え

matまon，Saarbr竜ckem，Germanyl正式の名称は，LibTaTyforEfncientDatatypesandAlgo−ることができる。そういう意味で，ここではアルゴリ
ズムを利用するだけの人達を対象として解説をする．

訂i七ぬms。

瑠32（24）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

2．1EDAの威力

VOidCRUST（constlist＜point＞＆S，今でも鮮明に記憶しているが，1997年にドイツのGRAPH＜point，int＞＆G）

ダグシ

ュツールで計算幾何学のワークショップに著者（の内の2人（浅野とMehlhorn）が共に参加していた．

1ist＜point＞L＝S；

1週間の予定のワークショップの2日目だったと思う

GRAPH＜circle，pOint＞VD；

が，夕方にMehlhornが自らLEDAプロジェクトの進VORONOI（L，VD）；

展状況を説明することになっていた．ちょうどその日／／addVbronoiverticesandmarkthem
map＜point，bool＞voronoLvertex（false）；の午前中にNina Amenta（現テキサス大学）によるnodev；

非常に興味深いトークがあった．問題は，平面上に点集合が与えられたとき，これらの点を適当な順で結ん

払rall皿Odes（Ⅴ，VD）

で，自然に見える図形を構成せよ，というものである（if（VD・Outdeg（v）＜2）continue；［1】・人間にとっては比較的簡単な仕事であるが，これpointp＝VD［Ⅴ］・Center（）；
VOrOnOLvertex［p］＝true；

までこの間題が理論計算機科学者の関心を引くこと

Lappend（p）；はなかった・Nina達は，この間題に計算幾何学の道具を持ちこんで，実に華麗なアルゴリズムを考案した．

）

どんな方法かと言うと，まず与えられた点集合5にDELAUNAY−TRIANG（L，G）；

対してボロノイ図VD（g）を構成する．ここで生じた

払rall」10des（v，G）

ボロノイ図の頂点の集合Ⅴと元の点集合5の和集合

if（voronoi−VerteXtG［v］］）G・del」10de（v）；

エ＝＝5∪Ⅴに対してデローネイ三角形分割を求める．

／／deletevoronoiverticesandedges
incident to them

点集合エの三角形分割とは，エの凸包（エの点をすべて内に含む最小の凸多角形）の内部をエの点だけを）頂点としてもつ三角形に分割したものであるが，任意

intmain（）の2点を結ぶ線分を1辺とする三角形分割が考えら（1ist＜point＞S；れるので，多数の三角形分割が存在する．その中でもwindowW（

デローネイ三角形分割とは，大雑把に言うと，三角形

W・init（0，1000，0，25）；の内角の最小値が最大になるものである．この三角形

W・display（）；

ConnectingPointsNatura11y）；分割に含まれる辺のうち，元の点集合gの点どうしをpointp；

結ぶ辺だけを残して，残りの辺とボロノイ図の頂点をWhile（W＞＞p）†／／inputpointsinthewindow

消し去ってできる図形が，このアルゴリズムの出力とS・append（p）；なる．

W・draw−Circle（p，2，green）；

上に述べた方法は，ボロノイ図と（その双対として）与えられる）デローネイ三角形分割さえ計算できれGRAPH＜point，int＞G；

ば，残りの部分は余り難しくない．上にも述べたよう

CRUST（S，G）；に，LEDAではボロノイ図とデローネイ三角形分割をedgee；求める関数が用意されているので，実に簡単にプログfbrall−edges（e，G）（

ラムが仕上がってしまう．実際，Mehlhornは午後の間

pointpl＝G［source（e）］；にプログラミングをして，夕方にはデモを披露したのPOintp2＝G【target（e）］；

である・具体的なプログラムは以下の通りである．

W・draw−5egment（pl・tO＿pOint（），p2・tO−pOint（），blue）；＃include＜LEDA／graph．h＞＃include＜LEDA／graphwin．h＞＃include＜LEDA／map．h＞）

W・SCreenShot（ crust．ps ）；／／outputthescreenimagetoa、pSfi1e．

＃include＜LEDA／float止ernel．h＞

1eda−Wait（2・D）；／／wait2seconds＃include＜LEDA／geo」11g．h＞

2000年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）133

図3：ランダムグラフの例

図2：プログラムCRUSTの出力例

re七urnO；）

上記のプログラムの実行例を示したのが図2である。

． 道草で・・、∴′い∴トニニニム．
LEDÅはプログラムを作成するツールであると同時に，論文を書く際の作図の道具としても使える。たとえば，グラフに関する作図で甘がなどのツールを使ったとき，グラフが完成したところで，頂点の位置を少しだけずらそうとすると，接続している辺についても変更を余儀なくされる。しかし夕mEDAではデモ用のプログラムgw…p且an】demoを実行すると，グラフ作

図4：図3のグラフの平面描画成用のウインドーが開かれて，そこでグラフを作成p編集することができる。メインメニューでGraphを選ん後，そのサブメニュ如にあるrandomgraphを選んで頂方を選択すると，下図6のような結果が示され，この点数と辺数を指定すれば，ランダムに生成されたグラグラフにKuratowskiグラフが部分グラフとして含まフが画面上に表示される。マウスを用いて頂点の位置れていることが陽に示される．ここでもLEDAの基などを調節することができるが，さらに結果をpsファ本思想がある。求められているのは，グラフの平面性イルでセ山ブすることができる，図3に一例を示す。

判定であったとしても，出力が平面的かどうかだけで図4は，さらにこのグラフを直線で平面描画したものあれば，出力の正しさを証明することは非常に難しいである。では，図5に示したようなグラフはどうだ

が，問題を少し変更して，「与えられたグラフが平面的

ろう〜 これは，メインメニュー鼠ayou七のサブメニューかどうかを判定し，もし平面的なら実際に平面上に描にあるSimpleI」ayOutの中のcirclユiarlayou七を選択し画し，そうでなければKura七OWSkiグラフが部分グラてタグラフの頂点を円周上に配置して表現したものでフとして含まれることを示せ」とすると，今度はどちある。これを平面的に描画するメニューを選ぶと，今らの結果になっても出力の正しさは一目瞭然である。

度はグラフは平面的ではないという出力があり，さらこのように，出力の正しさを検証できる形で問題を設に証明をするかどうかが尋ねられる匂 ここで証明する定することは非常に重要である．

瑠3塾（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレ｝ションズ￠リサーチ

環境に合わせてコピーすればよい。環境が用意されたパッケージとあわない場合にはソースコードパッケー

ジが用意されている。ソースコードパッケージを展開後コンパイル（make）すればオブジェクトパッケージと同じものが作られる。これをオブジェクトパッケージと同様に必要なファイルをコピーすればよい。

5．LEDAのユーザサポート
LEDAは現在世界中で10年以上にわたって使われており，バグはかなりなくなってきているが，商用に使おうとするとユーザサポートは欠かせない．従来，LEDAはアカデミックな機関で管理されてきたが，ユーザサポートを本格的に行うたやには限界がある
図5：別のランダムグラフということで，現在は会社組織になっている．LEDA
はアカデミック機関のユーザに対しては無償であるが，ソースレベルでのユーザサポートを望む商用ユー

ザは，サポートの質によって幾つかのレベルで契約できることになっている．

ユーザサポートが完備してからユーザ数は飛躍的に増大し，現在では50か国の1500の機関がユーザ登録をしている．特筆すべきことは，そのうちで計算機科学関連のユーザは半数以下であり，さらに計算機科学のユーザの中でもアルゴリズムを専門としているユーザ数は5分の1に満たないということである．つまり，殆どのユーザはアルゴリズムを考案する側ではなく，単にアルゴリズム利用するだけの側にいるのである．これは，LEDAがアルゴリズム専門家のために図6：Kuratowski部分グラフ作られたライブラリではなく，非専門家を対象として作られたものであることを如実に物語っている．

4．LEDAのインストール方法

6．LEDAの商用ユーザ

LEDAを実際に使うためには、C＋＋言語のコンパ

上記のユーザサポートに助けられて，LEDAは産イ ラ が必要で あ る が、そ れ に 加 え て業界でも着実にユーザ数を増やしてきている．主だっLEDAをインストールする必要がある。インストールたところをあげると：MCI（USA），Comp七el（Finnland），は至って簡単である。まず、インターネットを通して

Ftance Telecom，ATR（Japan），Siemens（Germany），

ダウンロードする。ダウンロードはhttp：／／www．mpi−

Sun Microsystems（USA），Daimler Benz（Germany），sb．mpg．de／LEDA／download／からできる。ダウンロー

Ford（USA），Silicon Graphics（USA），DEC（USA），Mi−

ドするにはユ…ザ登録が必要だが、上記ホームページ

nolta（USA）等々である．

から登録できる。ホームページにはUnix系のSparc−
Solaris，Mips−Irix，i386−1inuxなどとWindows系のVi−

sualC＋＋，Borland C＋＋など用のオブジェクトパッケージが用意されている。使用する環境がこれらと合えば、パッケージをダウンロードした後展開し、必要なファイルを／usr／local／1ibや／usr／local／includeなど、

2000年3月号

7．教科書のアルゴリズムをそのまま実行
上に述べたように，LEDAには実に様々なアルゴリズムが実装されて用意されているが，単に多数のアルゴリズムを寄せ集めただけではなく，さらに一歩踏み込んで，できるだけ少ない労力でアルゴリズムをプロ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）135

グラム化するための環境も与えている。ここでは，グ払rall皿Odes（Ⅴ，G）

ラフ上で最短経路を求めるダイクストラのアルゴリ（if（Ⅴ＝＝S）dist卜】＝0；

ズムがmEDAではどれほど簡潔に記述できるかを示

elsedi叫Ⅴ］＝MAXmOUBLE；

そう。まず，下に示したのはアルゴリズムの教科書でPQ−inse血（Ⅴ，di叫Ⅴ］）；見かける記述である。
）

ダイクストラの最短経路アルゴリズム

whiユe（！PQ・emp七y（））Å力：有向グラフ錯ニ（Ⅴ，屈），β∈Ⅴ，始点，‡

no鮎川ト『昭。dei」nim（）；【．ヽ・ ・・・∴∴二∴、．、ぬぬmm血edges（e，u）

払eg鼠皿
dis七（β）＝0；（

dis七（即）＝∞；鮎訂即≠β；

Ⅴ＝もa柑e七（e）；

すべての頂点に「未到達」のラベルをつける；

doublec＝dist［u］＋co叫e］；

w勤怠且e「未到達」の頂点が存在する

if（c＜di叫Ⅴ］）

舶祝を「未到達」の頂点の中でdis七の値が（PQ。decrease＿p（Ⅴ，C）；d血［Ⅴ］＝C；）最小のものとする；）

視に「到達」のラベルをつける；）

蝕ぼ餌から出るすべての辺e＝＝（叫γ）‡通￠dis七（u）＝mim（dist（u，dist（祝）＋cost（e））；

8。 グラフアルヨ■リズムodのdLEDAにはグラフに関して実に様々なアルゴリズム

enagaが用意されているが，主だったものを列挙すると以下
ダイクストラのアルゴリズム自身は非常に基麓的なものであるので詳しい説明は省略するが，上の記述では曖昧な記述が多い。たとえば，有向グラフはどのようなデ仙夕構造で管理すべきかについては何も指定していない∴頂点や辺についても同様である。最も難関であるのはタ「未到達」の頂点の中でdis七の借が最小のものを求める所であるが，アルゴリズムの知識を待った人なら，プライオリティーキューが必要になる
ことば分かるが，実際のデータ構造を考えようとすると結構面倒である。mEⅢAでは，頂点と辺の配列とグラフを定めるデータタイプと，節点に関するプライオリティーキューのデータ構造をプログラムの先頭で宣言するだけでよい．紙数の都合上，詳細な説明はできないが，下に示したmEDAプログラムは上記のアルゴリズムの記述にかなり近いことが理解してもらえるであろう。のようになる。
飢トポロジカルソ如卜

望。深さ優先探索；訪れた節点に印だけをつける版と，番号付けをする版がある。
乱 幅優先探索：訪問したかどうかを示すラベルづけするだけの版と，始点からの距離をつける版とがある。

4。強連結成分‡与えられた有向グラフのすべての節点についてタその節点が属する強連結成分の番号を求める。

臨。2連結成分；与えられたグラフを無向グラフと見なして，各節点が属する2連結成分の番号を求める。
凱推移的閉包三 与えられた有向グラフの推移的閉包を計算して返す印7。最短経路：

7。1単 始点最短経路アルゴリズム； Dりks七raのア

vo温dⅢⅠ』ⅨST乱A（constgraph＆G，nOdes，

ルゴリズムとBellman−靴〉rdのアルゴリズムを含む

consもedge⊥arどay＜double＞＆cosも，7．2全点対最短経路アルゴリズム： すべての節点対

node＿array＜donble＞＆d五如）について最短経路を求める。
臥 最大ヲ∈巨「＋：脚eflow−puSbに基づくGoldberg−i

node＿pq＜dolユb且e＞PQ（G）；

TaIjanの最大フロー計算アルゴリズム・様々なヒュー

nodev；edgee；

リスティックスを組み込んだ版も用意されている。

関済（28）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ9．最小コストフロー：CapaCity−SCalingと最短経路位置づけている．具体的には，様々なアルゴリズムをアルゴリズムに基づいて最小コストフローを求める

利用可能な形で一般に公開することも重要な使命のアルゴリズム．これについても幾つかの変形版が用意一つであるが，一部のソフトはLEDAで記述するこされている．とが計画されている．現在はまだ整備中であるが，是10．2部グラフの最大マッチング：与えられた2部

非下記サイトを訪問されたい．

グラフに対して要素数最大のマッチングを求める．

http‥／／zagato・kuamp・kyoto−u・aC・jp

11．2部グラフの最大重みマッチング：／1abs／or／tokutei98／database／index．html

12．一般のグラフに対する最大マッチング：

ll．LEDAの数値誤差対策

13．最小全域木：

14．グラフの平面性判定：線形時間のアルゴリズム

浮動小数点数を用いた計算では数値誤差対策が非の他に，Kuratowskiグラフを部分グラフとして含む常に重要である．特に，幾何データの処理においてかどうかを判定するアルゴリズムもある．

は，数値誤差が位相情報と矛盾するためにプログラム

15．平面グラフの三角形分割：が暴走することが深刻な問題である，LEDAでは，誤16．平面グラフを5色で彩色するアルゴリズム：

差なしの計算を効率良くサポートするためのデータ

17．グラフ描画アルゴリズム：様々な条件の下で平タイプを用意している．具体的には，int，aOat，doll−面グラフを直線などを用いて平面上に描画するアルbleの他に，任意桁数の整数を表すinteger，任意精度ゴリズム多数．の浮動小数点数を表すbigfloat，有理数を表すratio，nalなどが用意されている．これ以外にも様々なデー

9．幾何ルゴリズム

タタイプが用意されているが，詳しくは最近刊行されグラフだけではなく，計算幾何学関係のアルゴリズ

たLEDABook［3］かLEDAManual［4】を参照されたい．

ムも多数用意されている．下に名前だけを列挙してお

基本的には，浮動小数点数の代わりに有理数の多倍長

く．

表現を用いて，誤差が生じないように計算するという

1．凸包を求めるアルゴリズム：ものであるが，単純な仕掛けでは実行時間が爆発して2．点集合に対する三角形分割（デローネイ三角形分しまう．そのために，浮動小数点数での計算結果をう割を含む）：まく利用している．

3．制約つきの三角形分割：

参考文献

4．多角形の三角形分割：［1］NtAmenta，M・Bern，andD．Eppstein：

5．ユークリッド最小木：

Thecrust

and theβ−Skeleton：Combinatorialcurve recon−

臥 ボロノイ図の計算：

StruCtion， Graphics Models andhna9e Process−

7．最遠点ボロノイ図：Ⅲ飢pp．125−135，1998．

8．最大空円：
9．最小包含円：［2］N．ヴイルト著，片山卓也訳：「アルゴリズム＋10．真円度の計算：半径の差が最小である同心円のデータ構造＝プログラム」，日本コンピュータ協

間にすべての点が入るような2つの円を求める．

会，1979．

11・与えられた点を自然に結ぶ（CRUST）：［3］K・MehlhornandS．Naher：

12．線分交差列挙アルゴリズム：

LEDA：Aplatform

forcombinatorialandgeometriccomputing，

13．最近点対；
14．最小包含長方形：
15．単純多角形かどうかの判定：［4】K・Mehlhornetal・：

10．公開されているアルゴリズム

Sion4・0，

TheLEDAUserManualVer−

Max PlanckInstitute fiirInformatik，Germenay，1999．

科学研究費特定研究「アルゴリズム工学」のグルー
プでは，アルゴリズムの実用化研究を推進しているが，一般的普及のための重要な道具としてLEDAを2000年3月号

Cm−bridgeUniv．Press，1999．

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

（29）13丁