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が必要です．
その方法は以下のサイトにまとめがありますので，ご覧ください．

https://qiita.com/noanoa07/items/a20dccff0902947d3e0c

ちなみにgem install gnuplotもある様ですが，バージョンが古いのか機能しなかったので添付しているURLの通りにhomebrewでgnuplotをインストールすることを推奨します．

gnuplotをインストールし終えた方は，gem install numo-gnuplotでnumo-gnuplotをインストールしてください．

以上でこのTravelingSalesmanクラスを実行できるはずです！

#ちなみこんなgifに仕上がった