 複雑なアルゴリズムも簡単にプログラム化できる魔法のツール
北陸先端科学技術大学院大学 情報科学研究科 浅野哲夫，小保方 幸次
マックスプランク研究所，ドイツ   

概 要
アルゴリズムの重要性はよく分かっているけれども，自分のプログラムに組み込むまでの労力を考えると，素朴な方法で我慢してしまうことが多い．特に多くの場合データ構造までは記述されていないことを考えると，教科書で記述されたアルゴリズムと実際のプログラムとの間には大きなギャップがある．これがアルゴリズムの普及を妨げている大きな一大要因であるが，このギャップを埋めるべくドイツのマックスプランク研究所で開発されたのが  である．本文では，  を用いると如何にプログラミングが簡単になるかを具体的に解説する．

はじめに計算機の進歩に伴って扱う問題のサイズが飛躍的に増大し，以前から使ってきた単純なアルゴリズムに基づくプログラムでは処理しきれない状況が現実のものとなってきています．少しでも計算時間の見積もりをしたことのあるプログラマーならアルゴリズムの重要性はよく分かっていると思いますが，さて自分のプログラムに組み込むまでの労力を考えると，なかなか決心がつかないということが多いと思います．問題は何かと言うと，教科書にアルゴリズムの記述はあっても，そもそもがアルゴリズムの基礎を理解している人向けに記述されていることが一般的なので，たとえば最も基本的なデータ構造であるスタックの実現方法などは常識として片付けられていることです．抽象的なアルゴリズムだけ理解できても，具体的にどんなデータ構造を用いるかが分かっていないとプログラムが書けないのが実情です．実際，どんなデータ構造を用いるかによってプログラムの効率は大きく異なりますが，その辺りの事情を分かりやすく解説している教科書が「アルゴリズム＋データ構造＝プログラム」  です．しかし，実際にプログラムを書くにはこれでも十分とは言えないでしょう．たとえば，データ構造として平衡２分探索木を使うとよいことが分かっても，今度はそのデータ構造のプログラムが必要になるからです．
ドイツのザールブリュッケンにあるマックスプランク研究所で開発された （正式の名Æ    ）は，「アルゴリズム＋  ＝プロ称は，グラム」の実現を目指したソフトウェアライブラリです．このライブラリは約  年前に開発が始まって以来，改良が加えられてきていますが，最初の目標は，アルゴリズムとプログラムの差を縮めることでした． は 言語で書かれたライブラリですが，教科書でアルゴリズムが記述されているのとほぼ同じ感じでプログラムが書けるように工夫されています．詳細は後で説明しますが，様々な繰り返し構造やクラスが用意されています．次の目標は，豊富なデータ構造を実現して置いておくことです．これによって，プログラマーは努力をせずに既存のデータ構造を使うことができます．これ以外にも，誤差なし計算をサポートする仕掛けなどを用意することでプログラマーの様々な意味での負担を著しく軽減することに成功しています．
本文では，まず具体的な例題に即して  の威力を説明します．教科書ではアルゴリズムを擬似言語で記述することが一般的ですが， によるアルゴリズムの記述がいかにテキストレベルのものに近いかを  ダイクストラ の最短経路発見アルゴリズムを例にとって説明します．また， では多数のアルゴリズムが関数の形で用意されていますが，特に，グラフと計算幾何に関してどんなアルゴリズムが用意されているかを述べた後，ユーザサポートやインストールの方法についても説明します．

