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
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
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
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