経路の探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/01 00:14 UTC 版)
古い時代に行われた最長片道切符旅行の行程は、手計算で立案したルート構成を総当たり的に検討した結果得られたものであり、実際の算出作業は非常な困難を極めた。 1961年の東大旅行研究会のルート探索では、全国を地域ブロックに分割し、メンバーが各ブロックごとの最長ルートを求め、これを合算するという手法がとられた。北海道と九州は、青森と下関を通る単一ルートに限られるため本州から切り離して計算できた。本州についても列島方向に走る鉄道線が少ない地域で切断し、4ブロックに分割して計算している。しかし彼らの探索したルートは東京都内で旅規第70条に定める特定区間の扱いに見落としがあり、実際には最長ルートではなかったことが前述の通り後に判明している。 1970年代中期以降は、光畑茂が手計算により最長片道ルートを探索し続け、種村直樹の著書などを介して定期的に改訂内容が公表されていたことから、愛好者の間で広く利用された。宮脇俊三も『最長片道切符の旅』の中で、自力でも手探りで経路を確定させようとする様子を綴っているが、最終的には光畑ルートを利用することになった。この光畑ルートは近年の研究で、間違いない最長片道ルートだったことが数学的に証明されている。 1980年代以降は、コンピュータを利用した数的解析を用いて最長行程を算出する試みが始まっている。古くは1970年代に報告がある。当初は、ブロック分けによる総当り法が主流だった。なおしばしば俗に「一筆書き」と表現されるが、実際にはグラフ理論の視点からは、駅を「節」、線路を「辺」とすると、同じ辺を2度通らないが同じ節は何度通ってもよいオイラー路である「一筆書き」ではなく、同じ節を2度通らないハミルトン路のほうが「片道切符ルート」には似ている。 数的解析の一例として、2000年当時東京大学大学院生だった葛西隆也は、整数計画法を用い、数学的に厳密に最長を求めたと言える手順で経路（稚内→肥前山口、11,925.9キロ）を求めた。このルートは、肥前山口側で環状線を形成しており、逆経路は前述のルールの「環状線一周を超えない」に抵触するため不可となっている。同年春に、とある研究会で整数計画法によるものと並行して実施した全探索による手法の詳細を発表したところ、好評で、費用を提供するので是非乗ってきてほしいという複数の同志があり、同年夏に実際にこの経路を旅行した。その経路の探索過程と旅行記は、ウェブページに掲載されている。探索手法と実際に乗車して記録を発表したことなどが評価され、情報処理学会のプログラミング・シンポジウムで山内奨励賞を受賞した。なお、2004年のNHKの番組もルート計算はこの方法を使用し、九州新幹線開業後に改めて計算を東大のある研究室に依頼し実施したうえで放送された。 コンピュータを利用した経路の探索は、近年のコンピュータのスペック向上により、年々容易になっている。
※この「経路の探索」の解説は、「最長片道切符」の解説の一部です。
「経路の探索」を含む「最長片道切符」の記事については、「最長片道切符」の概要を参照ください。
- 経路の探索のページへのリンク
