「最長片道切符」を算出することについてのメモ

Ruby Linux

このところ探索問題を続けて解いて（迷路、エイト・クイーン）、ふと「最長片道切符」が気になった。僕は「最長片道切符」のことを、多くの人と同じであろう、宮脇俊三氏の『最長片道切符の旅』で知った。試しに「最長片道切符」でぐぐってみると、興味深い記事が色いろ見つかる。例えば、検索上位に出てくる
最長片道切符ルートの変遷1961-2018
のサイトなど、圧倒される。また、ルート探索ついては
‚d‚w‚b‚d‚k‚É‚æ‚éÅ’·•Ð“¹ƒ‹[ƒg’Tõ
や
http://www.swa.gr.jp/lop/index.html
などがあって、つい読みふけってしまう。

というので思ったのだが、JR路線で「最長片道切符」のルートを求めるとして、実際に問題になるのは本州だろう。北海道と九州はやさしい。で、その方法として、ごくふつうの「バックトラック法」で求めるという記事がないのだが（※追記　いや、「総当り」というのがそれかな）。簡単にしかぐぐっていないので実際はあるかも知れない。とにかく、本州は入口と出口が明確に決っているので、バックトラックで充分簡単に求められそうなのだけれど。条件は、ノードとなる駅だけ選び、盲腸線はカットしておいて、

  • 分岐は（そこから進んできた枝を除き）すべてを選択
  • 出口についたらそれはひとつの解
  • 既に通った駅は選択できない
  • 出口以外で行き詰まったら戻る

で、入口から出口までのすべての片道解が求められる筈である。あとは解のすべてについて距離数を計算すればいい。

この方法で現実的な時間内でできないだろうか？　たぶんできそうなのだけれどね。やってみたいなあ。でも、データを作るのが面倒。誰かネットに CSV か何かでアップしていないかしらん。
→と思ったら本当に存在しました。ここのページからダウンロードできます。すばらしい（ありがとうございます！）。最新のデータかどうかは知らないが、これで遊べるではないか。


とりあえず、盲腸線をカットするためのコード。

edges = open("edgeshon.csv", &:readlines).map {|x| x.chomp.split(",")}
nodes = edges.inject([]) {|ar, x| ar << x[1]; ar << x[2]}
h = Hash.new(0)
nodes.each {|i| h[i] += 1}
h.select {|k, v| v == 1}.each_key do |k|
  edges.select! {|x| x[1] != k and x[2] != k}
end
open("rosen_honshu.csv", "w+") do |io|
  edges.map {|x| io.puts x.join(",")}
end

路線の数は347。始点は中小国、終点は小倉。
　
　

路線網を Graphviz で出力してみる

Graphviz のインストールは $ sudo apt-get install graphviz でOK。RubyGem は Gviz を使う。

こんな感じ。

　
コード。

require 'bundler/setup'
require 'gviz'
require 'csv'

edges = CSV.read("rosen_honshu.csv")
stations = {}
name = {}
edges.each do |e|
  e1 = e[1].intern
  e2 = e[2].intern
  stations[e1] ||= []
  stations[e1] << e2
  stations[e2] ||= []
  stations[e2] << e1
  
  name[e1] = e[6].split("→")[0]
  name[e2] = e[6].split("→")[1]
end

gv = Gviz.new
gv.graph do
  global layout: :neato
  edges arrowhead: :none
  stations.each_pair do |k, v|
    route k => v
    node k, label: name[k]
  end
end

gv.save(:rosen, :png)

　
分岐。

{:"37"=>[:"38"], :"38"=>[:"37", :"39", :"55"], :"39"=>[:"38", :"41"], :"55"=>[:"38", :"56", :"57"], :"41"=>[:"39", :"44"],
 :"44"=>[:"41", :"45", :"47", :"48", :"61"], :"45"=>[:"44", :"46"], :"47"=>[:"44", :"46", :"48", :"50"], :"48"=>[:"44", :"47", :"50"],
 :"61"=>[:"44", :"60", :"62"], :"46"=>[:"45", :"47"], :"50"=>[:"47", :"48", :"51", :"51", :"62"], :"51"=>[:"50", :"50", :"52", :"63", :"380"],
 :"62"=>[:"50", :"61", :"65"], :"52"=>[:"51", :"53", :"63", :"118"], :"63"=>[:"51", :"52", :"65", :"66"], :"380"=>[:"51", :"118"],
 :"53"=>[:"52", :"66"], :"118"=>[:"52", :"362", :"380"], :"66"=>[:"53", :"63", :"67", :"71", :"72", :"362"], :"56"=>[:"55", :"57"],
 :"57"=>[:"55", :"56", :"58"], :"58"=>[:"57", :"60"], :"60"=>[:"58", :"61", :"64"], :"64"=>[:"60", :"65", :"113"],
 :"65"=>[:"62", :"63", :"64", :"67"], :"113"=>[:"64", :"70", :"114"], :"67"=>[:"65", :"66", :"68"], :"71"=>[:"66", :"72", :"73"],
 :"72"=>[:"66", :"70", :"71", :"74"], :"362"=>[:"66", :"118"], :"68"=>[:"67", :"70"], :"70"=>[:"68", :"72", :"113"],
 :"73"=>[:"71", :"74", :"78"], :"74"=>[:"72", :"73", :"75", :"115"], :"78"=>[:"73", :"76", :"119"], :"75"=>[:"74", :"76", :"79"],
 :"115"=>[:"74", :"95", :"116"], :"76"=>[:"75", :"78"], :"79"=>[:"75", :"80"], :"119"=>[:"78", :"85", :"120"], :"80"=>[:"79", :"81"],
 :"81"=>[:"80", :"83"], :"83"=>[:"81", :"85"], :"85"=>[:"83", :"86", :"90", :"119"], :"86"=>[:"85", :"87", :"139", :"140", :"159"],
 :"90"=>[:"85", :"89", :"91"], :"87"=>[:"86", :"88", :"89"], :"139"=>[:"86", :"138", :"140", :"141"], :"140"=>[:"86", :"139", :"141", :"156"],
 :"159"=>[:"86", :"88", :"160"], :"88"=>[:"87", :"89", :"159"], :"89"=>[:"87", :"88", :"90", :"92", :"98"], :"92"=>[:"89", :"91", :"93"],
 :"98"=>[:"89", :"100"], :"91"=>[:"90", :"92"], :"93"=>[:"92", :"94"], :"94"=>[:"93", :"95"], :"95"=>[:"94", :"96", :"115"],
 :"96"=>[:"95", :"97", :"108"], :"97"=>[:"96", :"104"], :"108"=>[:"96", :"107", :"109"], :"104"=>[:"97", :"103", :"105"],
 :"100"=>[:"98", :"103", :"193"], :"103"=>[:"100", :"102", :"104"], :"193"=>[:"100", :"192", :"194"], :"102"=>[:"103", :"196"],
 :"196"=>[:"102", :"197", :"201"], :"105"=>[:"104", :"106", :"201"], :"106"=>[:"105", :"107"], :"201"=>[:"105", :"196", :"202"],
 :"107"=>[:"106", :"108", :"112"], :"112"=>[:"107", :"111", :"117"], :"109"=>[:"108", :"110", :"111"], :"110"=>[:"109", :"111", :"116"],
 :"111"=>[:"109", :"110", :"112", :"117"], :"116"=>[:"110", :"114", :"115", :"117"], :"117"=>[:"111", :"112", :"114", :"116"],
 :"114"=>[:"113", :"116", :"117"], :"120"=>[:"119", :"125", :"138"], :"125"=>[:"120", :"123", :"127"], :"138"=>[:"120", :"136", :"139", :"143"],
 :"122"=>[:"123", :"126"], :"123"=>[:"122", :"125"], :"126"=>[:"122", :"127", :"133"], :"127"=>[:"125", :"126", :"129"],
 :"133"=>[:"126", :"130", :"134"], :"129"=>[:"127", :"130", :"136"], :"130"=>[:"129", :"131", :"133", :"135"], :"136"=>[:"129", :"135", :"137",
 :"138", :"145"], :"131"=>[:"130", :"134"], :"135"=>[:"130", :"136", :"137"], :"134"=>[:"131", :"133"], :"137"=>[:"135", :"136", :"148"],
 :"145"=>[:"136", :"146", :"148"], :"148"=>[:"137", :"145", :"147", :"153"], :"143"=>[:"138", :"141", :"142", :"144"],
 :"141"=>[:"139", :"140", :"142", :"143", :"150"], :"156"=>[:"140", :"152", :"157", :"158"], :"142"=>[:"141", :"143", :"150"],
 :"150"=>[:"141", :"142", :"152"], :"144"=>[:"143", :"146"], :"146"=>[:"144", :"145", :"147", :"149"], :"147"=>[:"146", :"148", :"149"],
 :"149"=>[:"146", :"147", :"151"], :"153"=>[:"148", :"151", :"154", :"165", :"166"], :"151"=>[:"149", :"152", :"153"],
 :"152"=>[:"150", :"151", :"156"], :"154"=>[:"153", :"155", :"166"], :"165"=>[:"153", :"164", :"173", :"179"],
 :"166"=>[:"153", :"154", :"167", :"173"], :"155"=>[:"154", :"157", :"169"], :"157"=>[:"155", :"156", :"158"], :"169"=>[:"155", :"168"],
 :"158"=>[:"156", :"157", :"160", :"163"], :"160"=>[:"158", :"159", :"163"], :"163"=>[:"158", :"160", :"164", :"192"],
 :"164"=>[:"163", :"165", :"177"], :"192"=>[:"163", :"184", :"193"], :"177"=>[:"164", :"175", :"178"], :"173"=>[:"165", :"166", :"174"],
 :"179"=>[:"165", :"178", :"180"], :"167"=>[:"166", :"168"], :"168"=>[:"167", :"169"], :"174"=>[:"173", :"175", :"175"],
 :"175"=>[:"174", :"174", :"177"], :"178"=>[:"177", :"179", :"183"], :"183"=>[:"178", :"182", :"184"], :"180"=>[:"179", :"182"],
 :"182"=>[:"180", :"183", :"185"], :"185"=>[:"182", :"184", :"186"], :"184"=>[:"183", :"185", :"192"], :"186"=>[:"185", :"187"],
 :"187"=>[:"186", :"188"], :"188"=>[:"187", :"189", :"195"], :"189"=>[:"188", :"190"], :"195"=>[:"188", :"194", :"197"], :"190"=>[:"189", :"199"],
 :"199"=>[:"190", :"198", :"200"], :"194"=>[:"193", :"195", :"197"], :"197"=>[:"194", :"195", :"196", :"198"], :"198"=>[:"197", :"199", :"204"],
 :"204"=>[:"198", :"202", :"205"], :"200"=>[:"199", :"205", :"207", :"217"], :"205"=>[:"200", :"204", :"206"], :"207"=>[:"200", :"221"],
 :"217"=>[:"200", :"206", :"216", :"218"], :"202"=>[:"201", :"204", :"208"], :"208"=>[:"202", :"211"], :"206"=>[:"205", :"217"],
 :"221"=>[:"207", :"222", :"227"], :"211"=>[:"208", :"213"], :"213"=>[:"211", :"215"], :"215"=>[:"213", :"216", :"385"],
 :"216"=>[:"215", :"217", :"219"], :"385"=>[:"215", :"384"], :"219"=>[:"216", :"218", :"220"], :"218"=>[:"217", :"219", :"222"],
 :"222"=>[:"218", :"221", :"223"], :"220"=>[:"219", :"223", :"238", :"241"], :"223"=>[:"220", :"222", :"224", :"236"],
 :"238"=>[:"220", :"239", :"250"], :"241"=>[:"220", :"246", :"384"], :"227"=>[:"221", :"229"], :"224"=>[:"223", :"225", :"226"],
 :"236"=>[:"223", :"235", :"237", :"239"], :"225"=>[:"224", :"226", :"228"], :"226"=>[:"224", :"225", :"231"], :"228"=>[:"225", :"235"],
 :"231"=>[:"226", :"230", :"232"], :"229"=>[:"227", :"230"], :"235"=>[:"228", :"234", :"236", :"242"], :"230"=>[:"229", :"231"],
 :"232"=>[:"231", :"233"], :"233"=>[:"232", :"234"], :"234"=>[:"233", :"235"], :"242"=>[:"235", :"240"], :"237"=>[:"236", :"244"],
 :"239"=>[:"236", :"238", :"240", :"244"], :"244"=>[:"237", :"239", :"245", :"248"], :"250"=>[:"238", :"249", :"251"], :"240"=>[:"239", :"242"],
 :"246"=>[:"241", :"245", :"247"], :"384"=>[:"241", :"385"], :"245"=>[:"244", :"246", :"251"], :"248"=>[:"244", :"249"],
 :"251"=>[:"245", :"250", :"252"], :"247"=>[:"246", :"252", :"254"], :"252"=>[:"247", :"251", :"253", :"257"], :"254"=>[:"247", :"255"],
 :"249"=>[:"248", :"250"], :"253"=>[:"252", :"260", :"261"], :"257"=>[:"252", :"258"], :"260"=>[:"253", :"261"], :"261"=>[:"253", :"260", :"262"],
 :"255"=>[:"254", :"256", :"285"], :"256"=>[:"255", :"258"], :"285"=>[:"255", :"284", :"286"], :"258"=>[:"256", :"257", :"259"],
 :"259"=>[:"258", :"262", :"283"], :"262"=>[:"259", :"261", :"263", :"281", :"282"], :"283"=>[:"259", :"282", :"284"], :"263"=>[:"262"],
 :"281"=>[:"262", :"282", :"290"], :"282"=>[:"262", :"281", :"283"], :"290"=>[:"281", :"291"], :"284"=>[:"283", :"285", :"288"],
 :"288"=>[:"284", :"287", :"289"], :"286"=>[:"285", :"287"], :"287"=>[:"286", :"288", :"296"], :"296"=>[:"287", :"294", :"303"],
 :"289"=>[:"288", :"291", :"294"], :"291"=>[:"289", :"290", :"292", :"292"], :"294"=>[:"289", :"295", :"296"],
 :"292"=>[:"291", :"291", :"293", :"293", :"295"], :"293"=>[:"292", :"292", :"295"], :"295"=>[:"292", :"293", :"294", :"297", :"301"],
 :"297"=>[:"295", :"298"], :"301"=>[:"295", :"300", :"302"], :"303"=>[:"296", :"302", :"305"], :"298"=>[:"297", :"299"],
 :"299"=>[:"298", :"300", :"300"], :"300"=>[:"299", :"299", :"301"], :"302"=>[:"301", :"303", :"308", :"309"], :"308"=>[:"302", :"309", :"310"],
 :"309"=>[:"302", :"308", :"311"], :"305"=>[:"303", :"306", :"315"], :"306"=>[:"305", :"313"], :"315"=>[:"305", :"314", :"317"],
 :"313"=>[:"306", :"311", :"314"], :"310"=>[:"308", :"311"], :"311"=>[:"309", :"310", :"313"], :"314"=>[:"313", :"315", :"318"],
 :"318"=>[:"314", :"317"], :"317"=>[:"315", :"318"]}

　
駅名。

{:"37"=>"中小国", :"38"=>"青森", :"39"=>"野辺地", :"55"=>"川部", :"41"=>"八戸", :"44"=>"盛岡", :"45"=>"茂市", :"47"=>"新花巻", :"48"=>"花巻",
 :"61"=>"大曲", :"46"=>"釜石", :"50"=>"北上", :"51"=>"一ノ関", :"62"=>"横手", :"52"=>"小牛田", :"63"=>"古川", :"380"=>"気仙沼", :"53"=>"岩切",
 :"118"=>"前谷地", :"66"=>"仙台", :"56"=>"大館", :"57"=>"東能代", :"58"=>"(奥)追分", :"60"=>"秋田", :"64"=>"余目", :"65"=>"新庄", :"113"=>"坂町",
 :"67"=>"羽前千歳", :"71"=>"岩沼", :"72"=>"(北)福島", :"362"=>"石巻", :"68"=>"北山形", :"70"=>"米沢", :"73"=>"いわき", :"74"=>"(北)郡山", :"78"=>"水戸",
 :"75"=>"安積永盛", :"115"=>"会津若松", :"76"=>"上菅谷", :"79"=>"新白河", :"119"=>"友部", :"80"=>"那須塩原", :"81"=>"宝積寺", :"83"=>"宇都宮", :"85"=>"小山",
 :"86"=>"大宮", :"90"=>"新前橋", :"87"=>"熊谷", :"139"=>"南浦和", :"140"=>"武蔵浦和", :"159"=>"高麗川", :"88"=>"倉賀野", :"89"=>"高崎", :"92"=>"越後湯沢",
 :"98"=>"軽井沢", :"91"=>"渋川", :"93"=>"六日町", :"94"=>"浦佐", :"95"=>"小出", :"96"=>"越後川口", :"97"=>"十日町", :"108"=>"宮内", :"104"=>"豊野",
 :"100"=>"佐久平", :"103"=>"長野", :"193"=>"小淵沢", :"102"=>"篠ノ井", :"196"=>"松本", :"105"=>"直江津", :"106"=>"犀潟", :"201"=>"糸魚川", :"107"=>"柏崎",
 :"112"=>"吉田", :"109"=>"長岡", :"110"=>"東三条", :"111"=>"燕三条", :"116"=>"新津", :"117"=>"新潟", :"114"=>"新発田", :"120"=>"我孫子", :"125"=>"成田",
 :"138"=>"新松戸", :"122"=>"松岸", :"123"=>"香取", :"126"=>"成東", :"127"=>"佐倉", :"133"=>"大網", :"129"=>"千葉", :"130"=>"蘇我", :"136"=>"西船橋",
 :"131"=>"木更津", :"135"=>"南船橋", :"134"=>"安房鴨川", :"137"=>"市川塩浜", :"145"=>"錦糸町", :"148"=>"東京", :"143"=>"日暮里", :"141"=>"赤羽",
 :"156"=>"西国分寺", :"142"=>"田端", :"150"=>"池袋", :"144"=>"上野", :"146"=>"秋葉原", :"147"=>"神田", :"149"=>"御茶ノ水", :"153"=>"品川", :"151"=>"代々木",
 :"152"=>"新宿", :"154"=>"川崎", :"165"=>"新横浜", :"166"=>"鶴見", :"155"=>"尻手", :"157"=>"府中本町", :"169"=>"浜川崎", :"158"=>"立川", :"160"=>"拝島",
 :"163"=>"八王子", :"164"=>"(横)橋本", :"192"=>"甲府", :"177"=>"茅ヶ崎", :"173"=>"東神奈川", :"179"=>"小田原", :"167"=>"浅野", :"168"=>"武蔵白石",
 :"174"=>"横浜", :"175"=>"大船", :"178"=>"国府津", :"183"=>"沼津", :"180"=>"熱海", :"182"=>"三島", :"185"=>"静岡", :"184"=>"富士", :"186"=>"掛川",
 :"187"=>"浜松", :"188"=>"豊橋", :"189"=>"三河安城", :"195"=>"辰野", :"190"=>"大府", :"199"=>"(中)金山", :"194"=>"岡谷", :"197"=>"塩尻", :"198"=>"多治見",
 :"204"=>"美濃太田", :"200"=>"名古屋", :"205"=>"岐阜", :"207"=>"河原田", :"217"=>"米原", :"202"=>"富山", :"208"=>"高岡", :"206"=>"大垣", :"221"=>"亀山",
 :"211"=>"津幡", :"213"=>"越前花堂", :"215"=>"敦賀", :"216"=>"近江塩津", :"385"=>"東舞鶴", :"219"=>"山科", :"218"=>"草津", :"222"=>"柘植", :"220"=>"京都",
 :"223"=>"木津", :"238"=>"新大阪", :"241"=>"綾部", :"227"=>"津", :"224"=>"奈良", :"236"=>"京橋", :"225"=>"王寺", :"226"=>"(和)高田", :"228"=>"八尾",
 :"231"=>"和歌山", :"229"=>"松阪", :"235"=>"天王寺", :"230"=>"多気", :"232"=>"日根野", :"233"=>"鳳", :"234"=>"杉本町", :"242"=>"今宮", :"237"=>"北新地",
 :"239"=>"大阪", :"244"=>"尼崎", :"250"=>"西明石", :"240"=>"西九条", :"246"=>"福知山", :"384"=>"西舞鶴", :"245"=>"谷川", :"248"=>"神戸", :"251"=>"加古川",
 :"247"=>"和田山", :"252"=>"姫路", :"254"=>"豊岡", :"249"=>"兵庫", :"253"=>"相生", :"257"=>"佐用", :"260"=>"上郡", :"261"=>"東岡山", :"255"=>"鳥取",
 :"256"=>"智頭", :"285"=>"伯耆大山", :"258"=>"東津山", :"259"=>"津山", :"262"=>"岡山", :"283"=>"新見", :"263"=>"茶屋町", :"281"=>"倉敷", :"282"=>"総社",
 :"290"=>"新倉敷", :"284"=>"備中神代", :"288"=>"備後落合", :"286"=>"米子", :"287"=>"宍道", :"296"=>"江津", :"289"=>"塩町", :"291"=>"福山", :"294"=>"三次",
 :"292"=>"三原", :"293"=>"海田市", :"295"=>"広島", :"297"=>"(陽)横川", :"301"=>"徳山", :"303"=>"益田", :"298"=>"宮島口", :"299"=>"岩国", :"300"=>"櫛ヶ浜",
 :"302"=>"新山口", :"308"=>"居能", :"309"=>"宇部", :"305"=>"長門市", :"306"=>"南大嶺", :"315"=>"幡生", :"313"=>"厚狭", :"310"=>"雀田", :"311"=>"小野田",
 :"314"=>"新下関", :"318"=>"小倉", :"317"=>"門司"}

　
　

「バックトラック法」で実装してみたけれど、やはり無理

ダメですな。どれくらいかかっちゃうのだろう。

lop.rb　

require 'csv'

class LOP
  class Step
    def initialize(node)
      @node = node
      @parents = []
    end
    attr_accessor :node, :parents
  end
  
  def initialize
    rosen = CSV.read("rosen_honshu.csv")
    @edges = {}
    @name = {}
    rosen.each do |e|
      e1 = e[1].intern
      e2 = e[2].intern
      @edges[e1] ||= []
      @edges[e1] << e2
      @edges[e2] ||= []
      @edges[e2] << e1
      
      @name[e1] = e[6].split("→")[0]
      @name[e2] = e[6].split("→")[1]
    end
    
    @ans = []
    @stack = [Step.new(:"37")]
  end
  
  def solve
    while (a = @stack.pop)
      @edges[a.node].each do |nxt|
        next if a.parents.include?(nxt)
        nxtstp = Step.new(nxt)
        nxtstp.parents = a.parents + [a.node]
        if nxt == :"318"
          reach(nxtstp)
        else
          @stack << nxtstp
        end
      end
    end
    @ans
  end
  
  def reach(a)
    @ans.push(a.parents + [:"318"])
  end
end

ans = LOP.new.solve
CSV.open("rosen_ans.csv", "w+") do |csv|
  ans.each {|x| csv << x}
end

　
　

距離も入れて計算してみる

とりあえず「和田山」まで求めてみる。しかし、何とメモリをバカ食いしてスワップ領域に突入。あきらめました。
　

require 'csv'

class LOP
  class Step
    def initialize(node)
      @node = node
      @parents = []
    end
    attr_accessor :node, :parents
    
    def inspect
      A.instance_variable_get(:@name)[@node]
    end
  end
  
  def initialize
    @rosen = CSV.read("rosen_honshu.csv")
    @edges = {}
    @name = {}
    @rosen.each do |e|
      e1 = e[1].intern
      e2 = e[2].intern
      @edges[e1] ||= []
      @edges[e1] << e2
      @edges[e2] ||= []
      @edges[e2] << e1
      
      @name[e1] = e[6].split("→")[0]
      @name[e2] = e[6].split("→")[1]
    end
    
    @ans = [0, nil]
    @stack = [Step.new(:"37")]
  end
  
  def solve
    while (a = @stack.shift)
      @edges[a.node].each do |nxt|
        next if a.parents.include?(nxt)
        nxtstp = Step.new(nxt)
        nxtstp.parents = a.parents + [a.node]
        if nxt == :"247" or nxt == :"252"
          reach(nxtstp) if nxt == :"247"
        else
          @stack << nxtstp
        end
      end
    end
    @ans
  end
  
  def reach(a)
    way = 0
    (ar = a.parents + [a.node]).each_cons(2) do |x1, x2|
      @rosen.each {|r| way += r[3].to_i if r[1].intern == x1 and r[2].intern == x2}
    end
    print "."
    return if @ans[0] > way
    ar = ar.map {|x| @name[x]}
    @ans = [way, ar]
    puts "\n" + @ans.inspect
  end
end

A = LOP.new
A.solve