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

プログラミングの基礎 (Computer Science Library) (単行本)プログラミングの入門に適した言語は何かという問いに唯一の具体的な答えというものはありません。多くの大学では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のアルゴリズム」では簡単すぎてあまり勉強にならないことを確認してみましょう。

グラフ用のパッケージとデータを読み込みます。

Needs["Combinatorica`"];
nodes = Import["http://www.unfindable.net/material/metro/nodes.csv", 
   CharacterEncoding -> "UTF8"];
edges = Import["http://www.unfindable.net/material/metro/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[First /@ nodes];
MapIndexed[(id[#1] = First@#2) &, names];

隣接行列を作り、グラフにします。

matrix = Table[Infinity, {Length@nodes}, {Length@nodes}];
Scan[(matrix[[id@#[[1]], id@#[[2]]]]
     = matrix[[id@#[[2]], id@#[[1]]]] = #[[4]]) &, edges];
g = FromAdjacencyMatrix[matrix, EdgeWeight];

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

search[start_, goal_] := ShortestPath[g, id@start, id@goal]

path = search["渋谷", "護国寺"];

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

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

経路長を求めます。

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

length@path

9.8

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

おまけ(グラフの描画)

せっかくなので、絵を描いてみましょう。駅名を全部表示すると見にくくなるので、最短経路の始点と終点、路線を3つ以上持つ駅を表示することにします。

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

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

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

sPlot@path

sPlot[search["渋谷", "護国寺"]]