Class: Newral::Graphs::TreeSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/newral/graphs/tree_search.rb

Overview

the algorithms are heavily inspired by the Udacity course from Sebastian Thrun classroom.udacity.com/courses/cs271

Direct Known Subclasses

AStar, CheapestFirst

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph: nil, start_node: nil, end_node: nil) ⇒ TreeSearch

Returns a new instance of TreeSearch.



10
11
12
13
14
15
16
17
 
# File 'lib/newral/graphs/tree_search.rb', line 10

def initialize( graph: nil, start_node: nil, end_node: nil  )
  @graph = graph 
  @start_node = start_node
  @end_node = end_node 
  path = Path.new(edges:[ Edge.new( start_node: start_node, end_node: start_node, directed: true, cost:0 )])
  @explored = {end_node: 0 }
  @frontier = [ path ]
end

Instance Attribute Details

#frontier ⇒ Object (readonly)

Returns the value of attribute frontier.



9
10
11
 
# File 'lib/newral/graphs/tree_search.rb', line 9

def frontier
  @frontier
end

Instance Method Details

#measure(path) ⇒ Object

the standard approach is breath first



54
55
56
 
# File 'lib/newral/graphs/tree_search.rb', line 54

def measure( path )
  path.length
end

#remove_choice ⇒ Object 



45
46
47
48
49
50
51
 
# File 'lib/newral/graphs/tree_search.rb', line 45

def remove_choice
  @frontier.sort! do |path1,path2|
    measure( path2 ) <=> measure( path1 ) # reverse 
  end
  puts "frontier: #{@frontier.length}"
  @frontier.pop # pops shortest
end

#run ⇒ Object

Raises:



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/newral/graphs/tree_search.rb', line 19

def run

  while @frontier.length > 0 
    path = remove_choice
    return path if path.end_node == @end_node
    edges = @graph.find_edges( path.end_node)
    puts "no edges found for #{path.end_node.name} #{@graph.edges.length}" unless edges.length > 0
    edges.each do |edge|
      begin
        end_node = edge.start_node == path.end_node ? edge.end_node : edge.start_node
        new_edge = Edge.new( start_node: path.end_node, end_node: end_node, directed: true, cost: edge.cost )
        puts( "n:#{ new_edge.to_s } e:#{edge} n:#{end_node} s:#{path.end_node} #{edge.start_node == new_edge.end_node } #{edge.end_node}")
        new_path = Path.new(edges:path.edges).add_edge( new_edge )
        if  @explored[new_path.end_node].nil? ||  measure( path  ) < @explored[new_path.end_node]
          @frontier << new_path
          @explored[ new_path.end_node ] = measure( new_path )
        end
      rescue Errors::CircularPath
        puts "circular #{ new_path.to_s }"
        # no need to check this path
      end
    end
  end
  raise Errors::FrontierEmpty 
end