追加キーワード: グラフ理論，ネットワーク最適化，展開形ゲーム，ゲームツリー，可視化，ヴィジュアル，グラフィックス．

前回記事にある「油分け問題」に続き，今回は最短路問題を解くダイクストラ法 (Dijkstra 法) の Ruby プログラミングを担当科目の課題にした．こちらはアルゴリズム自体はその疑似コードとともに授業で学んだので，あとは Ruby で表現する問題だ (受講生によればそこがむずかしい)．たとえば Wikipedia にある疑似コードを下敷きにしていいと受講生には伝えた．

自分でもプログラムを書いてみた．路線探索プログラムの本質的な部分が初心者にも書けたということであり，なかなか素晴らしい．(ちなみに路線探索では2番目以降に表示する経路をどうするかがむずかしいらしい．←こちらのサイトにはダイクストラ法の図解もある．)

だが，なにかもの足りない．いや，将来「もの足りない」と言う学生が出てきそうな気がする．そう，なにもかも文字として処理されるのだ！　つまり重み付き枝たち (たとえば距離あるいは重み 10 の枝 (s, 1) を [:s,1,10] と書く) を要素とする配列と出発点 (たとえば :s と書く) を持つインスタンス problem を作れば，あとは problem.shortest_path_to(v) とやることで任意の点 v への最短路とその距離が配列として返って来る．図がどこにも現れないのである．

そういう学生には，「心配はいらない．こういうグラフをテキストデータから描いてくれるプログラムは存在するはずだ」と答えるつもりだった．グラフというのは点と点のむすびつきの情報だけで決まるものであり，画像としての表現はその本質ではないからだ．把握のしやすさや見栄えを別にすれば，データを画像としてではなくテキストデータとして保持するのが本質的なやり方と言える．たぶん Mathematica あたりもそんな描画機能を備えているだろう．そんなところにたまたま飛び込んで来たのが，こちらの解説記事「ITpro【特選フリーソフト】テキストをグラフに変換 Graphviz」だ．ふむふむ，Graphviz ってのがあるんだね．ということで，Mac OS X edition of Graphviz を試してみた．

読者は「平面グラフ (点の位置をうまく選べば，辺が交差しないように平面上に描けるグラフ) をじっさいに辺が交差しないように描いてくれるんだろうか？」などの興味を持つかもしれない．平面グラフかどうかは理論的にはクラトウスキーの定理で判定できるが，このソフトがその判定機能を備えているかどうかは知らない．デモンストレーションを一見したところ，交差する枝が少ない気はするので，それに近い機能を利用しているんじゃないかとは思うが．

個人的には，これが家系図に使えるかどうかに関心がある．(ちょっと試したところ，残念ながら日本語が文字化けしたけど．) じっさい，同じ疑問をもったひとはいたようで，その返答として Graphviz で家系図を描いた例はあった．ポイントは親子関係を有向枝で表し，男性のノードを長方形で女性のノードを楕円で表すことにより区別することだろう．ノードを形で区別することは (ノードにノード名と異なるラベルをつける，あるいはノード名の付け方に規則を導入するという意味で多少)《グラフ》の定義を逸脱しているが (追記参照)，こうすることで「父・母・子」の3項関係を表すことはできる．ただし，このままでは兄弟の順番は (ラベルなしでは) 表現できないし，父母と兄弟の間の枝を交差させず直線で描こうとすれば (リマーク 1)，たぶん (先祖を子孫より位置的に上に描くといった) 階層構造は崩れる．じっさい，さっきの例のコードを描画してみたところ，根っこ以外のどのノードも出次数が 1，つまり子供がひとりだけということになっていた．すなわちこの家系図はある個人の直系尊属のみを記録したものであり，兄弟や傍系の存在に起因する複雑さを回避したものだった．

リマーク 1.