計算幾何のアルゴリズム例
如何に良いアルゴリズムを設計するかではなく，如何に良いアルゴリズムを選ぶか具体的な例をあげて説明することにしましょう．計算幾何学における重要な概念の一つにボロノイ図というものがあります．平面上に多数の点が与えられているとき，平面をどの点に最も近いかによって領域に分割したものです．たとえば，２点だけの場合，垂直２等分線を引いて平面を２分割することに対応しています．多数の点がある場合には，比較的近い点対について垂直２等分線を引くことによって平面を分割していくことになります．ボロノイ図を構成す
るアルゴリズムは幾つか知られていますが，計算幾何学の分野で最初に提案されたものは分割統治法に基づいたものでした．つまり，与えられた点集合を１本の直線でほぼ同じ点数の部分集合に２分割した後，それぞれの部分集合に対するボロノイ図を再帰的に構成して，それらを中央部で統合するというものです．記述自身は簡単ですが，この記述だけでプログラムが書ける人は天才と言うべきでしょう．
最低必要なのは，２点に関する垂直２等分線の求め方，２本の線分（直線）の交点の計算方法でありますが，線分の連結関係を表現するデータ構造をどうするかはもっと大きな問題です．計
算幾何学では常識になっていることですが，計算誤差によって交差判定で意外に簡単に間違った判定結果が出てしまいます．そのためにプログラムの暴走を招いたりするので，これは深刻な問題です．後でも詳しく説明しますが， では誤差なし計算を採用することによってこの問題を解決しています．このように，ボロノイ図を計算するプログラムを組むのは並大抵なことではありません．修士レベルの学生でも１週間で組むのは相当困難だと思いますが， なら１日でボロノイ図を計算する関数の呼び出し方が習得できてしまいます．具体的には，!"#"$"%という名前の関数を呼び出すだけでボロノイ図の計算ができてしまいます．図  は&  で用意されているデモ用のプログラム '    ( を実行して作成したものです．このプログ
ラムでは，画面上にマウスで点を指定すると，上部にあるボタンをクリックするだけでボロノイ図だけでなく，ユークリッド最小木や凸包などを求めることができるようになっています．
今までアルゴリズムというと，新たなアルゴリズムを設計し，解析するものだという考え方が支配的ではなかったかと思いますが，今では効率の良いアルゴリズムを如何に利用するかの方が重要になってきています．アルゴリズムを理解していなくても，入力と出力の関係が分かっていれば，誰でもアルゴリズムは使えます．そのための道具の一つとして  を考えること

図 ) ボロノイ図（ の画面）ができます．

 だとこんなに簡単

今でも鮮明に記憶していますが，**+ 年にドイツのダグシュツールで計算幾何学のワークショップに著者の内の２人（浅野と , ）が共に参加していました．１週間の予定のワークショップの２日目だったと思いますが，夕方に ,  が自ら  プロジェクトの進展状況を説明することになっていました．ちょうどその日の午前中に $  （現テキサス大学）による非常に興味深いトークがありました．問題は，平面上に点集合が与えられたとき，これらの点を適当な順で結んで，自然に見える図形を構成せよ，というものです ．人間にとっては比較的簡単な仕事ですが，これまでこの問題が理論計算機科学者の関心を引くことはありませんでした．$ 達は，この問題に計算幾何学の道具を持ちこんで，実に華麗なアルゴリズムを考案しました．どんな方法かと言うと，まず与えられた点集合 に対してボロノイ図 !
を構成します．ここで生じたボロノイ図の頂点の集合  と元の点集合 の和集合  に対してデローネイ三角形分割を求めます．点集合  の三角形分割とは，  の凸包（ の点をすべて内に含む最小の凸多角形）の内部を  の点だけを頂点としてもつ三角形に分割したものですが，任意の２点を結ぶ線分を１辺とする三角形分割が考えられますので，多数の三角形分割が存在することになります．その中でもデローネイ三角形分割とは，大雑把に言うと，三角形の内角の最小値が最大になるものです．この三角形分割に含まれる辺のうち，元の点集合 の点どうしを結ぶ辺だけを残して，残りの辺とボロノイ図の頂点を消し去ってできる図形が，このアルゴリズムの出力となります．
上に述べた方法は，ボロノイ図と（その双対として与えられる）デローネイ三角形分割さえ計算できれば，残りの部分は余り難しくありません．上にも述べたように， ではボロノ
イ図とデローネイ三角形分割を求める関数が用意されていますので，実に簡単にプログラムが仕上がってしまいます．実際，,  は午後の間にプログラミングをして，夕方にはデモを.

披露したのです．具体的なプログラムは以下の通りです．

