Python+PULPで大阪市営地下鉄・最長一筆書き経路を求める(まとめ)
おねがい
このページの内容は大阪メトロ公式さんとは一切の関係がございません、
このページの内容について大阪メトロに問い合わせることはやめてくださいますようお願いします
記事購入のおねがい
わたくし大学生でして、調子こいて軽自動車買ったりした結果、非常に金欠です
この記事がまぁおもろいなと思った方はこの記事の「購入」項で記事を購入するかこちらのドネーションサイト ( Buy me a coffee ) でチップを送っていただけると幸いです
私の日常生活を支援していただけると幸いです…
ぶしつけなお願いですがよろしくお願いいたします…
目次
はしがき
大阪メトロから最長一筆書き経路を紹介する動画が上がっていた;
最長一筆書き経路
挑戦者求む！Osaka Metroが導き出した一筆書きの最長ルートとは！【Metro News #78】 (youtube.com)
今回はこの経路が正しいか、はたまた別の未知の経路が最長経路となるのかをPython+PULPで整数計画法を用いて確認して行こうと思う。
問題を明確に…
大阪メトロ+ニュートラムにおいて、同じ駅を2回通過しない経路のうち、距離が最長となるものを求める。
このとき、距離が同じ経路が複数ある場合は、通過する駅数が最も多いものを最長距離とする。
ただし、梅田は同じ駅を通過したとみなさないことにする。
前提
各駅間の距離は、次の表に書かれた距離で計算する;
ただしこのとき、計算量を減らすために、大国町～なんば、心斎橋～本町、心斎橋～なんばの御堂筋線・四つ橋線が重なっている区間で、片方を -9999km と設定し、最長距離の計算に含まれないようにした。
再びですが…記事購入のおねがい
この記事を面白いと思われた方は、是非この記事最後にあります"購入"項からこの記事を購入するか、Buy Me A Coffeeで一寸チップをしていただけますとありがたいです
この記事の購入…
Python+PULPで大阪市営地下鉄・最長一筆書き経路を求める(まとめ)｜boz (note.com)
Buy Me A Coffee…
Bozley (buymeacoffee.com)
結論
最長経路は次のような 77.0km の道のりであると求められた;
江坂→梅田→本町→心斎橋→なんば→西長堀→阿波座→コスモスクエア→住之江公園→大国町→動物園前→日本橋→長堀橋→谷町六丁目→谷町四丁目→堺筋本町→南森町→東梅田→天神橋筋六丁目→太子橋今市→蒲生四丁目→森ノ宮→緑橋→今里→谷町九丁目→天王寺→なかもず ( 77.0 km )
青線は大阪メトロ公式が求めた最長一筆書き経路
このとき、従来の経路と今回新たに求められた経路の異なる部分は
従来の経路: 谷町四丁目ー(谷町線)→南森町 ( 2.7km )
今回の経路: 谷町四丁目ー(中央線)→堺筋本町ー(堺筋線)→南森町 ( 1.0 km + 1.7 km )
の部分で、距離的には同じであるが、今回求められた方が通過する駅数が1駅多い。
そうだけど…?
(大阪メトロ公式さんも、ここまで求めておいて今回の経路を考え付かないわけがないので、数十メートル / 数メートル単位で計算するともしかしたら谷町四丁目ー(谷町線)→南森町の経路の方が距離的にも長いのかもしれないです)
証明
経路の問題を整数計画問題に帰着させる
たとえばこのような問題があったとする
問題;
下の図において、S地点からG地点まで線が交差しないような経路のうち、最長となるような経路は何か？
このとき、最長となるような経路は
2値変数N_iについて、ΣN_i が最大となるような経路である
ただし、このとき線が交差しないという条件を含めていないので、線が交差しないという条件を立式し、計算結果に含めていく;
線が交差しないということは、出発地・到着地以外の点(ノード)についてその点に接続する線(エッジ)が2以下であるということと同値なので、
N_0 + N_1 + N_4 <= 2
N_1 + N_2 + N_5 <= 2
…..
N_4 + N_7 + N_8 + N_11 <= 2
…
N_12 + N_15 + N_16 <= 2
という式がたてられる
ただしこのとき、出発地・到着地以外のノードに接続するエッジが1ということは、そこで経路の終点になることと必要十分なので、出発地・到着地いがいのノードに接続するエッジは1ではないことから
N_0 + N_1 + N_4 == 0 or 2
N_1 + N_2 + N_5 == 0 or 2
…
という式がたてられる
よって、上のような図において、S地点からG地点へ向かう交差しない経路のうち最長となるものは、次のような式と同値だと考えられる;
MAXIMIZE ( Σ N_i )
such as (条件として)
N_0 + N_3 == 1
N_0 + N_1 + N_4 == 0 or 2
N_1 + N_2 + N_5 == 0 or 2
….
N_4 + N_7 + N_8 + N_11 == 0 or 2
…
N_12 + N_15 + N_16 == 0 or 2
N_13 + N_16 == 1
これでめでたく、経路の問題を整数計画問題に帰着させることができた
Pythonで書く
計算上の工夫
PULPというのは線形計画問題の解を求めるようなソルバーであるため、あいにく
== 0 or 2
というような条件式を持つものは計算できないから、ちょっとした計算の工夫を行う
a,b,c,d は 0,1 を取る2値変数であるとき
a + b + c + d == 0 or 2
という式は
a + b + c + d <= 2
-a + b + c + d >= 0
a - b + c + d >= 0
a + b - c + d >= 0
a + b + c - d >= 0
という線形な式と必要十分であることに注意すると、うまいこと書ける
(これは変数が3個のときでも、あるいは5個の時でも成り立つ)
実装
これをPythonでPULPというライブラリを用いて書くと次のように表せられる;
解
計算するとこのように求められて
無事最長経路が求められた
これの各エッジに重みをもたせて、同じようにすれば大阪メトロの最長一筆書き経路も求まる…!
大阪メトロでは…?
大阪メトロでは"梅田は同じ駅(ノード)を通ったことにならない"というルールがあるために上記の方法では最長一筆書き経路を求めたことにならない、そのことについて考える
大阪メトロでは梅田は何回でも通っていいため、このような経路のパターンが考えられる、このそれぞれについて整数計画問題に帰着させればよい
経路の図
梅田に5本のエッジが接続している場合
2.梅田に4本のエッジが接続している場合
3.梅田に3本のエッジが接続している場合
なお、梅田に3本のエッジが接続しているとき、必ず梅田からもう1本エッジが引けて、梅田に3本のエッジが接続している場合よりも長くなるため、考えなくても良い
4.梅田に0本・1本・2本のエッジが接続している場合
同じような理由で考えなくても良い
それぞれを立式すると…?
1.梅田に5本のエッジが接続している場合
2.梅田に4本のエッジが接続している場合
これを 1.梅田にエッジが5本接続している場合 / 2.梅田にエッジが4本接続している場合 それぞれについて解いた結果 1.では最長経路が60kmほど、2.で先ほど見た77kmの経路になったことから、最長経路は先ほど見た77kmの経路だと求められた
このあたりは記事
Python+PULPで大阪市営地下鉄・最長一筆書き経路を求める(後編)
で詳しく解説しているので是非ご覧ください！
参考文献
この記事を書くにあたって次の記事を大いに参考しました;
特に a+b+c+d == 0 or 2 を
a+b+c+d <= 2
-a+b+c+d >= 0
a-b+c+d >= 0
a+b-c+d >= 0
a+b+c-d >= 0
と変形するのはこのサイトなしでは到底考え付かなかったと思います、
ありがとうございました
購入
この記事が面白いと感じた方はここからの有料部分を購入して支援していただけると幸いです！ 追加の情報はありませんが….
ここから先は
¥ 300
この記事が気に入ったらチップで応援してみませんか？