TraveringSalesman問題とは
とあるセールスマンが本社から[1, 2, 3, 4]の御宅を回って本社に戻る．どの順番で行けば一番距離が短くて済む？という問題です．
実装（街の個数が12個以上だと処理が終わらないよ...）
とりあえずコードをぺたり．
traveling_salesman.rb
require 'numo/gnuplot'
class Array
def swap(idx1,idx2)
temp = self.dup
temp[idx1],temp[idx2] = temp[idx2],temp[idx1]
temp
end
def swap!(idx1,idx2)
self[idx1],self[idx2] = self[idx2],self[idx1]
self
end
end
class TravelingSalesman
def initialize(points_count)
puts "sales_points_count: #{points_count}"
@order_sales_points = mk_random_points(points_count) # the component is {id: Int, x_point: Float, y_point: Float}
@points_for_gnuplot = []
end
def execution
result_order_sales_points = @order_sales_points.clone
add_points_for_gnuplot(result_order_sales_points.clone)
standard_energy = energy(order_points: @order_sales_points)
puts "first standard_energy: #{standard_energy}"
exchanges = mk_exchange_in_hash(@order_sales_points, 1, @order_sales_points.size-2)
exchanges.each do |order_item|
=begin
print 'order_item: '
order_item.each do |item|
print "#{item[:id]}, "
end
=end
@order_sales_points[1..@order_sales_points.size-2] = order_item
compared_energy = energy(order_points: @order_sales_points)
# print "energy: #{compared_energy}, "
if standard_energy > compared_energy
# puts "\t\tresult update"
result_order_sales_points = @order_sales_points.clone
add_points_for_gnuplot(result_order_sales_points.clone)
standard_energy = compared_energy
else
# puts "\t\tnot update"
end
end
result_order_sales_points.each do |item|
puts "min_distance_order_sales_points: #{item[:id]}"
end
puts "standard_energy: #{standard_energy}"
gnuplot
end
def add_points_for_gnuplot(hashes)
@points_for_gnuplot << [[], []]
hashes.each do |hash|
@points_for_gnuplot.last[0] << hash[:x_point]
@points_for_gnuplot.last[1] << hash[:y_point]
end
end
def gnuplot
points = @points_for_gnuplot
Numo.gnuplot do
set output: 'traveling_salesman_gnuplot.gif'
set term: 'gif', animate:true, delay:15, size:[500,500]
set :nokey
set size: {ratio: 1.0}
set xrange: 0..1
set yrange: 0..1
unset :colorbox
set palette_defined:'(0 "white", 1 "green")'
points.each do |item|
plot item[0], item[1], w: :lp, pt: 6
end
end
end
def mk_exchange_in_hash(hashes, from_index, to_index)
exchanges = []
count = 0
first_array_nums = []
count_in_same_first_array_num = 1
for i in 0...(to_index - from_index)
count_in_same_first_array_num *= (to_index - 1 - from_index - i + 1)
end
hashes[from_index..to_index].permutation(to_index - from_index + 1) do |item|
first_array_nums << item[0][:id] if count % count_in_same_first_array_num == 0
exchanges << item if !first_array_nums.include?(item.last[:id])
count += 1
end
exchanges
end
def distance(point0, point1)
tmp = Math.sqrt((point0[0] - point1[0])**2 + (point0[1] - point1[1])**2)
return tmp
end
def energy(order_points: [{id: Int, x_point: Float, y_point: Float}])
tmp = 0.0
for i in 0..order_points.size-2 do
tmp+=distance([order_points[i][:x_point], order_points[i][:y_point]],
[order_points[i+1][:x_point], order_points[i+1][:y_point]])
end
return tmp
end
def mk_random_points(size)
order_points = []
for item in 0...size
order_points << {id: item, x_point: rand(10).to_f/10, y_point: rand(10).to_f/10}
end
order_points << order_points[0]
order_points
end
end
puts 'Please input city count'
get_count = STDIN.gets.chomp.to_i
traveling_salesman = TravelingSalesman.new(get_count)
traveling_salesman.execution
TravelingSalesmanクラスの概要
- initializeでセールスマンが巡回する街の個数Nを受け取ります．
- 街の情報を{id: Int, x_point: Float, y_point: Float}の形にすると考えます．
- 全ての街の情報をidの小さい順に配列(order_sales_points)に追加します．（僕はorder_sales_pointsの配列の要素0から要素N-1までを巡回のルートとして考えました）
- order_sales_pointsの巡回ルートの距離を求めてstandard_energyに代入します．energyメソッド使用．
- order_sales_pointsの各要素の全組み合わせを[ [{id: 1}, {id: 2}, ], [id: 1}, {id: 3}, ], [id: 1}, {id: 4}, ]...]の様な形で取得してexchangesに代入します．mk_exchange_in_hashメソッド使用．
- exchangesの各要素の巡回ルートの距離を求めてより小さい値を取る組み合わせを結果として更新していきます．
- exchangesの全要素の距離を比べて，一番小さい値をとったルートを答えとしました．
視覚的にもわかりやすい様にgnuplotで表示させる．
このコードを実行しようとしてくれてる方はgnuplotが必要です．
その方法は以下のサイトにまとめがありますので，ご覧ください．
ちなみにgem install gnuplotもある様ですが，バージョンが古いのか機能しなかったので添付しているURLの通りにhomebrewでgnuplotをインストールすることを推奨します．
gnuplotをインストールし終えた方は，gem install numo-gnuplotでnumo-gnuplotをインストールしてください．
以上でこのTravelingSalesmanクラスを実行できるはずです！
ちなみこんなgifに仕上がった