読者は「そもそも親子間の枝をつねに交差なしの直線で描くことは無理では」と思うかもしれない．だが，できるのだ．一組の夫婦とその子だけからなるグラフに関する限りできる．そのグラフが平面グラフであることは描いてみればすぐ確かめられる．そして，たぶん驚くべきことにファーリの定理によれば，すべての平面グラフはどの辺もまっすぐになるように描けるのだ!……いや，そんな定理を持ち出すまでもなく，子を横一列にならべて，親をその列の上下に配置すればできる．よき教育者は，イメージを喚起しやすいように教育的配慮をするものだ．これはどうか？　時間軸の両側に男女がいて，ある時点 t におけるセックスでできた子供を，時間軸上の点 t に配置する感じだ．(ちなみに一組の夫婦とその n 人の子からなる親子関係グラフは完全2部グラフ K_2,n という．)

なお，夫婦 1 組子供 5人を表現する dot ファイルを作って Graphviz の 4 つのレイアウトをちょっと試したところ，いずれの描画も枝が交差するものだった．「平面グラフを辺が交差しないように描いてくれるんだろうか？」という疑問には，いまのところポジティブな答を得ていない．

というわけで，Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で，階層構造の表現を優先するのがよさそうだ．ここまでできるのだから，一組の夫婦にかんする親子関係の枝をまとめる方法 (つまり完全2部グラフ K_2,n のすっきりした描き方) を提供してくれてもいい気はするけどね．[追記 2 参照]

追記 1 (1/26/2008).

リマーク 1 などに若干手を入れた．

「お前は「父・母・子」の3項関係にこだわり過ぎている．家系図を描く上で重要なのはだれとだれが子供の親であるかであって，そのどちらが父親でどちらが母親かということではない．あくまでも親子関係という2項関係が基本だ．数学でも，2項関係の理論を多項関係のそれに拡張して本質的なちがいがあったか？　よき振る舞いをする多項関係は，2項関係に一定の条件を加えたものにすぎないのではないか？　お前の専門とする社会選択でも，《選好》という2項関係をもとにした理論と，多数からなにかを選ぶ選択関数という多項関係をもとにした理論とで大きなちがいがあったか？」とのお告げがあった．

アダムとイブの関係を基本にして「生めよ，ふえよ，地に満ちよ」と祝福した神のお告げにしては意外だが，そこは問わないことにする．なるほど，《親子関係》を基本と考えて，それぞれのノードが親をふたつ持つ (入次数が2である) ことだけ要求すれば，たしかにどちらが父でどちらが母かは系図作成上重要ではないかもしれない．親の一方に「男」と，もう一方に「女」とラベルをつけることで満足ならば，3項関係を持ち出すまでもない．このばあい，親子関係のグラフは《グラフ》の定義を逸脱してはいない．

同様のことは「2部グラフ」と呼ばれるグラフでも起こる．2部グラフとはたとえば互いにセックスをしたことのある男女に枝を引くようなグラフであり，もちろん《グラフ》の定義を逸脱していない．ホモセクシャルを考慮外にすれば，男同士あるいは女同士のあいだには枝がない．つまりそれぞれの点に「男」あるいは「女」とラベルをつけられるようなグラフだ．その際，男性である太朗に「女」のラベルをつけたならば，太朗とセックスしたことのある花子には「男」のラベルをつけることになる．グラフへの追加的な構造として「男集合」「女集合」といたラベルのついた集合を導入しないかぎり，性別の逆転はありうる．

追記 2 (2/7/2008).

「Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で」と書いたが，もちろん下図のように婚姻関係などを表す点をダミーとして入れれば枝の交差はなくせる．人間を表さない点が導入されるとか，入力ファイルの可読性が下がる (上がる?) といった問題を除けば，現実的な描き方かもしれない．

年明けには Ruby プログラミングをやった．去年の夏に「プログラミング教育用なんかにもいいかも」と書いたことのある ruby だけど，いま教えているオペレーションズ・リサーチの授業でじっさい ruby プログラミングをやることにした．プログラミングの経験がないという受講生が「プログラミングをやってみるいい機会」と意欲を見せたため，「じゃあ，すぐにマスターできる言語で行こう」と，急遽予定に組み入れた．

といってもボクもほとんど知らない言語だ (というか，プログラミング自体の経験も浅い) ．まずはこちらの文献集にあった，まつもとの「rubyユーザガイド」 (ちょっと古い; また，初心者である自分にはあまり分かりやすくなかった) と Chris Pine の「プログラミング入門: Rubyを使って」(大部分は初心者でも読めるだろうけど，9章の後半と10章はむずかしそう) をざっと読んだ．プログラミングをはじめてからは，その文献集の「入門編」の「サイト」にある情報や，「オブジェクト指向スクリプト言語 Ruby リファレンスマニュアル」その他を参照した．

