Rubyで巡回セールスマン問題

Tweet

Pocket

Rubyで巡回セールスマン問題を解こうと思いプログラミングをしてみました。
とりあえず、難しいことは考えずに、単純な方法でやってみました。
以下、アルゴリズムと言うにはあまりに単純な方法。

1. すべての経路をリストアップ
2. それぞれの経路のコストを計算
3. コストが低い順にソート
4. コストが低い順に結果を表示

ソースコードは以下のような感じです。
もう少し洗練させて他のアルゴリズムとかもコーディングしていきたいです。
なんかなさそうだったので、TSP(巡回セールスマン問題)のgemとか作ってみたいですね！

[ruby]
# encoding: UTF-8

# file name(distence matrix)
filename = "matrix.csv"

# -(CSVファイルのテキトウな例)-
# ,tokyo,osaka,nagoya
# tokyo,0,300,500
# osaka,300,0,400
# nagoya,500,400,0
# ———————-

# import CSV as distance matrix
def import_distance(filename)
require "csv"
city_list = Array.new
distance = Array.new
i = 0
reader = CSV.open(filename, "r:UTF-8")
header = reader.take(1)[0]
reader.each do |row|
city_list.push(row.shift)
distance[i] = row
i = i + 1
end
return [distance, city_list]
end

# 力ずく法でTSPを解く
# 引数は距離行列（CSV）、結果は短い順にソートされた順路と距離の合計（二重配列）
def brute_force_method(filename)
distance, city_list = import_distance(filename)

# list up all courses
num_of_city = city_list.size – 1
str_num = (0..num_of_city).to_a
start = str_num.shift
route_arr = str_num.permutation.to_a.map {|e| e.unshift(start).push(start)}

# calculate the cost
route = Hash.new
route_arr.each do |elment|
first_place = 0
second_place = 0
distance_temp = 0
num_of_city.times do |num|
first_place = num
second_place = num + 1
distance_temp += distance[elment[first_place]][elment[second_place]].to_i
end
distance_temp += distance[elment[second_place]][elment[0]].to_i
route[elment] = distance_temp
end

# sort by the cost
route_sort = route.sort {|(k1, v1), (k2, v2)| v1 <=> v2 }

# replace city number for city name
return route_sort.each{|k| k[0].map!{|e| e = city_list[e]}}
end

# 結果の表示（上位10まで）
route_sorted = brute_force_method(filename)
10.times do |i|
print("ルート：　", route_sorted[i][0].join("→"), "\n")
print("距離：　#{route_sorted[i][1]}\n")
end
[/ruby]

Tweet

Pocket