メトロネットワーク最短路問題 (Mathematica)

プログラミングの入門に適した言語は何かという問いに唯一の具体的な答えというものはありません。多くの大学ではC言語を使っているでしょう。MITのように関数型言語を使う例もあります（その教科書SICP）。基本的にはなんでもいいと私は思います。オブジェクト指向でしか書けないような言語は、思考を制限してしまう危険があるのでちょっと躊躇しますが、取り返しがつかないというほどではないでしょう。

関数型で入門したい（させたい）けれど、SICPは本格的すぎるという向きには、浅井健一『プログラミングの基礎』（サイエンス社, 2007）がいいかもしれません。使用言語は関数型言語OCamlですが、プログラミング言語ではなくプログラミングを学べるように書かれています。

でも、ちょっと引っかかるところがあったので、そのことについて書いておきます。

プログラミング言語について学ぶのであれば、Javaなどのオブジェクト指向言語、あるいはCやPascalといった命令型言語を思い浮かべる方が多いと思います。それらを使わずに、あえて関数型言語であるOCamlを選ぶのには理由があります。それはOcamlが「単純、かつ強力である」からです。

単純ということはすなわち簡単ということです。OCamlでプログラムを作るのは、JavaやCで作るよりもずっと簡単です。それは、より人間の思考レベルに近い記述ができるからです。さらに、プログラムの記述量が違います。OCamlで書いたプログラムと同じことをするプログラムをJavaやCで書こうとすると、ほとんどの場合、コード量にして10倍以上になります。JavaやCを使っていたのでは、初学者が短期間のうちにメトロネットワーク最短路問題を解くプログラムを作るのはほぼ不可能でしょう。(p.3)

プログラミング言語について学ぶのであれば、Javaなどのオブジェクト指向言語、あるいはCやPascalといった命令型言語、OCamlのような関数型言語を思い浮かべる方が多いと思います。それらを使わずに、あえてマルチパラダイム言語であるMathematicaを選ぶのには理由があります。それはMathematicaが「単純、かつ強力である」からです。

単純な言語がいつも簡単だというわけではありませんが、Mathematicaは簡単です。Mathematicaでプログラムを作るのは、JavaやC、OCamlで作るよりもずっと簡単です。それは、より人間の思考レベルに近い記述ができるからです。さらに、プログラムの記述量が違います。Mathematicaで書いたプログラムと同じことをするプログラムをJavaやC、OCamlで書こうとすると、ほとんどの場合、コード量にして数倍になります。JavaやC、OCamlを使っていたのでは、初学者が短期間のうちにメトロネットワーク最短路問題を解くプログラムを作るのはほぼ不可能でしょう。

プログラミングを学ぶ際に、言語の選択は本質的なことではないと思います。よいプログラミング言語とその言語にあった題材があればいいのです。

C言語なら、題材に「グラフの実装」を選ぶのは正解でしょう。きっといろんなことを学べます。しかし、題材に「Dijkstraのアルゴリズムの実装」を選ぶと、初学者は挫折してしまうかもしれません。

OCamlなら、題材に「Dijkstraのアルゴリズムの実装」を選ぶのは正解でしょう。この本はきっと正解です。逆に、「グラフの実装」だけではあまり勉強にならないかもしれません。

Mathematicaなら、グラフもDijkstraのアルゴリズムも実装済みなので、もっと先に進むことができます。生産性を上げるためにはベクタやリストのような基本的なコンテナが準備されていなければなりません。同じことがグラフ（とグラフに関するアルゴリズム）にも言えます。そのような期待に応えているMathematicaでは、「Dijkstraのアルゴリズム」では簡単すぎてあまり勉強にならないことを確認してみましょう。

グラフ用のパッケージを読み込んでおきます。

