（【その１】 からの続き）
4. 最長片道経路の算出
4-1. 最長片道経路の算出に用いるコード(スクリプト)
最長片道経路の特定に用いるコードは以下の二つ。
JNOT様のコード（ https://note.com/jnot/n/nd2c9469e4fd8 ）
■探索エリアにおける最長片道経路の始点と終点を求めるコード
■探索される経路はいわゆる「L型」のルート（そのため、「P型」「O型」のルートの確認作業が必要）
■途中経路は表示されない
Psyduck様のコード（ https://psyduck-take-it-easy.hatenablog.com/entry/2018/06/17/222824 ）
■始点・終点を指定するとその間の最長一筆書き経路を提示してくれるコード
（Psyduck様が公開しているコードにも、探索エリアにおける最長片道経路(経路タイプはL型/O型/P型を問わない)を見つけるコードがあると思われるのですが、現段階で私は使いこなせていません。）
最長片道きっぷ - 問題の分析
「(最長片道経路の)経路タイプのL型/O型/P型って何？」というお話については上記リンクをご参照ください。2000年にJR全線の最長片道経路を求められた葛西隆也さんのHPです。
スルッとKANSAIの最長片道経路を求めるに当たっては、1.→2.の順にコードを回していくことになる。（1.のコードで経路の始点と終点を特定し、2.のコードでその経路を確認する。）
しかしながら、スルッとKANSAIの「必要駅間データセット」には、最長片道経路の始点駅/終点駅となる候補が346駅あり、このまま愚直に1.のJNOT様のコードを実行すると計算不可となる可能性が高い。
※346駅の始点/終点候補がある時、候補経路数は ${}_{346} C_2 = 59685 $ 通り
4-2. スルッとKANSAI 最長片道経路特定のための工夫
最長片道経路探索において、計算量が膨大になる場合*の主な対処方法としては、探索エリア内を複数の領域に分割して経路を探索する方法が挙げられる。（*60,000通り程度の計算ができないというのは私のPCスペックの問題かもしれないが...。）
今回は、上記のエリア分割による対処ではなく、
「有力候補を見つけ、それが最長であることを証明する方法」
によりスルッとKANSAIの最長片道経路を特定していく。
4-3. スルッとKANSAI 最長片道経路の"有力候補"
| 区間 | 距離 | |
|---|---|---|
| 1 | 大和八木〜伊勢中川〜近鉄名古屋 | $152.9 km$ |
| 2 | 大和八木〜伊勢中川〜賢島 | $140.1 km$ |
| 3 | 岸里玉出〜紀ノ川〜加太 | $67.3 km$ |
| 4 | 板宿〜飾磨〜山陽網干 | $58.4km$ |
上記の路線図と表を見ると、今回の探索エリア内においては、近鉄名古屋線を含む「近鉄名古屋〜伊勢中川〜大和八木」の距離が長く、この区間を含むルートがスルッと"KANSAIの最長片道経路"ではないかという見当をつけることが出来る。
そこで、JNOT様のコードを「発駅候補を近鉄名古屋のみ」として実行、まずは345通りの経路のみ距離を求めてみる。
| 順位 | 最長片道経路の候補 | 経路の距離 |
|---|---|---|
| 1 | 近鉄名古屋〜加太 | $633.0km$ |
| 2 | 近鉄名古屋〜山陽網干 | $619.2km$ |
| 3 | 近鉄名古屋〜吉野 | $617.2km$ |
以上の実行結果から、 スルッとKANSAIの最長片道経路は「$近鉄名古屋～加太：633.0km$」ではないか？ という候補を見つけることが出来た。
4-4. "有力候補"が最長であることの証明
前節で見つけたスルッとKANSAI 最長片道経路の"有力候補"を、下記の方法で「最長である。」と証明する。
<１> 今回最長経路探索を行うスルッとKANSAI有効エリアの路線を以下の２種類に分ける。
⑴ 閉じた経路を構成できる路線
⑵ 盲腸線
「盲腸線」 とは、起点もしくは終点のどちらかが他の路線に接続していない行き止まりの路線のこと。路線網の中であたかも盲腸（虫垂）のように見えることからこのように俗称される。
盲腸線の例(起点/終点のどちらかが他路線に接続していない行き止まり路線)：わたらせ渓谷線
<２> “未知の最長片道経路”には、次の不等式が成り立つ。
“有力候補（$近鉄名古屋〜加太：633.0km$）”よりも長い距離の"未知の最長片道経路"を考える。ここで、“未知の最長片道経路”には、次の不等式が成り立つ。
この不等式について分かりやすく図示すると下図のようになる。
fig.1の図において、
⑴ 閉じた経路を構成できる路線 は 紫色の路線
⑵ 盲腸線 は 水色の路線
である。
このとき、fig.1中央の図に赤線で示された"未知の最長経路"は、fig.1右側の図に赤線で示された"(⑴の路線距離の総計)+(⑵から選択した２路線の距離)"より短い。
<３> "未知の最長片道経路"を探す方向性は以下の通り。
<１>と<２> を踏まえると、“有力候補（$近鉄名古屋〜加太：633.0km$）”に対抗出来る “未知の最長片道経路” となる可能性があるのは 「⑴閉じた経路を構成できる路線区間をより長く+⑵盲腸線区間では近鉄名古屋or加太を外した選択」 した経路。
※またここで、『「⑴の中をより長く」した距離は、「⑴の路線距離の総計」よりは短い。』ということも言える。
<４> "未知の最長片道経路"は盲腸線区間を何km経由すれば良いかを確認。
上記の確認のために、まず“有力候補（$近鉄名古屋〜加太：633.0km$）”の内訳を確認する。“有力候補（$近鉄名古屋〜加太：633.0km$）”の経路は以下の通り分解ができる。
| 分類 | 区間 | 距離 |
|---|---|---|
| (2)盲腸線区間 | 近鉄名古屋〜大和八木 | $152.9km$ |
| (2)盲腸線区間 | 岸里玉出〜加太 | $67.3km$ |
| (1)閉じた経路を構成できる路線区間 | 大和八木〜岸里玉出 | $412.8km$ |
“有力候補（$近鉄名古屋〜加太：633.0km$）”の盲腸線区間である２区間の距離の合計は $152.9km + 67.3km =220.2km$ 。
一方、スルッとKANSAIエリア内の (1)閉じた経路を構成できる路線 の路線距離の総計は「 $610km$ 」であるため、(1)内で更に延ばせる可能性がある距離は
$610−412.8.9=197.2km$
つまり、(1)内で延ばしうる距離は$197.2km$であることを踏まえた上で、更に $
23.0km+α$ の距離(※※)を盲腸線区間で稼ぐ必要がある。
(※※)$23.0km=220.2km−197.2km$ 。実際には、最長片道経路において(1)内の通過経路を$197.2km$ 延ばすことは不可能である(∵<3>の※)ため、盲腸線区間で稼ぐ必要がある距離は「$23.0km+α$」となる。
<５> 「$23.0km+α$」の距離を稼げる可能性のある盲腸線区間候補を調べる。
スルッとKANSAIエリア内で比較的長い距離があり、目標とする「$23.0km+α$」を稼げる可能性がある区間（始点/終点のどちらかに必ずなる駅の候補）は以下の通り。
山陽網干/高野山/粟生/吉野/鞍馬/ウッディタウン中央/大阪阿部野橋/ケーブル延暦寺(計８駅)
“未知の最長片道経路”における始点/終点駅の候補
上記の８駅に近鉄名古屋と加太の２駅を加えた、計１０駅を「スルッとKANSAIの最長片道経路における発駅」の候補とし、
$10*346=3460$ 通り
の経路の距離を求め、「スルッとKANSAIの最長片道経路」を確定させる。
4-5. スルッとKANSAI の最長片道経路の特定
前節4-４の<５>で「スルッとKANSAIの最長片道経路」候補とした3460通りについて、距離が長いTop10の経路と距離は以下の通りとなる。
以上より、スルッとKANSAIの最長片道経路は 「$近鉄名古屋～加太：633.0km$」 と分かった。
最後に、「近鉄名古屋〜加太」の最長片道経路を 2.Psyduck様のコード（ https://psyduck-take-it-easy.hatenablog.com/entry/2018/06/17/222824 ）で確認する。
5. スルッとKANSAIの最長片道経路 ※
スルッとKANSAIの最長片道経路 「$近鉄名古屋～加太：633.0km$」 は以下の通り。
近鉄名古屋→近鉄長島→桑名→益生→耳成→大和八木→八木西口→畝傍御陵前→橿原神宮前→橿原神宮西口→高田市→尺土→磐城→駒ヶ谷→古市→喜志→汐ノ宮→河内長野→千代田→白鷺→中百舌鳥→新金岡→昭和町→天王寺→四天王寺前夕陽ヶ丘→谷町九丁目→日本橋→恵美須町（日本橋筋）→動物園前（新世界）→大国町→住之江公園→コスモスクエア→弁天町→九条→ドーム前→桜川→大阪難波→大阪上本町→鶴橋→今里（近鉄）→布施→河内永和→石切→生駒→菜畑→黒田→田原本→石見→ファミリー公園前→平端→筒井→尼ヶ辻→大和西大寺→平城→伏見→竹田→上鳥羽口→十条（近鉄）→東寺→京都→五条→四条→烏丸御池→京都市役所前（河原町御池）→蹴上→御陵→山科→石田→六地蔵→桃山南口→観月橋→中書島→淀（京都競馬場）→石清水八幡宮→橋本→御殿山→枚方市→枚方公園→古川橋→門真市→西三荘→野江→京橋→蒲生四丁目→鴫野→緑橋→森ノ宮→玉造→谷町六丁目→谷町四丁目→天満橋→南森町→東梅田→中崎町→天神橋筋六丁目→都島→千林大宮→太子橋今市→守口→大日→南摂津→沢良宜→南茨木→宇野辺→万博記念公園→山田→南千里→下新庄→淡路→崇禅寺→南方→十三→中津（阪急）→大阪梅田→杭瀬→大物→尼崎→尼崎センタープール前→武庫川→鳴尾・武庫川女子大前→久寿川→今津→西宮→青木→魚崎→住吉→春日野道→三宮→元町→西元町→高速神戸→新開地→湊川→鵯越→鈴蘭台→北鈴蘭台→箕谷→谷上→新神戸→神戸三宮→芦屋川→夙川→西宮北口→門戸厄神→宝塚→雲雀丘花屋敷→川西能勢口→池田→石橋阪大前→蛍池→柴原阪大前→少路→千里中央→桃山台→梅田→淀屋橋→北浜→堺筋本町（船場東）→長堀橋→心斎橋→西大橋→西長堀→阿波座→本町→四ツ橋→難波→今宮戎→萩ノ茶屋→天下茶屋→岸里玉出→粉浜→加太
伊勢中川から西に向かってコスモスクエアまで行き、折り返して奈良・京都に向かうなど、行程が途中で何度かクロスする経路になっているのが面白い。（経路がクロスするのは、後述の通り、"別名だが乗り換えができる駅"を別駅扱いのままとしている影響。）
6. スルッとKANSAIの最長片道経路を更に延ばす
さて、ここまでで求めてきた「スルッとKANSAIの最長片道経路」だが、【その１】の準備作業において"孤立線を他路線に接続"した以外は「別名だが乗り換えができる駅」の考慮はしなかった。
この、「別名だが乗り換えができる駅」を考慮すると、「スルッとKANSAIの最長片道経路」は $633.0km$ から更に延ばすことが出来る。
次回「スルッとKANSAIエリアの最長片道経路を求める 【その３】」では、「別名だが乗り換えができる駅」を考慮した『スルッとKANSAI"真の"最長片道経路』を求めていく。