1 (/0 1 (/0 12  (/0 1(/0 13 3('  #456   7 5&8#9: & 7 8/0   - 5;
8#9: &   !;!"#"$"%& ! ;
11

 !

   '  & 

'    ' < ;  ';
  '& !



!( 0'   0;   - ! '(  ;'  ' <  -  0;

(  ;4$= 6#%$8& 8 ;  '& 8'

  ' < 8 '

8(  ' ;    5;

3 3 >; >( ;  ;3>

110     3 35(  ;8#9:

 &  8;

#4565& 8 ;  ';  ;>( ;

  '& 8>(3  8 ' ; & 8>(3 8  0  & 8   ;>(  ? 0(? ;@11 00      3 ( ; A(113    0  ;

上記のプログラムの実行例を示したのが図  です．同図下には，実行の途中で構成されたデローネイ三角形分割を示しています．

図 ) プログラム #456 の出力例（左）と対応するデローネイ三角形分割（右）

ツールとしても使える アルゴリズムのことを知らない人でも，平面グラフの４色定理については新聞や本で読んだことがあるのではないでしょうか．これは，地図の上で隣接する国を区別するために，隣接する国には必ず異なる色で塗り分けるとしたとき，実は４色で十分だという定理のことです．この定理は長年未解決でしたが，計算機を駆使した証明によって遂に肯定的に解決されて世間を騒がしたことをご記憶の読者も多いことでしょう．したがって，理論的には存在証明があるのですが，実際に白地図を与えて，４色だけで条件を満たすように彩色してほしい，と言われると，なかなか難しいものです．
計算機に上記の問題を解かせようとすると，まず問題を抽象的に定式化する必要があります．
この問題の場合にはグラフを用いるのが最も適切でしょう．問題は隣接する国に異なる色を割り当てないといけないのですが，国の形がどのようなものであっても関係はないわけです．そこで，国を１つの点で表し，２つの国が隣接しているときには対応する２点間を線で結ぶことにします．すると一つの図形ができますが，この図形をグラフと言います．実は，うまく線を引くと，このグラフは必ず平面的に描くことができます．つまり，どの２つの線も端点以外で交差しないように描くことができるのです．逆に，うまく線を引けば，交差しないように描くことができるような隣接関係を表したグラフのことを平面的グラフと言います．
先の彩色問題は，実は平面的グラフの点に彩色を施す問題だと言うことができます．制約は，B

17182101316199114151458126713

図 .) 地図の例
線で結ばれている２点には必ず違う色を彩色しないといけないというものです．４色定理では４色だけで十分だと保証しているのですが，どのように４色を割り当てるべきかを求めるのは難しい問題です．しかし，５色を使っても良いということになると，効率の良いアルゴリズムが知られています．ただ，そのアルゴリズムを使って彩色しようとすると，そのアルゴリズムを勉強して，細部に至るまで動作を理解した上でプログラム化する必要があります．グラフ理論を勉強したことがない人にとって，これは大変なことです．
17182101316199114145158126713

図 @) 国の隣接関係を表すグラフ
もっと難しい問題があります．上に平面的グラフを定義しましたが，今度は任意にグラフを与えて，それが平面的かどうかを問うのです．わかりやすく言うと，点には  から  までの番号がついているものとします．グラフを指定するには，どの点とどの点が隣接するかを指定すればいいわけですから，   の行列で隣接関係を表すことができます．つまり， 番目の点と 番目の点が隣接するなら，行列の   および   要素を  とし，そうでなければ  とするように決めればいいわけです．このような行列が与えられて，その行列が表すグラフが平面的かどうかを判定しなければならないわけです．人間なら，紙の上に適当に点を並べて，適当に番号をつけ，行列の値に従って結ぶべき２点間に線を引いて行きます．最後まで交差なく線が引けたら，平面的だと言うことができます．でも，少し隣接関係が複雑になると，本当は交差なく引けるのに，その方法を見つけるのが非常に難しくなります．図 B の例を見て下さい．適当に点を並べて単純に直線で結んだために，交差が生じていますが，うまく点の位置を変えると交差をなくすことができます．あなたはできますか？
上に述べた問題は，グラフの平面性判定問題と言って，グラフ理論のテキストなら必ず載っている重要な問題です．グラフ理論の方では，グラフが平面的であるための必要十分条件が求めC

471251190136103821図 B) このグラフは平面的か？
られていますが，その条件を確かめるという形でプログラムを書くことはかなり困難です．そこで，アルゴリズムの分野では，如何にして効率良く平面性を判定するかが研究されてきました．幸いなことに，点の個数に比例する時間で平面性を判定するアルゴリズムが :   と
6   によって *+@ 年に求められていますので，アルゴリズム理論としては解決がついているのですが，実際にそのアルゴリズムをプログラムの形に実現するのは，余程グラフとアルゴリズムの知識を持ち合わせていないと難しいでしょう．事実，アルゴリズムの分野では平面性判定に関しては幾つかの方法が提案されていますが，やはりプログラムを組むとなると，相当の覚悟が必要になります．
 にはグラフの平面性を判定するプログラムが組み込まれているだけではなく，平面的であるグラフを実際に平面的に，すなわち辺が交差しないように描画する関数が組み込まれています．たとえば，デモ用のプログラム 3    を実行しますと，グラフ作成用のウィンドーが開かれて，そこでグラフを作成・編集することができます．このグラフを平面描画するメニューを選んで実行すると図 C に示す結果が得られます．このように， はプログラムを作成するツールであると同時に，論文を書く際の作図の道具としても使えるのです．出力
結果を  ファイルとして出力することも簡単です．実際& 図 C もその機能を使って描いたものです．
では，図 + に示したようなグラフはどうでしょう．これは，メインメニュー 0 のサブメ
ニューにある 5 0 の中の  00 を選択して，グラフの頂点を円周上に配置して表現したものです．平面的に描画するメニューを選ぶと，今度はグラフは平面的ではないという出力があり，さらに証明をするかどうかが尋ねられます．ここで証明する方を選択すると，図 のような結果が示され，このグラフに D0  3 グラフ（この場合は， ¿ ¿ ）が部分グラフとして含まれていることが陽に示されます．
ここにも  の基本思想が現れています．求められているのは，グラフの平面性判定であったとしても，出力が平面的かどうかだけであれば，出力の正しさを証明することは非常に難しいわけですが，問題を少し変更して，「与えられたグラフが平面的かどうかを判定し，もし平面的なら実際に平面上に描画し，そうでなければ D0  3 グラフが部分グラフとして含+7151494101211518361302

図 C) 図 B のグラフの平面描画まれることを示せ」とすると，今度はどちらの結果になっても出力の正しさを検証するのは簡単です．このように，出力の正しさを検証できる形で問題を設定することは非常に重要です．

 をインストールしようを実際に使うためには& 言語のコンパイラが必要ですが，それに加えて  をインストールする必要があります．インストールは至って簡単です．まず，インターネットを通してダウンロードします．ダウンロードは)11333(E((11 3

1

からできます．ダウンロードするにはユーザ登録が必要ですが，上記ホームページから登録できます．ホームページには 4< 系の 5 E5  & ,E% <& .FCE0< などと > 3 系の!0  & G  など用のオブジェクトパッケージが用意されています．使用する環境がこれらと合えば，パッケージをダウンロードした後で展開し，必要なファイルを10 1  1
や10 1  10 など，環境に合わせてコピーすればよいわけです．環境が用意されたパッケージと合わない場合のためにソースコードパッケージが用意されています．ソースコードパッ
ケージを展開した後でコンパイル   すれば，オブジェクトパッケージと同じものが作られます．

 のサポート体制
は現在世界中で  年以上にわたって使われており，バグはかなりなくなってきていますが，商用に使おうとすると信頼できるユーザサポートは欠かせません．従来， はアカ
デミックな機関で管理されてきましたが，ユーザサポートを本格的に行うためには限界があるということで，現在は会社組織になっています．  はアカデミック機関のユーザに対しては無償ですが，ソースレベルでのユーザサポートを望む商用ユーザは，サポートの質によってF

435261740815910761214101311312

図 +) 別のランダムグラフ（左）と D02 3

1

部分グラフ（右）幾つかのレベルで契約できることになっています．
ユーザサポートが完備してからユーザ数は飛躍的に増大し，現在では B か国の B の機関がユーザ登録をしています．特筆すべきことは，そのうちで計算機科学関連のユーザは半数以下であり，さらに計算機科学のユーザの中でもアルゴリズムを専門としているユーザ数は５分の１に満たないということです．つまり，殆どのユーザはアルゴリズムを考案する側ではなく，単にアルゴリズム利用するだけの側にいるのです．これは， がアルゴリズム専門家のために作られたライブラリではなく，非専門家を対象として作られたものであることを如実に物語っています．

 の商用ユーザ
上記のユーザサポートに助けられて， は産業界でも着実にユーザ数を増やしてきています．主だったところをあげると：,%45 &  H  & H  6 & 6#I   &58  
8& 50 , 45 &  45 & 45 & ,  45GJ8  & H45 & 5 等々です．

教科書のアルゴリズムからプログラムへ
上に述べたように，  には実に様々なアルゴリズムが実装されて用意されていますが，単に多数のアルゴリズムを寄せ集めただけではなく，さらに一歩踏み込んで，できるだけ少ない労力でアルゴリズムをプログラム化するための環境も与えています．ここでは，グラフ上で最短経路を求める  のアルゴリズムが  ではどれほど簡潔に記述できるかを示しましょう．まず，下に示したのはアルゴリズムの教科書で見かける記述です．

 の最短経路アルゴリズム
入力：有向グラフ- &  & 始点，* )


&辺のコスト- ; - ; - ;

すべての頂点に「未到達」のラベルをつける;
 「未到達」の頂点が存在する  を「未到達」の頂点の中で  の値が最小のものとする;
 に「到達」のラベルをつける；
  から出る すべての 辺  -    -  &    ;のアルゴリズム自身は非常に基礎的なものなので詳しい説明は省略しますが，上の記述には曖昧な記述が多くあります．たとえば，有向グラフはどのようなデータ構造で管理すべきかについては何も指定していません．頂点や辺についても同様です．最も難関であるのは，「未到達」の頂点の中で  の値が最小のものを求める所ですが，アルゴリズムの知識を持った人なら，プライオリティーキューが必要になることは分かるのですが，実際のデータ構造を考えようとすると結構面倒です． では，頂点と辺の配列とグラフを定めるデータタイプと，節点に関するプライオリティーキューのデータ構造をプログラムの先頭で宣言するだけです．紙
数の都合上，詳細な説明はできませんが，下に示した  プログラムは上記のアルゴリズムの記述にかなり近いことが理解してもらえるでしょう．
'  %ID56#       K

 78&   & 07  & 07  0 9L8 ;  ';  ;  '& 8  ' --   ' - ;  ' - ,M"4G;9L( '&  ' ;3N9L(   0 - 9L(  ;0 & 0' -  ; 0  -  0    ;   ' 9L(   '&  ;  ' - ;  の構成には様々な基本的なデータタイプが用意されています．スタックやキューはもちろんのこと，たとえば連結リストも  ; のように宣言することで，整数値をもつ単方向連結リストを利用することができます．この他にも各種のプライオリティーキューや，有向および無向のグラフも簡単に扱えます．さらに，点，直線，多角形などの幾何対象物の扱いも非常に容易です．計算幾何では最近ヨーロッパの大学が中心となって 8 と呼ばれるライブラリーが開発されていますが，それとの親和性も図られていますので，共用可能です．
 における計算誤差対策

浮動小数点数を用いた計算では計算誤差対策が非常に重要です．特に，幾何データの処理においては，計算誤差が位相情報と矛盾するためにプログラムが暴走することが深刻な問題になります． では，誤差なしの計算を効率良くサポートするためのデータタイプを用意しています．具体的には，Ｃ言語でサポートされている  & &  & 2 &  0 の他に，任意桁数の整数を表す  & 任意精度の浮動小数点数を表す 2 ，有理数を表す    などが用意されています．2  では，2 ))    ; のようにして仮数部の長さを指定したり，丸めの方式さえも指定できるようになっています．さらに  に特徴的なデータタイプに   があります．これは，
  < - K + K +   ;のように使います．このように平方根や立方根などを用いて定義された値を持てるのが   変数です．数学的には上式の値は + ¾ - . となりますが， の   変数も同じ値をもつことになります．これはかなりすごいことです．これ以外にも様々なデータタイプが用意されていますが，詳しくは最近刊行された  G  . か  , 0  @ を参照して下さい．
基本的には，浮動小数点数の代わりに有理数の多倍長表現を用いて，誤差が生じないように計算するというものですが，単純な仕掛けでは実行時間が爆発してしまいます．そのために，浮動小数点数での計算結果をうまく利用しています．

グラフに関するアルゴリズムにはグラフに関して実に様々なアルゴリズムが関数の形で用意されていますが，主だったものを列挙すると以下のようになります．
( トポロジカルソート( 深さ優先探索 訪れた節点に印だけをつける版と，番号付けをする版があります．
幅優先探索 訪問したかどうかを示すラベルづけするだけの版と，始点からの距離をつける版とがあります．
@( 強連結成分 与えられた有向グラフのすべての節点について，その節点が属する強連結成分の番号を求めます．
B( ２連結成分 与えられたグラフを無向グラフと見なして，各節点が属する２連結成分の番号を求めます．
C( 推移的閉包 与えられた有向グラフの推移的閉包を計算して返します．
+( 最短経路のアルゴリズムと G EH  のアルゴリズ+( 単一始点最短経路アルゴリズム
ムを含みます(すべての節点対について最短経路を求めます(+( 全点対最短経路アルゴリズム
F( 最大フロー  2 3E0 に基づく 8  E6   の最大フロー計算アルゴリズム( 様々なヒューリスティックスを組み込んだ版も用意されています．
*( 最小コストフロー   E  と最短経路アルゴリズムに基づいて最小コストフローを求めるアルゴリズム( これについても幾つかの変形版が用意されています．
( ２部グラフの最大マッチング
与えられた２部グラフに対して要素数最大のマッチングを求めます(( ２部グラフの最大重みマッチング( 一般のグラフに対する最大マッチング.( 最小全域木@( グラフの平面性判定 線形時間のアルゴリズムの他に， D0 3 グラフを部分グラフとして含むかどうかを判定するアルゴリズムもあります(B( 平面グラフの三角形分割C( 平面グラフを５色で彩色するアルゴリズム
+( グラフ描画アルゴリズム 様々な条件の下で平面グラフを直線などを用いて平面上に描画するアルゴリズム多数．
.(

計算幾何学関係のアルゴリズム

グラフだけではなく，計算幾何学関係のアルゴリズムも多数用意されています．下に名前だ
けを列挙しておきます．
( 凸包を求めるアルゴリズム
( 点集合に対する三角形分割 デローネイ三角形分割を含む）.( 制約つきの三角形分割@( 多角形の三角形分割
B( ユークリッド最小木C( ボロノイ図の計算+( 最遠点ボロノイ図F( 最大空円*( 最小包含円真円度の計算 半径の差が最小である同心円の間にすべての点が入るような２つの円を求めます．
( 与えられた点を自然に結ぶ ( 線分交差列挙アルゴリズム
.( 最近点対@( 最小包含長方形B( 単純多角形かどうかの判定(日本で公開されているアルゴリズム

科学研究費特定研究「アルゴリズム工学」のグループでは，アルゴリズムの実用化研究を推進していますが，一般的普及のための重要な道具として  を位置づけています．具体的には，様々なアルゴリズムを利用可能な形で一般に公開することも重要な使命の一つですが，一部のソフトは  で記述することが計画されています．現在はまだ整備中ですが，是非下記サイトを訪問して下さい．
)11333E( (( E0( (1  E11<(参考文献
 $(  & ,( G &
0 '  0 &?

 ( ) ?6  0   E )          (BE.B **F (Ｎ．ヴィルト著，片山卓也訳：「アルゴリズム＋データ構造＝プログラム」，日本コンピュータ協会 *+* (. D( , 5( $O ) ?)           E

0&?   4'( 9  *** (@ D( ,% () & 8 ?6  4, 0  !   @(&? , < 9  %0*** (.

0O