<< Combinatorica`

適当な作業ディレクトリに移動し、データを読み込みます。

SetDirectory@"作業ディレクトリ";
nodes = Import["nodes.csv", CharacterEncoding -> "UTF8"];
edges = Import["edges.csv", CharacterEncoding -> "UTF8"];

データはこの本のサポートサイトのコードmetro.mlから取りました（データはその言語特有の形式でなく、CSVなどのような一般的な形式で用意した方がいいと思います）。ちなみに、OCamlの完成版はコードex21_3.mlです。

データファイルnodes.csvはこんな感じです。

代々木上原,よよぎうえはら,yoyogiuehara,千代田線
代々木公園,よよぎこうえん,yoyogikouen,千代田線
明治神宮前,めいじじんぐうまえ,meijijinguumae,千代田線
...

データファイルedges.csvはこんな感じです（4列目が距離、5列目が時間だそうです）。

代々木上原,代々木公園,千代田線,1,2
代々木公園,明治神宮前,千代田線,1.2,2
明治神宮前,表参道,千代田線,0.9,2
...

駅名のリスト。

names = Union[Map[First, nodes]];

駅名を数字に変換するためのルール。

id = Table[names[[i]] -> i, {i, 1, Length@names}];

隣接行列。

aMatrix = Table[Infinity, {Length@nodes}, {Length@nodes}];
Map[(aMatrix[[#[[1]] /. id, #[[2]] /. id]] = 
     aMatrix[[#[[2]] /. id, #[[1]] /. id]] = #[[4]]) &, edges];

グラフ。

g = FromAdjacencyMatrix[aMatrix, EdgeWeight, Type -> Undirected];

最短経路は関数ShortestPathで求められる。ノードの番号のリストで返る結果を駅名に変換し、経路長を計算する。

search[station1_, station2_] := ShortestPath[g, station1 /. id, station2 /. id]

テスト1：search["渋谷", "護国寺"]

{20, 92, 136, 80, 39, 59, 100, 114, 97}

駅名。

Map[names[[#]] &, path]

{"渋谷", "表参道", "青山一丁目", "永田町", "麹町", "市ヶ谷", "飯田橋", "江戸川橋", "護国寺"}

経路長。

length[path_] := 
 Fold[{#2, #1[[2]] + aMatrix[[#1[[1]], #2]]} &, {First@path, 0}, Rest@path][[2]]

length@path

9.8

テスト2：search["茗荷谷", "目黒"]

{90, 61, 100, 59, 39, 80, 116, 138, 124, 118, 83, 24}

Map[names[[#]] &, path]

{"茗荷谷", "後楽園", "飯田橋", "市ヶ谷", "麹町", "永田町", "溜池山王", "六本木一丁目", "麻布十番", "白金高輪", "白金台", "目黒"}

length@path

12.7

というわけで、最短経路探索はMathematicaなら簡単です。先に進まなければなりません。たとえば、経路探索で重要なのは、距離ではなく時間です。メトロネットワークにおいては、やっかいなことに、駅間の移動にかかる時間は一定ではありません。そのあたりも考慮することにすれば、Mathematicaにとってのいい題材になるでしょう。

おまけ（グラフの描画）

せっかくなので、絵を描いてみましょう。駅名を全部表示すると見にくくなるので、路線を3つ以上持つ駅に注目するようにします。

hubStations = First /@ Select[Tally[Flatten[Take[#, 2] & /@ edges]], #[[2]] > 2 &]

{"表参道", "国会議事堂前", "霞ヶ関", "日比谷", "大手町", "北千住", "上野", "三越前", "日本橋", "銀座", "溜池山王", "赤坂見附", "青山一丁目", "永田町", "九段下", "茅場町", "池袋", "後楽園", "四ツ谷", "中野坂上", "市ヶ谷", "飯田橋"}

最短経路の始点と終点、hubStationsに含まれる駅の駅名を表示することにします。

label[path_, id_, position_] := 
 Text[If[MemberQ[path, id] && 
    Or[id == First@path, id == Last@path, 
     MemberQ[hubStations, names[[id]]]], names[[id]], ""], position]

グラフは関数GraphPlotで描きます。

stationPlot[path_] := 
 GraphPlot[g, 
  VertexRenderingFunction -> ({Gray, Point@#1, Black, 
      label[path, #2, #1]} &)]

テスト1の結果はstationPlot[search["渋谷", "護国寺"]]で描けます。

テスト2の結果はstationPlot[search["茗荷谷", "目黒"]]で描けます。