Class: Search

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options) ⇒ Search

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



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

Instance Attribute Details

#current_state ⇒ Object (readonly)

Returns the value of attribute current_state.



4
5
6
 
# File 'lib/rsearch/search.rb', line 4

def current_state
  @current_state
end

#iterations ⇒ Object (readonly)

Returns the value of attribute iterations.



4
5
6
 
# File 'lib/rsearch/search.rb', line 4

def iterations
  @iterations
end

Instance Method Details

#distance ⇒ Object

how far is the search right now from the start



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

def distance
  path.size - 1
end

#path ⇒ Object

returns the path to the current node from the start



38
39
40
 
# File 'lib/rsearch/search.rb', line 38

def path
  path_to(@current_state)
end

#run ⇒ Object

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



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# 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