class Search
Attributes
current_state[R]
iterations[R]
Public Class Methods
new(options)
click to toggle source
Search
object is initialized with a start node, a generator function that expands neighbours of the node, and scheduler that chooses which neighbour to expand next
# File lib/rsearch/search.rb, line 8 def initialize(options) @start = options[:start] @generator = options[:generator] @scheduler = options[:scheduler] @iterations = 0 #keep track of iterations executed @current_state = @start #set start as current state of the search @child_to_parent = {} #parent tree to find paths @parents = Set.new #keep track of parents to prevent back-edges in the parent tree end
Public Instance Methods
distance()
click to toggle source
how far is the search right now from the start
# File lib/rsearch/search.rb, line 43 def distance path.size - 1 end
path()
click to toggle source
returns the path to the current node from the start
# File lib/rsearch/search.rb, line 38 def path path_to(@current_state) end
run()
click to toggle source
performs an iteration of a search, expanding the current node in the search tree and scheduling neighbours, as well as keep track of paths and iterations
# File lib/rsearch/search.rb, line 21 def run raise "dead end" if @current_state.nil? @iterations += 1 new_states = @generator.call(@current_state) @parents << @current_state if new_states.any? new_states.each do |new_state| if !@parents.include?(new_state) && #prevent back-edges !@child_to_parent[new_state] #respect expansion order in the path @child_to_parent[new_state] = @current_state end end next_state = @scheduler.call(new_states) @current_state = next_state end
Private Instance Methods
path_to(node)
click to toggle source
# File lib/rsearch/search.rb, line 49 def path_to(node) anc = [node] while @child_to_parent[node] anc << @child_to_parent[node] node = @child_to_parent[node] end anc.reverse end