module BFsearch

This class implements the Best-First Search algorithm.

The Best-First Search algorithm (BFS) tries to find a valid path from a starting node to a destination node. It will always find a path if one exists.

The typical usage is to call BFsearch.find_path.

Constants

Entry

Public Class Methods

find_path(root_node, destination, distance_function, neighbors_function, heuristic_function) click to toggle source

Finds a way from root_node to destination_node and returns the path node by node.

This method implements the Best-First Search algorithm. It starts at root_node, trying to find a way to the destination.

The distance between two nodes is measured using a function object passed as the distance_function parameter. It is called as:

distance_function.call(node_1, node_2)  # => Float

Whenever the algorithm advances from the current node, it needs to know of the node’s neighbors. For this, the foruth parameter, neighbors_function, is required. It is also assumed to be a lambda object or any object that responds to +neighbors_function#call(current_node)+ and returns a list of adjacent nodes.

neighbors_function.call(node)  # => Array

BFS is an informed search algorithm, i.e., it uses an heuristic to select the probably best next node at any given state. This heuristic is implemented using a Lambda and the third parameter, +heuristic_function(node)+. The distance function must return an optimistic guess of the distance from the given node to the destination node. ‘Optimistic’ means that the value returned (a float) must be equal to or lower than the actual distance, but never greater. The air-line distance is a valid implementation of the distance function, since it will always return a value equal to or lower than the actual distance due to the triangle inequality.

heuristic_function(node)  # => Float

# File lib/bfsearch.rb, line 61
def self.find_path(root_node, destination,
    distance_function, neighbors_function, heuristic_function)
  root_entry = Entry.new(root_node, nil, 0.0)
  open = [root_entry]
  closed = []

  until open.empty?
    catch :restart do
      current = open.shift
      return construct_path(root_node, current) if current.node == destination
      closed.push current

      neighbors_function.call(current.node).each do |node|
        open_entry = open.find { |i| i.node == node }
        closed_entry = closed.find { |i| i.node == node }
        entry = open_entry || closed_entry ||
          Entry.new(node, current, nil)

        distance_from_start = distance(entry, distance_function)
        entry.distance ||= distance_from_start

        # Greedy BFS:

        heuristic_neighbor = heuristic_function.call node
        heuristic_current = heuristic_function.call current.node
        if heuristic_neighbor < heuristic_current
          open.unshift current
          open.unshift entry
          throw :restart
        end

        if !(open_entry || closed_entry)
          open.push entry
        else
          if distance_from_start < entry.distance
            entry.parent = current
            entry.distance = distance_from_start
            open.push entry unless open_entry
          end
        end
      end

      open.sort_by(&:distance)
    end
  end
end

Private Class Methods

construct_path(root_node, destination) click to toggle source

Constructs and returns an array that contains the best path from the root_node to the destination object.

# File lib/bfsearch.rb, line 111
def self.construct_path(root_node, destination)
  nodes = [destination[:node]]

  while destination[:node] != root_node
    destination = destination[:parent]
    nodes.unshift destination[:node]
  end

  nodes
end

distance(start, distance_function) click to toggle source

Retruns the accumulated distance between two nodes along the currently recorded path

# File lib/bfsearch.rb, line 125
def self.distance(start, distance_function)
  current = start
  distance = 0.0

  while current.parent
    distance += distance_function.call current.node, current.parent.node
    current = current.parent
  end

  distance
end