ブロック分割による手計算での最長片道ルート探索
２．九州
図5は九州のＪＲ路線図である。小倉−博多間の新幹線は、鹿児島本線とは別線とする解釈もあり、葛西氏はその解釈で最長ルートを算出しているが、ここでは同一路線と見做して算出することとした。
九州も北海道と同じように真ん中あたりで分割し、北九州と南九州のそれぞれで最長ルートを探すことを考える。熊本−宇土と大分−南宮崎が必ず通過しなければならない2ルートとなっているので、そこで分割することも考えられるが、そうすると南九州は単純になるが、北九州がかなり複雑なまま残ってしまう。そこで、図5の太線で示したように、その一段上の久留米−熊本、夜明−大分、城野−大分の3ルートを境に分割することにする。すると、@久留米−熊本のみ通過するケース、A夜明−大分のみ通過するケース、B城野−大分のみ通過するケース、C久留米−熊本と城野−大分のみ通過するケース、D久留米−熊本と夜明−大分のみ通過するケース、E全て通過するケースの6通りを考えれば良いことが分かる。（夜明−大分と城野−大分のみ通過するケースは成立しない。城野−大分−夜明と進んでしまうと、その後に南九州へ抜けるルートがなくなってしまう。）
図5
@久留米−熊本のみ通過するケースは図6にルートを示した。西小倉−久留米は、西小倉−城野−田川後藤寺−新飯塚−折尾−吉塚−桂川−原田−久留米というルートも長そうであるが、これは183.6kmであり、図6の西小倉−折尾−香椎−長者原−吉塚−原田−桂川−新飯塚−田川後藤寺−夜明−久留米では211.9kmになるので、こちらの方が長い。このルートの距離は1113.0km（幡生−枕崎、営業キロ）となった。
図6
A夜明−大分のみ通過するケースは図7の通り、B城野−大分のみ通過するケースは図8の通りである。ABのように南九州の基点を熊本ではなく大分とすると、大分−南宮崎−隼人−吉松−新八代−鹿児島中央−枕崎よりも図7、8のルートのように、豊肥本線を活用して大分−都城−吉松−隼人−熊本−大分とした方が、ルートが長くなる（前者は654.3km、後者は705.6km）。
また、図7では西小倉から折尾へ向かい、香椎−長者原−吉塚−原田−桂川−新飯塚−田川後藤寺−夜明とするル−ト（西小倉−夜明で172.8km、図7では同区間が222.7km）、図8では折尾から新飯塚へ向かい、桂川−長者原−香椎−原田とするルート（折尾−原田で88.3km、図8では同区間が92.2km）も計算したが、いずれも図7、8の方が長かった。
このルートの距離はAが1046.8km（幡生−大分、営業キロ）、Bが1083.6km（幡生−大分、営業キロ）となった。
図7 図8
次にC久留米−熊本と城野−大分のみ通過するケースを考える。@ABでは南九州への通過ルートを1本に限定していたため、終点が南九州内になっていたが、このケースでは南九州を循環して北九州に戻ってくるので、北九州が終点になる。今まで無視されてきた佐賀、長崎方面への道が開けることになる。
南九州は簡単だが、北九州は若干複雑である。本州から延びてきた最長ルートは関門トンネルを抜けて西小倉へ到達するが、そこで、西小倉から城野へ接続するか、久留米へ接続するかを考えなければならない。西小倉から久留米へ接続すると、南九州循環後に大分から佐賀、長崎方面に行くことができない。従って、西小倉からは城野に接続する方が、距離が伸びることが分かるだろう。
図9 図10
次に、南九州循環後に熊本から久留米まで来た所でルートが2つに分かれるが、どちらへ向かった方が長くなりそうか微妙である。そこで、夜明へ向かうケース（図9）と鳥栖へ向かうケース（図10）を分けて考えることにした。夜明へ向かうケースでは、夜明−田川後藤寺−新飯塚までは1本道であるので、本州から九州へ入ってきた際の西小倉から城野への接続ルートは自ずと直線ルートに限定されることが分かる。鳥栖へ向かうケースでは、鳥栖から佐賀、長崎方面に行くことが明白なので、本州から九州へ入ってきた際の西小倉から城野への接続ルートは筑豊地区をなるべく遠回りした方が良いことが分かる。
このルートの距離は、図9が1195.4km（幡生−肥前山口、営業キロ）、図10が1142.3km（幡生−肥前山口、営業キロ）となったので、Cとしては図9の1195.4km（幡生−肥前山口、営業キロ）が最長ということになる。
D久留米−熊本と夜明−大分のみ通過するケースは図11の通りである。Cとは異なり、熊本から久留米に来た時に、久留米−夜明ルートが通過できないので、自動的に久留米から鳥栖へ向かうことになり、Cのような場合分けは必要ない。このルートの距離は1126.6km（幡生−肥前山口、営業キロ）となった。
図11
E全て通過するケースは、Cと同様に場合分けが必要である。まず、大分から夜明へ来た時に久留米へ向かう（図12）か、田川後藤寺に向かうかによって場合分けをする。さらに夜明−田川後藤寺と進んだ場合には、田川後藤寺から城野へ向かう（図13）か、新飯塚へ向かう（図14）かで再度場合分けを行う必要がある。
図12
図13 図14
このルートの距離は、図12が1077.9km（幡生−大分、営業キロ）、図13が1081.6km（幡生−大分、営業キロ）、図14が1088.8km（幡生−大分、営業キロ）となったので、Eとしては図14の1088.8km（幡生−大分、営業キロ）が最長ということになる。
以上の結果により、@1113.0km 、A1046.8km 、B1083.6km 、C1195.4km、D1126.6km、E1088.8kmであるから、結局、Cが最長ルートとなることが分かった。やはり、佐賀、長崎方面を切り捨てると距離が伸びないのである。
このように、最長ルートを求める上でのポイントは、ブロック分割して、場合分けしながらブロック毎に最長ルートを求めることである。
なお、ブロック分割する場所が、2ルートだと、2C1+2C2=2+1＝3通り、3ルートだと、3C1+3C2+3C3=3+3+1＝7通りの場合分けが必要である。ブロック分割するとブロック毎の最長ルートは簡単に求まるが、4ルート以上の箇所で分割すると、逆に場合分けの方が大変になる。4ルートで4C1+4C2+4C3+4C4=4+6+4+1＝15通り、5ルートだと5C1+5C2+5C3+5C4+5C5=5+10+20+5+1＝41通りの場合分けが必要となる。
（注：nCk （ｎ個からｋ個を選ぶ組合せ数）= n(n-1)…(n-k+1)/k(k-1)…1)
←前のページ 目次 次のページ→
Copyright(c) 2005 KONDO Hideaki All rights reserved.
初版： 2005年2月12日