プログラミングに出した課題はこんなタイプの問題だ: 「カップ 0, 1, 2 はそれぞれ 10, 7, 3 の容量を持つ．最初は容量10のカップに水が満杯の状態 [10, 0, 0] である．カップ i から j への水の移し替えを繰り返して，目標である [5, 5, 0]を実現したい．」この例にかんするかぎりは，9段階の移し替えで目標が達成できることが，すべての場合を網羅的に調べることで手作業で確認できる． (上述の科目で少し学ぶ) グラフ理論を知っていれば，この種の問題をプログラムで扱えるように表現するのは簡単だろう．アルゴリズムを考えることもたやすい．

それでもはじめての言語というのはいろいろと戸惑うものだ．ありがちなミスのパタンは，マニュアルと悪戦苦闘したり試行錯誤を繰り返すうちにだいたい分かって来た．で，できあがった最初のプログラムは，9段階の移し替えを実行するだけで 5 時間もかかり，10 段階以上は結果を出せなかった．そんなバカな！　「オブジェクト指向でプログラムを書いたのが悪かったんだろうか？」「再帰で関数を定義したのが悪かったんだろうか？」などと疑った．Mac OS X にはじめからインストールしてあった ruby がたまたま当たりが悪いバージョンなのかもしれないと思って，最新安定版 1.8.6 に入れ替えたり，クリスマスにリリースされたばかりの「高速」不安定版 1.9.0 を (一年近く触れていなかった) Windows PC にインストールしたりもした．だがそれらの対処法はいずれも見当違いだった．

ところでMac OS X に ruby 1.8.6 をインストールするのには，MacPorts を使った．これはボクにとっては前進だ．Unix ふうというだけでいままで毛嫌いしてたけど，やってみたらたいしたことはなかった．最初の導入は多少面倒だけど，こいつをいったんインストールしておけば，ほとんどの unix 向けソフトがコマンド 1 行でインストールできるようになる．そういうソフトとしては，pTeX, Octave, Maxima などがある．可能性が一発で広がるわけだ．こちらのサイトも参考になるだろう．MacPorts を使えるようになったのは，失敗から生まれた収穫といえるだろう．

では，なにがプログラムをそんなに遅くしていたのか？　どうやら関数の相互参照であるようだ．たとえば history(t) という関数を定義するのに history(t-1) と obtained(t-1) を参照する一方で，obtained(t-1) を定義するのに obtained(t-2) と history(t-1) を参照するようになっていた．数学的には問題はなさそうだが，おそらくプログラム的には問題になるんだろうな．history(t) の定義のなかに使われていた関数 obtained(t-1) を単なるローカル変数に置き換えた．するとそれまで5時間かかってもできなかった計算が，1秒程度でできるようになった！　やれやれ．

「関数を変数に置き換えた」とあっさり書いている．「そんなに簡単にできるならはじめから変数で書けばいい」と思うだろう．実際そのとおりなんだろうけど，これは慣れあるいは経験の問題かもしれない．[以下，インデント部分に修正を加えた．追記参照．] たとえば 1 から 10 の整数 i を合計するプログラムでは s = s + i などと書いて，右辺の値の左辺の変数への代入を表すけど，数学ではふつうそうはやらない．添字をつけて s_i = s_i-1 + i とするか，関数にして s(i) = s(i-1) + i とやりたくなるわけだ．添字をつけて何段階目の更新かというのをはっきりさせるわけだ．そういう癖にしたがって書いたプログラムが (メモリを浪費せず，かつ素早く) 自然に動いてくれたほうが都合いいと思ってるアマチュアプログラマはけっこういるかもしれない．

