Class: SearchAlgorithm

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

Overview

Author: Johnny Lee Othon

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(space, start, goal, caches = true) ⇒ SearchAlgorithm

Initializes a search algorithm. Parameters:

space

a graph

start

the id or name of the starting node

goal

the id or name of the goal node

cache

true a cache of visited nodes is desired



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/usearchtree/search.rb', line 12

def initialize space, start, goal, caches=true
    @space = space
    @start = space.node(start)
    @goal = space.node(goal)
    # node.key => node
    @cache = (Hash.new if caches)
    # order in which the graph nodes were traversed
    @traversal = Array.new
    # parent => parent_node
    @tree = {@start => nil}
    # lazy list of nodes from start to goal
    @path = Array.new
    # lazy total of cost from start to goal
    @cost = nil
    # history to see the history of the stack
    @history = Array.new
end

Instance Attribute Details

#goal ⇒ Object (readonly)

Returns the value of attribute goal.



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

def goal
  @goal
end

#history ⇒ Object (readonly)

Returns the value of attribute history.



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

def history
  @history
end

#space ⇒ Object (readonly)

Returns the value of attribute space.



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

def space
  @space
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



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

def start
  @start
end

#traversal ⇒ Object (readonly)

Returns the value of attribute traversal.



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

def traversal
  @traversal
end

#tree ⇒ Object (readonly)

Returns the value of attribute tree.



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

def tree
  @tree
end

Instance Method Details

#cost ⇒ Object

Retruns the total cost from start to goal following the path specifed in SearchAlgorithm#Path.



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

def cost
    self.path if @path.empty?
    return @cost
end

#path ⇒ Object

Returns a list of all nodes in order from start to goal.



37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/usearchtree/search.rb', line 37

def path
    return @path if @path.any?
    node = @goal
    @cost = 0
    while node
        parent = @tree[node]
        @path.insert(0, node)
        @cost += parent ? parent.cost(node) : 0
        node = parent
    end
    return @path
end

#search ⇒ Object

Performs the search and populates traversal and tree



32
33
34
 
# File 'lib/usearchtree/search.rb', line 32

def search
    throw "Unimplemented"
end