Best-First Search

Introduction

This Ruby gem implements the Best-First Search algorithm.

Synopsis

require 'bfsearch'

distance = ->(a, b) { a.calculate_distance_to(b) }
neighbors = ->(node) { node.all_neighbors }
heuristic = ->(a, b) { a.calculate_optimistic_distance_to(b) }

path = BFsearch.find_path(start, destination, distance, neighbors,
                          heuristic)

This gem implements the Greedy Best-First Search algorithm. Its main and only interface is BFsearch.find_path. This method requires a number of arguments, which are:

start:: The starting node destination:: The destination node distance:: A function that calculates the real distance between two nodes neighbors:: A function that returns all immediate neighbors of a node heuristic:: A function that calculates the optimistic distance between two nodes

The three functions are assumed to be Proc objects, i.e., procs or lambdas that answer to #call. Moreover, distance and heuristic are assumed to return a Float.

Heuristic must return an optimistic distance between two nodes. "Optimistic" means that the value must be lower than or equal to what the distance function would return: heuristic(a, b) <= distance(a, b). For example, the air-line distance would be such an optimistic function (compared to, e.g., the manhattan distance).

gBFS can be turned into standard BFS with heuristic = ->(a, b) { 0.0 }.

License

This code is licensed under the GNU GPL v3. See the file COPYING for details.