ところで数の合計といえば，はじめに s = 0 と設定して(1..10).each do |i| とやるのがただしいが，ボクがはじめのころ書いたプログラムには (1..10).each do |i| と書いたあとに s = 0 とする類いの初歩的なミスがあった．(これだと合計は 55 ではなく 10 になってしまう．) さすがに合計を求めるだけのプログラムではそういうミスはしないだろうけど，ループとか条件が何重かにネストする，より複雑なプログラムだと，意外とおかしてしまうミスかもしれない．

それにしても「おまじない」の類いをほとんど記述せずにプログラムが書けるのは気持ちいい．できたプログラムは普通に書くアルゴリズムよりもむしろ簡単かも．たとえば (?) 上記の水移し問題 (油移し問題) のインスタンスである abura にたいする結果を表示する---より具体的にはその履歴 history(t) を t = 0 から t = 12 まで表示する---には，以下のように書けばいい:

(0..12).each do |t|
p abura.history(t)
end

追記 (1/10/2008). あまりにも単純すぎてポイントが伝わらなかった例を差し替えた．以下は修正前の記述．「プログラムでは x = x + 1 と書いて，右辺の値の左辺の変数への代入を表すけど，数学ではふつうそうはやらない．わざわざ添字をつけて x_t = x_t-1 + 1 とするか，関数にして x(t) = x(t-1) + 1 とやりたくなるわけだ．(この例は簡単すぎるので説得力ないけど，もっとむずかしくなると添字をつけて何段階目の更新かというのをはっきりさせた方が分かりやすくなる例は少なくないはずだ．)」

年末が遠い過去に思える．

年末はなにをしたっけ．ニトリで L 型デスクを買って部屋に入れた．ネットショッピングで買ったレース調遮音カーテンと書棚4つを部屋に導入し，古い机と書棚は「物置」に移動した．部屋は書斎ぽくなった．でも箱詰めして押し入れに入れてあった本 (といっても箱はふたがしてないものが大部分だったので，すぐ見れるようにはなっていた) を書棚に移したらすぐいっぱいになった．本というのは場所を取るものだ．

その前は竹内外史『集合とはなにか』と篠田らの『集合・位相演習』(サイエンス社)の集合論の後半 (6-10章) をざっと読んで，今年書く予定のペーパーに必要な知識というか直観を仕入れた．「直観を仕入れる」って言い方はヘンってのはおいとこう．無限上昇列があるからといって無限下降列がとれるわけでないことは，たとえば自然数の全体 ω を考えれば分かるだろう．一般読者としては，「一般の順序集合で，ある要素の前に無限上昇列があるからといって，その要素から始まる無限下降列が存在するとはいえない」ことを知っておけば十分だろう．たとえば，どんな (たとえ非可算でも) 《順序数》をとっても，無限下降列は作れない．順序数ってのは自然数の概念を拡張した集合で，たとえば ω・2 = ω + ω = {0, 1, 2, 3, ..., ω, ω +1, ω+2, ω+3, ...} のように ω のコピーをふたつ用意して，最初のコピーの次に2番目のコピーを並べたものは順序数だ (2 のコピーをω回ならべた 2・ωとはべつ)．ω +1 以前に無限個要素があるけど，ω +1 から始まる無限下降列は作れない．ほかにも ω・ω = ω² のように ω, ω・2, ω・3, ω・4, ... のリミットに来る順序数もある．ω³, ω⁴, ... のリミットである ω^ω もある (ノーテーションは同じだけど，ω^ω は ω から ω への関数の集合とはべつもの)．ω^ωω もある．これらの操作によって，バカでかい無限の「数」が作れると思うかもしれないが，それらはせいぜい加算個の要素しか持たない「小さな」順序数だ．だからより大きな順序数を作る操作も必要で，たとえば実数の濃度に対応する最初の順序数というのを考えることができる．順序数はいくらでも大きくできるが，その部分列で減少するものを作れば必ず有限個で終わるのだ．

休み前には今年教える可能性の高い MBA プログラム向けの「経済分析」にむけて，伊藤元重の『ビジネスエコノミクス』 なんかも読んでみた．すぐ読めてすぐ忘れるたぐいのものだけど，副読本には悪くないかも．流通業界の話とかするには抽象的プレーヤーを持ち出すよりも，イオンとかセブンイレブンとかプレーヤーが具体的なほうが一般人には受けるんだろうな．

つづく