动态规划研究

用数组存储.rb

# 返回城市距离
def dis e1, e2
  if (e1 == "A" and e2 == "E") || (e1 == "E" and e2 == "B") || (e1 == "B" and e2 == "F")
    return 5
  end
  10
end

@boxes = []

def boxes_has? e_h, e_t, set
  dis, route = nil
  @boxes.each do |box|
    if e_h == box[0] && e_t == box[1] && set == box[2]
      dis, route = box[3], box[4]
      break
    end
  end
  return dis, route
end

@god_i = 0

def fn_xh e_h, e_t, set
  the_dis, the_route = boxes_has? e_h, e_t, set
  return the_dis, the_route if the_dis
  @god_i += 1
  if e_h == e_t
    if set.size == 2
      e = (set - [e_h, e_t])[0]
      dis, route = dis(e_h, e) + dis(e, e_t), [e_h, e, e_t].sort
      @boxes << [e_h, e_t, set.sort, dis, route]
      #save_to_boxes e_h, e_t, set, dis, route
      return dis, route
    end
  else
    if set.size == 2
      dis, route = dis(e_h, e_t), [e_h, e_t]
      @boxes << [e_h, e_t, set.sort, dis, route]
      #save_to_boxes e_h, e_t, set, dis, route
      return dis, route
    end
    if set.size == 3
      e = (set - [e_h, e_t])[0]
      dis, route = dis(e_h, e) + dis(e, e_t), [e_h, e, e_t]
      @boxes << [e_h, e_t, set.sort, dis, route]
      #save_to_boxes e_h, e_t, set, dis, route
      return dis, route
    end
  end
  r_dis, r_route = nil
  sub_set = set - [e_h, e_t]
  sub_set.each do |e1|
    sub_set.each do |e2|
      if e1 != e2
        temp_dis, temp_route = (fn_xh e1, e2, sub_set)
        temp_dis = dis(e_h, e1) + temp_dis + dis(e2, e_t)
        if r_dis
          if temp_dis < r_dis
            temp_route = Array.new(temp_route)
            temp_route.insert(0, e_h) << e_t
            r_dis, r_route = temp_dis, temp_route
          end
        else
          temp_route = Array.new(temp_route)
          temp_route.insert(0, e_h) << e_t
          r_dis, r_route = temp_dis, temp_route
        end
      end
    end
  end
  @boxes << [e_h, e_t, set.sort, r_dis, r_route]
  #save_to_boxes e_h, e_t, set, r_dis, r_route.sort
  return r_dis, r_route
end

# %w(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)
t1 = Time.new
dis, route = fn_xh "A", "A", %w(A B C D E F G H)
puts "time:#{Time.new.to_f - t1.to_f}"
puts dis, route.to_s
puts @god_i
#puts Box.boxes.size

#Box.boxes.each do |box|
#  #puts box.set.size
#  if box.set.size == 2
#    puts "#{box.e_h} #{box.e_t} #{box.set.to_s}"
#  end
#end

用类存储.rb

# 返回城市距离
def dis e1, e2
  if (e1 == "A" and e2 == "E") || (e1 == "E" and e2 == "B") || (e1 == "B" and e2 == "F")
    return 5
  end
  10
end

class Box
  @boxes = []

  class << self
    attr_accessor :boxes
  end

  attr_accessor :e_h, :e_t, :set, :dis, :route

  def initialize e_h, e_t, set, dis = nil, route = nil
    @e_h, @e_t, @set, @dis, @route = e_h, e_t, set, dis, route
  end

  def == box
    @e_h == box.e_h && @e_t == box.e_t && @set.sort == box.set.sort
  end

  def self.box_exists? e_h, e_t, set
    box = Box.new e_h, e_t, set
    @boxes.each do |one_box|
      if box == one_box
        box = one_box
        break
      end
    end
    return box.dis, box.route
  end
end

@god_i = 0

def fn_xh e_h, e_t, set
  the_dis, the_route = Box.box_exists? e_h, e_t, set
  return the_dis, the_route if the_dis
  @god_i += 1
  if e_h == e_t
    if set.size == 2
      e = (set - [e_h, e_t])[0]
      box = Box.new e_h, e_t, set, dis(e_h, e) + dis(e, e_t), [e_h, e, e_t]
      Box.boxes << box
      return box.dis, box.route
    end
  else
    if set.size == 2
      box = Box.new e_h, e_t, set, dis(e_h, e_t), [e_h, e_t]
      Box.boxes << box
      return box.dis, box.route
    end
    if set.size == 3
      e = (set - [e_h, e_t])[0]
      box = Box.new e_h, e_t, set, dis(e_h, e) + dis(e, e_t), [e_h, e, e_t]
      Box.boxes << box
      return box.dis, box.route
    end
  end
  r_dis, r_route = nil
  sub_set = set - [e_h, e_t]
  sub_set.each do |e1|
    sub_set.each do |e2|
      if e1 != e2
        temp_dis, temp_route = (fn_xh e1, e2, sub_set)
        temp_dis = dis(e_h, e1) + temp_dis + dis(e2, e_t)
        if r_dis
          if temp_dis < r_dis
            temp_route = Array.new(temp_route)
            temp_route.insert(0, e_h) << e_t
            r_dis, r_route = temp_dis, temp_route
          end
        else
          temp_route = Array.new(temp_route)
          temp_route.insert(0, e_h) << e_t
          r_dis, r_route = temp_dis, temp_route
        end
      end
    end
  end
  box = Box.new e_h, e_t, set, r_dis, r_route
  Box.boxes << box
  return box.dis, box.route
end

# %w(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)
t1 = Time.new
dis, route = fn_xh "A", "A", %w(A B C D E F G H)
puts "time:#{Time.new.to_f - t1.to_f}"
puts dis, route.to_s
puts @god_i
#puts Box.boxes.size

#Box.boxes.each do |box|
#  #puts box.set.size
#  if box.set.size == 2
#    puts "#{box.e_h} #{box.e_t} #{box.set.to_s}"
#  end
#end

穷举.rb

# 返回城市距离
def dis e1, e2
  if (e1 == "A" and e2 == "E") || (e1 == "E" and e2 == "B") || (e1 == "B" and e2 == "F")
    return 5
  end
  10
end

@god_i = 0

def fn_xh e_h, e_t, set
  @god_i += 1
  if e_h == e_t
    #与 e_h != e_t 时，set.size == 3 的情形相同
    if set.size == 2
      e = (set - [e_h, e_t])[0]
      return dis(e_h, e) + dis(e, e_t), [e_h, e, e_t]
    end
  else
    return dis(e_h, e_t), [e_h, e_t] if set.size == 2
    if set.size == 3
      e = (set - [e_h, e_t])[0]
      return dis(e_h, e) + dis(e, e_t), [e_h, e, e_t]
    end
  end
  r_dis, r_route = nil
  sub_set = set - [e_h, e_t]
  sub_set.each do |e1|
    sub_set.each do |e2|
      if e1 != e2
        temp_dis, temp_route = fn_xh e1, e2, sub_set
        temp_dis = dis(e_h, e1) + temp_dis + dis(e2, e_t)
        temp_route.insert(0, e_h) << e_t
        if r_dis
          if temp_dis < r_dis
            r_dis, r_route = temp_dis, temp_route
          end
        else
          r_dis, r_route = temp_dis, temp_route
        end
      end
    end
  end
  return r_dis, r_route
end

# %w(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)
t1 = Time.new
dis, route = fn_xh "A", "A", %w(A B C D E F G H)
puts "time:#{Time.new.to_f - t1.to_f}"
puts dis, route.to_s
puts @god_i