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