Method: Plexus::Search#astar

Defined in:

lib/plexus/search.rb

#astar(start, goal, func, options, &block) ⇒ Array(vertices), ...

A* Heuristic best first search.

‘start` is the starting vertex for the search.

‘func` is a `Proc` that when passed a vertex returns the heuristic weight of sending the path through that node. It must always be equal to or less than the true cost.

‘options` are mostly callbacks passed in as a hash, the default block is `:discover_vertex` and the weight is assumed to be the label for the Arc. The following options are valid, anything else is ignored:

• ‘:weight` => can be a `Proc`, or anything else is accessed using the `[]` for the

  the label or it defaults to using
  the value stored in the label for the {Arc}. If it is a `Proc` it will
  pass the edge to the proc and use the resulting value.
  

• ‘:discover_vertex` => `Proc` invoked when a vertex is first discovered and is added to the open list.

• ‘:examine_vertex` => `Proc` invoked when a vertex is popped from the queue (i.e., it has the lowest cost on the open list).

• ‘:examine_edge` => `Proc` invoked on each out-edge of a vertex immediately after it is examined.

• ‘:edge_relaxed` => `Proc` invoked on edge `(u,v) if d + w(u,v) < d`.

• ‘:edge_not_relaxed`=> `Proc` invoked if the edge is not relaxed (see above).

• ‘:black_target` => `Proc` invoked when a vertex that is on the closed

  list is "rediscovered" via a more efficient path, and is re-added
  to the open list.
  

• ‘:finish_vertex` => Proc invoked on a vertex when it is added to the

  closed list, which happens after all of its out edges have been
  examined.
  

Can also be called like ‘astar_examine_edge {|e| … }` or `astar_edge_relaxed {|e| … }` for any of the callbacks.

The criteria for expanding a vertex on the open list is that it has the lowest ‘f(v) = g(v) + h(v)` value of all vertices on open.

The time complexity of A* depends on the heuristic. It is exponential in the worst case, but is polynomial when the heuristic function h meets the following condition: ‘|h(x) - h*(x)| < O(log h*(x))` where `h*` is the optimal heuristic, i.e. the exact cost to get from `x` to the `goal`.

See also: [A* search algorithm](en.wikipedia.org/wiki/A*_search_algorithm) on Wikipedia.

Parameters:

• start (vertex) —

  the starting vertex for the search

• goal (vertex) —

  the vertex to reach

• func (Proc) —

  heuristic weight computing process

• options (Hash)

Returns:

• (Array(vertices), call, nil) —

  an array of nodes in path, or calls block on all nodes, upon failure returns ‘nil`

# File 'lib/plexus/search.rb', line 288

def astar(start, goal, func, options, &block)
  options.instance_eval "def handle_callback(sym,u) self[sym].call(u) if self[sym]; end"

  # Initialize.
  d = { start => 0 }
  color = { start => :gray } # Open is :gray, closed is :black.
  parent = Hash.new { |k| parent[k] = k }
  f = { start => func.call(start) }
  queue = PriorityQueue.new.push(start, f[start])
  block.call(start) if block

  # Process queue.
  until queue.empty?
    u, dummy = queue.delete_min
    options.handle_callback(:examine_vertex, u)

    # Unravel solution if the goal is reached.
    if u == goal
      solution = [goal]
      while u != start
        solution << parent[u]
        u = parent[u]
      end
      return solution.reverse
    end

    adjacent(u, :type => :edges).each do |e|
      v = e.source == u ? e.target : e.source
      options.handle_callback(:examine_edge, e)
      w = cost(e, options[:weight])
      raise ArgumentError unless w

      if d[v].nil? or (w + d[u]) < d[v]
        options.handle_callback(:edge_relaxed, e)
        d[v] = w + d[u]
        f[v] = d[v] + func.call(v)
        parent[v] = u

        unless color[v] == :gray
          options.handle_callback(:black_target, v) if color[v] == :black
          color[v] = :gray
          options.handle_callback(:discover_vertex, v)
          queue.push v, f[v]
          block.call(v) if block
        end
      else
        options.handle_callback(:edge_not_relaxed, e)
      end
    end # adjacent(u)

    color[u] = :black
    options.handle_callback(:finish_vertex, u)
  end # queue.empty?

  nil # failure, on fall through
end