class SearchAlgorithm
Author: Johnny Lee Othon
Attributes
goal[R]
history[R]
space[R]
start[R]
traversal[R]
tree[R]
Public Class Methods
new(space, start, goal, caches=true)
click to toggle source
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
# 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
Public Instance Methods
cost()
click to toggle source
Retruns the total cost from start to goal following the path specifed in SearchAlgorithm#Path
.
# File lib/usearchtree/search.rb, line 52 def cost self.path if @path.empty? return @cost end
path()
click to toggle source
Returns a list of all nodes in order from start to goal.
# 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()
click to toggle source
Performs the search and populates traversal
and tree
# File lib/usearchtree/search.rb, line 32 def search throw "Unimplemented" end