class MM::Search

All you need to do is add an adjacent_points_function and cost_function

Attributes

adjacent_points_function[W]
banned[RW]
candidates[RW]
cost_function[W]
delta[RW]
iterations[RW]
path[RW]
starting_point[RW]

Public Class Methods

new(starting_point, delta = 0.001) click to toggle source
# File lib/mm/search.rb, line 8
def initialize starting_point, delta = 0.001
  @starting_point = starting_point
  @delta = delta
  @current_point = @starting_point
  @path = []
  @banned = []
  @iterations = 0
end

Public Instance Methods

add_to_path(point) click to toggle source
# File lib/mm/search.rb, line 42
def add_to_path point
  @current_point = point
  @path << point
end
backtrack() click to toggle source
# File lib/mm/search.rb, line 47
def backtrack
  @banned << @path.pop
  puts "Path: #{@path.size}, Banned: #{@banned.size}" if ENV["DEBUG_RB"] && ENV["DEBUG_RB"].to_i > 1
  @current_point = @path.last
end
calculate_cost(candidates) click to toggle source
# File lib/mm/search.rb, line 53
def calculate_cost candidates
  candidates.map {|x| cost_function x}
end
cost_function(*args) click to toggle source
# File lib/mm/search.rb, line 61
def cost_function *args
  @cost_function.call(*args)
end
current_cost() click to toggle source
# File lib/mm/search.rb, line 65
def current_cost
  cost_function @current_point
end
find() click to toggle source

Finds a vector beginning from the starting point

# File lib/mm/search.rb, line 18
def find
  find_from_point @starting_point
end
find_from_point(point) click to toggle source
# File lib/mm/search.rb, line 22
def find_from_point point
  @iterations += 1
  # The adjacent points are all sorted
  # raise StopIteration if cost_function(point) > current_cost
  add_to_path point
  sorted_adjacent_points = get_sorted_adjacent_points
  # If we've made it, return it.
  if made_it?
    @current_point
  else
    begin
      find_from_point sorted_adjacent_points.next
    rescue StopIteration => er
      # When the list of adjacent points runs out, backtrack
      backtrack
      retry unless @current_point.nil?
    end
  end
end
get_adjacent_points(*args) click to toggle source
# File lib/mm/search.rb, line 69
def get_adjacent_points *args
  @adjacent_points_function.call(@current_point, *args)
end
get_sorted_adjacent_points(*args) click to toggle source
# File lib/mm/search.rb, line 73
def get_sorted_adjacent_points *args
  get_adjacent_points(*args)
    .reject {|c| @path.include? c}
    .reject {|c| @banned.include? c}
    .sort_by {|x| cost_function x}
    .to_enum
end
made_it?() click to toggle source
# File lib/mm/search.rb, line 57
def made_it?
  current_cost < @delta
end