Class: Ai4r::Search::DFS

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

Overview

Explore nodes in depth-first order until a goal is found.

Instance Method Summary collapse

Constructor Details

#initialize(goal_test, neighbor_fn, start = nil) ⇒ DFS

Create a new DFS searcher.

goal_test

lambda returning true for a goal node

neighbor_fn

lambda returning adjacent nodes for a given node

start

optional starting node



18
19
20
21
22
 
# File 'lib/ai4r/search/dfs.rb', line 18

def initialize(goal_test, neighbor_fn, start = nil)
  @goal_test = goal_test
  @neighbor_fn = neighbor_fn
  @start = start
end

Instance Method Details

#search(start = nil) ⇒ Object

Find a path from the start node to a goal.

start

initial node if not provided on initialization

Returns an array of nodes representing the path, or nil if no goal was found.

Raises:

  • (ArgumentError) 


29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/ai4r/search/dfs.rb', line 29

def search(start = nil)
  start ||= @start
  raise ArgumentError, 'start node required' unless start

  stack = [[start, [start]]]
  visited = { start => true }
  until stack.empty?
    node, path = stack.pop
    return path if @goal_test.call(node)

    @neighbor_fn.call(node).each do |n|
      next if visited[n]

      visited[n] = true
      stack << [n, path + [n]]
    end
  end
  nil
end