Python+PULPで大阪市営地下鉄・(距離)最長一筆書き経路を求める(中編)

試行錯誤

1回目 問題発生

制約条件もようやく入力し終えたことだから、さっそく計算してみる。すると結果はこんな感じになった

画像はノードを含むか含まないかの数値
1回目の計算結果は、求めたい条件でないものも含んでいた

このルートはつまり、

中百舌鳥→天王寺→動物園前→コスモスクエア→阿波座→本町→梅田→天六→太子橋今市→大日

と進むような経路と、

それに交わらない環状の経路

を選べ！と言ってて、求めたい経路とは程遠い経路が出てきてしまっていた

ΣSi = 2 ( i ∈ 終着駅) かつ Sj = 0,2 (j ∈ 分岐駅) というのは
求めたいような経路と実は必要十分ではなかった

実はここでいれた制約条件

ΣSi = 2 ( i ∈ 終着駅)
Sj = 0 or 2 ( j ∈ 分岐駅) 

という条件は、

終着駅 ～ 終着駅　の経路 x 1
上の経路と交わらない環状の経路 x 1

という経路も含んでしまい、それが変な経路が出て来る原因になったのだ…!

(上の図から逆算してもらえばわかるが、上の図は確かに終着駅を2つ含み (= ΣSi = 2 ( i ∈ 終着駅 ) を満たし)、分岐駅から出るノードがすべて0,2である ( = (Sj = 0 or 2 ( j ∈ 分岐駅 ) を満たす))

1回目 対応

どうすれば正しい経路が出て来るか？それはその環状の経路が含まれないように制約条件を1回1回追加していけばよい
この場合はこの環状の経路上のノードすべてが1でなければよいということであるから・・・

Σ Ni ( i ∈ 環状のノード ) ≠ Ni の本数

という条件を付けくわえてあげればよい。

ただしここで、PuLPでは != ができないから

Σ Ni ( i ∈ 環状のノード) ≦ Ni の本数

としてやればよい。

PuLP に起こすとこのようになる:

環状のノードを無理やり条件指定して除こうとしている

気を取り直して、再度計算してみよう！

2回目 ～ 4回目

また終着駅～終着駅の経路と、それに交わらない環状の経路が出てきてしまった。1回目と同じようにして、この経路が結果に出ないようにする

終着駅～終着駅の経路と、それに交わらない環状の経路が
出てこないような条件を追加した

5回目 問題点

ようやく終着駅～終着駅を一筆書きで結ぶような経路が出てきた！これによると

中百舌鳥→天王寺→動物園前→大国町→住之江公園→コスモスクエア→阿波座→本町→堺筋本町→谷町四丁目→森ノ宮→谷町六丁目→長堀橋→心斎橋→西長堀→なんば→日本橋→谷町九丁目→今里→緑橋→長田

という経路が最長になるという計算結果である。しかし・・・？

というのも今里から

今里→緑橋

と進むより、

今里→蒲生四丁目→太子橋今市→井高野

などなど進む方が絶対により長い経路移動できそうなのである

どこかにミスがないかと探してみると….

第1項すべてにマイナスの符号がついてしまっている

ここで第1項すべてにマイナスの符号がついてしまっていたのだ

これを修正してまたまた計算してみよう

第数十回

あまたもの環状経路を取り除く試みと、あまたものプログラミングのバグとの死闘を戦い抜いて得られた結果がこれである:

江坂→梅田→天六→太子橋今市→蒲生四丁目→緑橋→今里→谷町九丁目→谷町六丁目→森ノ宮→谷町四丁目→南森町→堺筋本町→長堀橋→心斎橋→なんば→西長堀→阿波座→コスモスクエア→住之江公園→大国町→動物園前→天王寺→中百舌鳥
を結ぶ　76.8 km　の道のり…

最長距離は76.8km
これは既知の一筆書き経路78.9kmより確かに短いのである…!

という結果が返ってきた！

意気揚々と大阪メトロの動画と見比べてみると…?

大阪メトロの動画内で紹介されていた78.9kmの道のりは
確かに一筆書き経路になっていて、この計算結果より長い

なんとこの動画内で紹介されていた経路の方がこの計算結果より3kmほどではあるが長かったのである….！

果たして正解にたどり着くことはできるのか…？

引用元;

ヘッダー画像 … KishujiRapid - 投稿者自身による著作物, CC 表示-継承 4.0, https://commons.wikimedia.org/w/index.php?curid=59099290による