集合知プログラミング　5.1 5.2 5.3　最適化

ruby book 集合知プログラミング

集合知プログラミング

集合知プログラミング

今回もサンプルコード(python)から、Rubyへの書き換えに挑戦しました。
目標は一応サンプルコードに忠実にです。
5章の5.1から5.3までの、コスト関数の所までを書いてみました。
出版社から配布されているサンプルコードに間違いがいくつかあり苦労しました。

サンプルコードの正誤

PCI_Code\PCI_Code Folder\chapter5\optimization.pyの32,33行目

　　# サンプルコードのコード
    out=flights[(origin,destination)][int(r[d])]
    ret=flights[(destination,origin)][int(r[d+1])]

    # 正しいコード
    # *2を忘れている
    out=flights[(origin,destination)][int(r[d*2])]
    ret=flights[(destination,origin)][int(r[d*2+1])]

この後も、同じような箇所がいくつかあり、すべて書き換えます。
その他には69行目の演算子が逆でした。
まだまだ、間違っている所はあると思います。


ちなみに、本には正しいコードで書かれています。
ですので、サンプルコードをそのまま実行せず、本の通りに修正すれば問題ないです。

今回作成したプログラム

今回もいつもの通り、"optimization.rb"と名付けました。
フライトデータファイルはここのものを利用します。

http://kiwitobes.com/optimize/schedule.txt

#!/usr/bin/ruby
require 'date'
require 'time'

$people = [
  ['Seymour', 'BOS'],
  ['Franny','DAL'],
  ['Zooey','CAK'],
  ['Walt','MIA'],
  ['Buddy','ORD'],
  ['Les','OMA']
]

# ニューヨークのラガーディア空港
$destination='LGA'

$flights=[]

# テキストファイルから配列に格納
ifh = open('schedule.txt', 'r')
lines = ifh.readlines
for line in lines do
  line_sp=line.strip().split(/\s*,\s*/)
    $flights << [
	line_sp[0],
	line_sp[1],
	line_sp[2],
	line_sp[3],
	line_sp[4].to_i
    ]
end	
	
module Optimization
　# 時刻を分に直す関数
  def self.getminutes(t)
    # 文字列から日付オブジェクトに変換
    x = Time.parse(t)
    return x.hour * 60 + x.min
  end

  def self.printschedule(r)
    # 人数を割り出す
    ran_r = r.length / 2
    d = 0
    ran_r.times {|d|
	# 名前を取り出す
	name = $people[d][0]
	#　出発地を取り出す
	origin = $people[d][1]
	#　配列から行きの便を取り出す
	out_list = $flights.select{ |f|
	  f[0] == origin && f[1] == $destination
	}
	out = out_list[r[d*2]]
	#　配列から帰りの便を取り出す
	ret_list = $flights.select{ |f|
	  f[0] == $destination && f[1] == origin
	}
	ret = ret_list[r[d*2+1]]
	print name, " ",
            origin, " ",
            out[2], "-", out[3], " ",
            "$", out[4], " ",
            ret[2], "-", ret[3], " ",
            "$", ret[4], "\n"
    }
  end
  
  #コスト関数
  def self.schedulecost(sol)
    totalprice=0
    latestarrival=0
    earliestdep=24*60
    
    sol_r = sol.length / 2
    sol_r.times {|d|
      #　行きと帰りのフライトを得る
      origin = $people[d][1]
      #　配列から行きの便を取り出す
      outbound_list = $flights.select{ |f|
        f[0] == origin && f[1] == $destination
      }
      outbound = outbound_list[sol[d*2]]
      #　配列から帰りの便を取り出す
      returnf_list = $flights.select{ |f|
	f[0] == $destination && f[1] == origin
      }
      returnf = returnf_list[sol[d*2+1]]
      
      # 運賃総額Total price は出立便と帰宅便すべての運賃
      totalprice+=outbound[4]
      totalprice+=returnf[4]
      
      # 最も遅い便と最も早い便を記録
      if latestarrival<getminutes(outbound[3])
        latestarrival=getminutes(outbound[3])
      end
      if earliestdep>getminutes(returnf[2])
        earliestdep=getminutes(returnf[2])
      end
    }  
    
    # 最後の人が到着するまで全員で待機
    # 帰りも空港にみんなで来て自分の便を待つ
    totalwait=0
    sol_r.times {|d|
      #　行きと帰りのフライトを得る
      origin = $people[d][1]
      #　配列から行きの便を取り出す
      outbound_list = $flights.select{ |f|
        f[0] == origin && f[1] == $destination
      }
      outbound = outbound_list[sol[d*2]]
      #　配列から帰りの便を取り出す
      returnf_list = $flights.select{ |f|
	f[0] == $destination && f[1] == origin
      }
      returnf = returnf_list[sol[d*2+1]]
      
      # それぞれ待ち時間を足し合わせて、総待ち時間を算出する
      totalwait+=latestarrival - getminutes(outbound[3])
      totalwait+=getminutes(returnf[2]) - earliestdep     
    }  
    
    # レンタカーの追加料金が必要なら50ドル追加
    if latestarrival<earliestdep
      totalprice+=50
    end
    
    return totalprice+totalwait
  end
end

確認

irbで確認

irb(main):001:0> load 'optimization.rb'
=> true
irb(main):002:0> s=[1,4,3,2,7,3,6,3,2,4,5,3]
=> [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]
irb(main):003:0> Optimization.schedulecost(s)
=> 4585
irb(main):004:0> Optimization.printschedule(s)
Seymour BOS 8:04-10:11 $95 12:08-14:05 $142
Franny DAL 10:30-14:57 $290 9:49-13:51 $229
Zooey CAK 17:08-19:08 $262 10:32-13:16 $139
Walt MIA 15:34-18:11 $326 11:08-14:38 $262
Buddy ORD 9:42-11:32 $169 12:08-14:47 $231
Les OMA 13:37-15:08 $250 11:07-13:24 $171
=> 6

補足

getminutes関数

ある時刻が一日の中で何分目かを出す関数です。
時間計算をしたいので、引数で入ってきた文字列を日付オブジェクトに変換します。
strptimeがうまく使えず、今回はTime.parseを使いました。
しかし、もっといい方法がないかなと思っています。

メンバー毎のフライトの割り出し

Integerクラスのtimesメソッドを用いました。
これはブロック内を指定回数だけ実行します。
カウンタも使うことができます。

「初めてのRuby」では6.3.6イテレータで紹介されています。

初めてのRuby

初めてのRuby

この処理は同じような所が何回も出てくるので、関数でまとめてもよかったかもしれません。

結果の出力（printメソッド）

サンプルコードでは、文字列整形して出力していたのですが
自分ではうまくいかず不格好な感じになってしまいました。

フライト便の取り出し

メンバーの乗るフライト便は、テキストファイルから配列に格納し検索します。
サンプルコードでは、出発地・目的地をキーにその他の項目を格納していました。
Rubyで同じような方法が見つからず、とりあえず全部を配列に格納しました。
この配列の0番目には出発地が、1番目には目的地があるので
それをキーに検索しさらに配列にいれ、そこから解の表現のリストと照らしあわせました。
その配列要素の検索には、Array.selectを用いました。


とりあえず動くものができたという感じです。
pythonの配列やハッシュについて勉強する必要がありそうです。