Class: Ai4r::Search::AStar

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

Overview

Generic A* search implementation operating on arbitrary graph representations.

Initialize with start node, a goal predicate, a neighbor function and a heuristic.

The neighbor function must return a hash mapping neighbor nodes to edge costs. The heuristic receives a node and returns the estimated remaining cost to reach the goal.

Instance Method Summary collapse

Constructor Details

#initialize(start, goal_test, neighbor_fn, heuristic_fn) ⇒ AStar 



27
28
29
30
31
32
 
# File 'lib/ai4r/search/a_star.rb', line 27

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

Instance Method Details

#search ⇒ Object

Execute the search and return the path as an array of nodes or nil if the goal cannot be reached.



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/ai4r/search/a_star.rb', line 36

def search
  open_set = [@start]
  came_from = {}
  g = { @start => 0 }
  f = { @start => @heuristic_fn.call(@start) }
  closed = Set.new

  until open_set.empty?
    current = open_set.min_by { |n| f[n] }
    return reconstruct_path(came_from, current) if @goal_test.call(current)

    open_set.delete(current)
    closed << current
    @neighbor_fn.call(current).each do |neighbor, cost|
      next if closed.include?(neighbor)

      tentative_g = g[current] + cost
      next unless g[neighbor].nil? || tentative_g < g[neighbor]

      came_from[neighbor] = current
      g[neighbor] = tentative_g
      f[neighbor] = tentative_g + @heuristic_fn.call(neighbor)
      open_set << neighbor unless open_set.include?(neighbor)
    end
  end
  nil
end