コード晒し祭[1] 経路最適化

Google Developer Dayへの参加資格を得るべく夏休みを返上してコードを書いていた皆様お疲れ様でした。クイズの締め切りも過ぎネタばらししても良くなったようなので自分もひとさまにお見せできそうな部分のコードを晒してみようかと。

お題はこれ。

日本国内の場所のリストが与えられます。あなたはそれらをすべて通るようなルートのうち、最短時間のものを計算して、提出してください。ルートの開始点は最初に与えられる場所とし、最後にはもとの位置にもどって来て下さい。また、各地点を移動するのに必要な時間は Google Maps API の運転ルート案内で得られる秒数を使ってください。

まあ典型的な巡回セールスマン問題。ノードが10個程度なので総当たりでも組み合わせの数はたいしたことないしメモリも食うような問題じゃないので一気にがーっと書いた。

A-B間の所要時間は方向に限らず同じに違いないという誤った仮定を立てて対象行列を作ってMaps APIへのアクセス数を減らそうとしてしばらくはまった。せいぜい10x10-10のアクセスしか起きないんだから何も考えない方が良かった。

順列組み合わせのメソッドが用意されてるとか ruby便利すぎる。

#!/usr/bin/ruby
# -*- coding: utf-8 -*-

require "rexml/document"
require 'open-uri'

class Node
  attr_reader :name, :lat, :lng

  def initialize(n, lat, lng)
    @name = n
    @lat  = lat
    @lng  = lng
  end
end

class GMap

  attr_accessor :node
  attr_reader :minCost
  attr_reader :minRoute

  def initialize
    @node = Array.new
    @costMatrix = Hash.new
    @minCost  = 0
    @minRoute = nil
    alias :updateMinimumCost :updateMinimumCost0
  end

  def initNode_Q1
    @costMatrix = Hash.new
    @minCost  = 0
    @minRoute = nil

    alias :updateMinimumCost :updateMinimumCost0

    @node << Node.new("兼六園", 	36.562070, 136.662419)
    @node << Node.new("東京大学", 	35.712940, 139.759590)
    @node << Node.new("京都大学", 	35.025280, 135.780910)

  end

  def initNode_Q2
    @costMatrix = Hash.new
    @minCost  = 0
    @minRoute = nil
    alias :updateMinimumCost :updateMinimumCost0

    @node << Node.new("東京タワー", 	35.658570, 139.745484) # 0
    @node << Node.new("札幌時計台", 	43.062603, 141.353642) # 1
    @node << Node.new("通天閣", 	34.652554, 135.506333) # 2
    @node << Node.new("秋吉台", 	34.234753, 131.310094) # 3
    @node << Node.new("船の科学館", 	35.620168, 139.772157) # 4
    @node << Node.new("鈴鹿サーキット", 34.847899, 136.540862) # 5
  end

  def initNode_Q3
    @costMatrix = Hash.new
    @minCost  = 0
    @minRoute = nil
    alias :updateMinimumCost :updateMinimumCost0

    @node = Array.new([
                       Node.new("東京タワー", 		35.658570, 139.745484), #  0
                       Node.new("名古屋城",   		35.185590, 136.899060), #  1
                       Node.new("後楽園",     		34.669614, 133.933906), #  2 
                       Node.new("春日大社",   		34.681480, 135.848313), #  3
                       Node.new("佐多岬",     		30.994560, 130.660638), #  4
                       Node.new("日光東照宮", 		36.758051, 139.598899), #  5
                       Node.new("日本銀行",   		35.686839, 139.771438), #  6
                       Node.new("国会正門前",		35.676293, 139.746927), #  7
                       Node.new("天橋立駅",		35.557674, 135.182542), #  8
                       Node.new("東京ビッグサイト", 	35.629898, 139.794127)]) # 9
  end

  def getCost(n1, n2)
    # [MEMO] マトリクスは対象行列ではないことに注意。

    if @costMatrix[ [n1,n2] ]  == nil
      # 出発地と目的地の緯度・経度を指定して Maps APIを叩く
      url = 'http://maps.google.com/maps/api/directions/xml?' + 
             'origin='       + @node[n1].lat.to_s + ',' + @node[n1].lng.to_s + \
             '&destination=' + @node[n2].lat.to_s + ',' + @node[n2].lng.to_s + '&mode=driving&sensor=false'

      # XMLを解析 (例外は考えてない)
      result = open(url).read
      doc = REXML::Document.new(result)

      cost = 0
      REXML::XPath.match(doc, "/DirectionsResponse/route/leg/step/duration/value").each { |el|
        cost = cost + el.text.to_i
      }
      @costMatrix[ [n1,n2] ] = cost
      # puts "@costMatrix[ [#{n1},#{n2}] ] = #{@costMatrix[ [n1,n2] ]}"
    end

    @costMatrix[ [n1,n2] ]
  end

  def updateMinimumCost0(cost, route)
    @minCost  = cost
    @minRoute = route
    alias :updateMinimumCost :updateMinimumCost1
  end

  def updateMinimumCost1(cost, route)
    if cost < @minCost
      @minCost  = cost
      @minRoute = route
    end
  end  

end



#
# 計算ループ(総当たり式)
#
map = GMap.new

#map.initNode_Q1
#map.initNode_Q2
map.initNode_Q3

(1...map.node.length).to_a.permutation(map.node.length-1) { |route|
  route.insert 0, 0
  route.push 0

  cost = 0
  for n in 0...(route.size-1) do
    cost += map.getCost(route[n], route[n+1])
  end

  # puts "#{cost} : #{route.join(" ")}"
  map.updateMinimumCost(cost, route)
}

#
# 結果を出力
#
for n in 0...map.minRoute.size do
  print "#{map.node[ map.minRoute[n] ].name} "
end
puts ""
#puts map.minCost