Class: MM::Search

Inherits:
Object
  • Object
show all
Defined in:
lib/mm/search.rb

Overview

All you need to do is add an adjacent_points_function and cost_function

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(starting_point, delta = 0.001) ⇒ Search

Returns a new instance of Search.



8
9
10
11
12
13
14
15
 
# 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

Instance Attribute Details

#adjacent_points_function=(value) ⇒ Object (writeonly)

Sets the attribute adjacent_points_function

Parameters:

  • value —

    the value to set the attribute adjacent_points_function to.



6
7
8
 
# File 'lib/mm/search.rb', line 6

def adjacent_points_function=(value)
  @adjacent_points_function = value
end

#banned ⇒ Object

Returns the value of attribute banned.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def banned
  @banned
end

#candidates ⇒ Object

Returns the value of attribute candidates.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def candidates
  @candidates
end

#cost_function(*args) ⇒ Object 



61
62
63
 
# File 'lib/mm/search.rb', line 61

def cost_function *args
  @cost_function.call(*args)
end

#delta ⇒ Object

Returns the value of attribute delta.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def delta
  @delta
end

#iterations ⇒ Object

Returns the value of attribute iterations.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def iterations
  @iterations
end

#path ⇒ Object

Returns the value of attribute path.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def path
  @path
end

#starting_point ⇒ Object

Returns the value of attribute starting_point.



5
6
7
 
# File 'lib/mm/search.rb', line 5

def starting_point
  @starting_point
end

Instance Method Details

#add_to_path(point) ⇒ Object 



42
43
44
45
 
# File 'lib/mm/search.rb', line 42

def add_to_path point
  @current_point = point
  @path << point
end

#backtrack ⇒ Object 



47
48
49
50
51
 
# 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) ⇒ Object 



53
54
55
 
# File 'lib/mm/search.rb', line 53

def calculate_cost candidates
  candidates.map {|x| cost_function x}
end

#current_cost ⇒ Object 



65
66
67
 
# File 'lib/mm/search.rb', line 65

def current_cost
  cost_function @current_point
end

#find ⇒ Object

Finds a vector beginning from the starting point



18
19
20
 
# File 'lib/mm/search.rb', line 18

def find
  find_from_point @starting_point
end

#find_from_point(point) ⇒ Object 



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# 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) ⇒ Object 



69
70
71
 
# 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) ⇒ Object 



73
74
75
76
77
78
79
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


57
58
59
 
# File 'lib/mm/search.rb', line 57

def made_it?
  current_cost < @delta
end