Ruby\u3067\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c\u3092\u89e3\u3053\u3046\u3068\u601d\u3044\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u3092\u3057\u3066\u307f\u307e\u3057\u305f\u3002
\n\u3068\u308a\u3042\u3048\u305a\u3001\u96e3\u3057\u3044\u3053\u3068\u306f\u8003\u3048\u305a\u306b\u3001\u5358\u7d14\u306a\u65b9\u6cd5\u3067\u3084\u3063\u3066\u307f\u307e\u3057\u305f\u3002
\n\u4ee5\u4e0b\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u8a00\u3046\u306b\u306f\u3042\u307e\u308a\u306b\u5358\u7d14\u306a\u65b9\u6cd5\u3002<\/p>\n
<\/p>\n
\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306a\u611f\u3058\u3067\u3059\u3002
\n\u3082\u3046\u5c11\u3057\u6d17\u7df4\u3055\u305b\u3066\u4ed6\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u304b\u3082\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\u3057\u3066\u3044\u304d\u305f\u3044\u3067\u3059\u3002
\n\u306a\u3093\u304b\u306a\u3055\u305d\u3046\u3060\u3063\u305f\u306e\u3067\u3001TSP(\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c)\u306egem\u3068\u304b\u4f5c\u3063\u3066\u307f\u305f\u3044\u3067\u3059\u306d\uff01<\/p>\n
[ruby]
\n# encoding: UTF-8<\/p>\n
# file name(distence matrix)
\nfilename = "matrix.csv"<\/p>\n
# -(CSV\u30d5\u30a1\u30a4\u30eb\u306e\u30c6\u30ad\u30c8\u30a6\u306a\u4f8b)-
\n# ,tokyo,osaka,nagoya
\n# tokyo,0,300,500
\n# osaka,300,0,400
\n# nagoya,500,400,0
\n# ———————-<\/p>\n
# import CSV as distance matrix
\ndef import_distance(filename)
\n require "csv"
\n city_list = Array.new
\n distance = Array.new
\n i = 0
\n reader = CSV.open(filename, "r:UTF-8")
\n header = reader.take(1)[0]
\n reader.each do |row|
\n city_list.push(row.shift)
\n distance[i] = row
\n i = i + 1
\n end
\n return [distance, city_list]
\nend<\/p>\n
# \u529b\u305a\u304f\u6cd5\u3067TSP\u3092\u89e3\u304f
\n# \u5f15\u6570\u306f\u8ddd\u96e2\u884c\u5217\uff08CSV\uff09\u3001\u7d50\u679c\u306f\u77ed\u3044\u9806\u306b\u30bd\u30fc\u30c8\u3055\u308c\u305f\u9806\u8def\u3068\u8ddd\u96e2\u306e\u5408\u8a08\uff08\u4e8c\u91cd\u914d\u5217\uff09
\ndef brute_force_method(filename)
\n distance, city_list = import_distance(filename)<\/p>\n
# list up all courses
\n num_of_city = city_list.size – 1
\n str_num = (0..num_of_city).to_a
\n start = str_num.shift
\n route_arr = str_num.permutation.to_a.map {|e| e.unshift(start).push(start)}<\/p>\n
# calculate the cost
\n route = Hash.new
\n route_arr.each do |elment|
\n first_place = 0
\n second_place = 0
\n distance_temp = 0
\n num_of_city.times do |num|
\n first_place = num
\n second_place = num + 1
\n distance_temp += distance[elment[first_place]][elment[second_place]].to_i
\n end
\n distance_temp += distance[elment[second_place]][elment[0]].to_i
\n route[elment] = distance_temp
\n end<\/p>\n
# sort by the cost
\n route_sort = route.sort {|(k1, v1), (k2, v2)| v1 <=> v2 }<\/p>\n
# replace city number for city name
\n return route_sort.each{|k| k[0].map!{|e| e = city_list[e]}}
\nend<\/p>\n
# \u7d50\u679c\u306e\u8868\u793a\uff08\u4e0a\u4f4d10\u307e\u3067\uff09
\nroute_sorted = brute_force_method(filename)
\n10.times do |i|
\n print("\u30eb\u30fc\u30c8\uff1a\u3000", route_sorted[i][0].join("\u2192"), "\\n")
\n print("\u8ddd\u96e2\uff1a\u3000#{route_sorted[i][1]}\\n")
\nend
\n[\/ruby]<\/p>\n","protected":false},"excerpt":{"rendered":"
Ruby\u3067\u5de1\u56de\u30bb\u30fc\u30eb\u30b9\u30de\u30f3\u554f\u984c\u3092\u89e3\u3053\u3046\u3068\u601d\u3044\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u3092\u3057\u3066\u307f\u307e\u3057\u305f\u3002 \u3068\u308a\u3042\u3048\u305a\u3001\u96e3\u3057\u3044\u3053\u3068\u306f\u8003\u3048\u305a\u306b\u3001\u5358\u7d14\u306a\u65b9\u6cd5\u3067\u3084\u3063\u3066\u307f\u307e\u3057\u305f\u3002 \u4ee5\u4e0b\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u8a00\u3046\u306b\u306f\u3042\u307e\u308a\u306b\u5358\u7d14\u306a\u65b9\u6cd5\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,4,16],"tags":[22,23,24],"_links":{"self":[{"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/posts\/661"}],"collection":[{"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/comments?post=661"}],"version-history":[{"count":6,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/posts\/661\/revisions"}],"predecessor-version":[{"id":669,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/posts\/661\/revisions\/669"}],"wp:attachment":[{"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/media?parent=661"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/categories?post=661"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/frsw.net\/blog\/wp-json\/wp\/v2\/tags?post=661"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}