経路探索: 京都の鉄道乗り換え案内
気付いたんですが、MzScheme って日本語を変数名にできるんですね。
> (define 梅田 'erika) > (cond ((memq 梅田 '(erika aka ageko)) => caddr) (else 'sageko)) ageko
なぜ気付いたかと言いますと、探索アルゴリズムの勉強のために、鉄道のルート探索のプログラムを作っていたんです。
最初は駅名をアルファベットのシンボルで表していたんですが、読み方が分からない駅名があったり、とにかく手作業で書き換えるのがあまりに面倒なので、じかに日本語でやってみたら出来た、というわけです。
まだ仮の段階ですが、路線は次のような形式で定義しています:
(define-railway '阪急京都本線 '((梅田 大阪) 十三 南方 崇禅寺 淡路 上新庄 相川 正雀 南茨木 茨木市 総持寺 富田 高槻市 上牧 水無瀬 大山崎 長岡天神 西向日 東向日 洛西口 桂 西京極 西院 大宮 (烏丸 四条) 河原町))
始点から終点までの駅名を順に並べることで（どっち側を始点にしても良いです）、隣接する駅（ノード）間が接続されるような仕組みです。
ここで、(梅田 大阪) のようなリスト形式のノードは他路線との接続を表すことになっています (cdr 部 が他路線の駅リスト)。
梅田駅を例に取ってみると、次のように Lisp のプロパティー・リストに似た感じで情報が引き出せるようになっています:
> (node-get '梅田 'adjacent) (十三) > (node-get '梅田 'alias) (大阪) > (node-get '梅田 'line) (阪急京都本線)
京都はこんな感じです:
> (node-get '京都 'adjacent) (東寺 丹波口 西大路 九条 五条) > (node-get '京都 'line) (近鉄京都線 ＪＲ嵯峨野線 ＪＲ山陰本線 ＪＲ京都線 京都市営地下鉄烏丸線)
全体として、駅を表すシンボルと、それに関連付けられたリストによってネットワークが表現されています。
経路の探索は、現在の経路の終端駅の adjacent および alias の情報を引き出して目的地かどうかを調べる、そうでなければさらに先へ進む、という方法で行うことになります。
例えば、梅田駅から石庭で有名な龍安寺に行くルートを考えると、最初は
(梅田)
という経路から始めるわけです。この時点での終端である梅田駅の隣接駅を
(node-get '梅田 'adjacent)
として調べ、(十三) というリストを得ます。'龍安寺 と等しいものがあるかをチェックし、見あたらないので、経路を
(梅田 十三)
のように延ばします。
これを再帰的に行っていくわけですが、次の
(node-get '十三 'adjacent)
は (梅田 南方) を返すので、梅田に引き返して永久ループになってしまわないよう注意する必要があります。
このような計算を行う汎用的な探索関数が次のように書けました:
(define (graph-search start goal? next) (define new-paths (path-finder next)) (define (search paths) (if (pair? paths) (let* ((path (car paths)) (node (car path))) (if (goal? node) (cons (reverse path) (search (cdr paths))) (search (append (new-paths node path) (cdr paths))))) '())) (search (list (list start)))) (define (path-finder next) (lambda (node path) (if (null? path) '() (map (cut cons <> path) ;; `remove' as defined in SRFI-1 (remove (cut memq <> path) (or (next node) '()))))))
深さ優先で経路を探索し尽くす、という関数です。
路線検索の場合、最短経路を求めることが必ずしも目的ではありません。急行・特急に乗り継ぐことを考えると途中の駅の数はあまり関係なくなってくるからです。また、後から乗り換え回数や料金といった条件で最適なものを選択できるように、とにかく洗いざらい調べる方針にしました。
なお、graph-search の次の部分
(append (new-paths node path) (cdr paths))
の append の引数を入れ替えることで、幅優先探索 (最初に最短経路が見つかるアルゴリズム) になります。
path-finder は補助関数で、既に訪れたノードに後戻りしないようにします。したがって、graph-search を呼び出す側は、既に訪れたかどうかは気にせずに、与えられたノードに隣接するノードを返せば良いわけです。
次のように呼び出します:
(graph-search '梅田 (lambda (x) (eq? x '龍安寺)) (lambda (x) (append (or (node-get x 'alias) '()) (node-get x 'adjacent))))
graph-search の第 3 引数の関数で、隣接する、あるいは乗り換え可能な駅のリストを返しています。このように関数によってグラフ (ネットワーク) を抽象化することによって、グラフ構造自体はハッシュ表であれ連想リストであれ、自由に表現して良いことになります。
ただ、実際にこの呼び出しによってルートを計算してみると、
(梅田 大阪 新大阪 ... 龍安寺)
という、人間であれば有り得ないルートも出力されてしまいます（阪急梅田駅に行って、一駅も乗らずに出て、JR大阪駅に乗り換える、なんてことは有り得ないわけです）。
そんな問題も考慮した検索関数が以下です:
(define (search-routes start end) (define (next start) (let ((unalias (or (and-let* ((alias (node-get start 'alias))) (lambda (l) (remove (cut memq <> alias) l))) identity))) (lambda (node) (unalias (append (node-plist node 'alias) (node-plist node 'adjacent)))))) (define goal? (let ((goals (cons end (node-plist end 'alias)))) (lambda (node) (memq node goals)))) (mapconcat (lambda (start) (graph-search start goal? (next start))) (cons start (node-plist start 'alias)))) (define (node-plist node prop) (or (node-get node prop) '())) (define (mapconcat f l) (apply append (map f l)))
分かりにくいと思いますが、出発駅の alias は経路から外す処理を加えてあります。
さらに、乗り換えの計算を加えて、乗り換え回数の少ない順に上位３ルートを出力してみた結果は次のようになりました:
> (search-routes '梅田 '龍安寺) (阪急京都本線) 梅田 十三 南方 崇禅寺 淡路 上新庄 相川 正雀 南茨木 茨木市 総持寺 富田 高槻市 上牧 水無瀬 大山崎 長岡天神 西向日 東向日 洛西口 桂 西京極 西院 (嵐電嵐山本線) 西院 西大路三条 山ノ内 蚕ノ社 太秦広隆寺 帷子ノ辻 (嵐電北野線) 帷子ノ辻 常盤 鳴滝 宇多野 御室仁和寺 妙心寺 龍安寺 Stations: 34 Changes: 2 (阪急京都本線) 梅田 十三 南方 崇禅寺 淡路 上新庄 相川 正雀 南茨木 茨木市 総持寺 富田 高槻市 上牧 水無瀬 大山崎 長岡天神 西向日 東向日 洛西口 桂 (阪急嵐山線) 桂 上桂 松尾 嵐山 (嵐電嵐山本線) 嵐山 嵐電嵯峨 鹿王院 車折神社 有栖川 帷子ノ辻 (嵐電北野線) 帷子ノ辻 常盤 鳴滝 宇多野 御室仁和寺 妙心寺 龍安寺 Stations: 35 Changes: 3 (ＪＲ京都線) 大阪 新大阪 東淀川 吹田 岸辺 千里丘 茨木 摂津富田 高槻 島本 山崎 長岡京 向日町 西大路 京都 (京阪本線) 五条 四条 (阪急京都本線) 烏丸 大宮 西院 (嵐電嵐山本線) 西院 西大路三条 山ノ内 蚕ノ社 太秦広隆寺 帷子ノ辻 (嵐電北野線) 帷子ノ辻 常盤 鳴滝 宇多野 御室仁和寺 妙心寺 龍安寺 Stations: 31 Changes: 4
実際にこれが正しいルートかどうかは確認していませんが、出発駅として梅田を指定しているにも関わらず大阪からのルートも計算されているところに、上述の工夫の結果が表れています。
もう一つ、極端な例を:
> (search-routes '梅田 '十三) (阪急京都本線) 梅田 十三 Stations: 2 Changes: 0 (ＪＲ京都線) 大阪 新大阪 東淀川 吹田 岸辺 千里丘 茨木 摂津富田 高槻 島本 山崎 長岡京 向日町 西大路 京都 (京阪本線) 五条 四条 (阪急京都本線) 烏丸 大宮 西院 西京極 桂 洛西口 東向日 西向日 長岡天神 大山崎 水無瀬 上牧 高槻市 富田 総持寺 茨木市 南茨木 正雀 相川 上新庄 淡路 崇禅寺 南方 十三 Stations: 41 Changes: 2 (ＪＲ京都線) 大阪 新大阪 東淀川 吹田 岸辺 千里丘 茨木 摂津富田 高槻 島本 山崎 長岡京 向日町 西大路 京都 (ＪＲ嵯峨野線) 京都 丹波口 二条 (京都市営地下鉄東西線) 二条 二条城前 烏丸御池 (京都市営地下鉄烏丸線) 烏丸御池 四条 (阪急京都本線) 烏丸 大宮 西院 西京極 桂 洛西口 東向日 西向日 長岡天神 大山崎 水無瀬 上牧 高槻市 富田 総持寺 茨木市 南茨木 正雀 相川 上新庄 淡路 崇禅寺 南方 十三 Stations: 44 Changes: 4
一駅隣に行くのにぐるっと京都を巡ってくる、というルートが色々楽しめます。ちなみに最長ルートはこうなりました:
(ＪＲ京都線) 大阪 新大阪 東淀川 吹田 岸辺 千里丘 茨木 摂津富田 高槻 島本 山崎 長岡京 向日町 西大路 京都 (ＪＲ嵯峨野線) 京都 丹波口 二条 (京都市営地下鉄東西線) 二条 二条城前 烏丸御池 京都市役所前 三条京阪 東山 蹴上 御陵 山科 東野 椥辻 小野 醍醐 石田 六地蔵 (京阪宇治線) 六地蔵 桃山南口 観月橋 中書島 (京阪本線) 中書島 伏見桃山 丹波橋 墨染 藤森 深草 伏見稲荷 鳥羽街道 東福寺 七条 五条 四条 (阪急京都本線) 烏丸 大宮 西院 (嵐電嵐山本線) 西院 西大路三条 山ノ内 蚕ノ社 太秦広隆寺 帷子ノ辻 有栖川 車折神社 鹿王院 嵐電嵯峨 嵐山 (阪急嵐山線) 嵐山 松尾 上桂 桂 (阪急京都本線) 桂 洛西口 東向日 西向日 長岡天神 大山崎 水無瀬 上牧 高槻市 富田 総持寺 茨木市 南茨木 正雀 相川 上新庄 淡路 崇禅寺 南方 十三 Stations: 80 Changes: 8
京都周辺の路線しか登録していないのでこの程度で済んでいますが、規模を拡大していくともっとひどい事になります。
ここにアルゴリズムを差し替えたりする余地があるわけなんですが、空間的効率の観点から、深さ優先探索はそのままにしておきたいところです。幅優先にしてしまうと、最初に最短経路が見つかるという利点があるものの、同時に保持しなければならない経路の数が膨大になってしまうからです。
そこで、優先順位を付けて探索する方法を思いつきました。全ての駅について緯度・経度の情報を用意し、目的地に近い方向を優先的に選ぶ、という方法です。あるいは、優先順にソートするよりも、関係なさそうな方向は選択肢から省く方法が良いかもしれませんね。
大変そうなので今のところ実装する気はないです。
参考文献:
Paul Graham. "ANSI Common Lisp", Chapter 3.
Peter Norvig. "Paradigms of Artificial Intelligence Programming", Chapter 6.
Gerald Jay Sussman et al. Adventures in Advanced Symbolic Programming, Assignment 6. (MIT の Sussman 先生のクラスの講義資料)
