A-star is an informed search method that evaluates nodes by combining both the cost to reach the node (step cost) and the cost to get to the goal state (heuristic):

Provided that the heuristic function satisfies the optimality conditions (i.e., admissibility for tree-search and consistency for graph-search), A-star search is both complete and optimal despite its large space complexity. Its implementation is based on the best-first search algorithm using an anonymous evaluation function that returns the sum of the two cost criteria, see Figure 1.

*Figure 1. A-star search algorithm.*

## @deftypefn {Function File} {@var{solution} =} a_star_search (@var{problem}, @var{start}, @var{finish}, @var{treegraph}, @var{heuristic}) ## A-star search algorithm. ## ## PRE: ## @var{problem} must be the cost-weighted adjacency matrix. ## @var{start} must be the starting node index. ## @var{finish} must be the finishing node index. ## @var{treegraph} must be the tree/graph version flag. 0 is tree-version. ## @var{heuristic} must be the heuristic vector. ## ## POST: ## @var{solution} is the solution path. State set to zero if failure. ## @end deftypefn ## Author: Alexandre Trilla <alex@atrilla.net> function [solution] = a_star_search(problem, start, finish, treegraph, heuristic) % eval func is anonymous and returns path cost + heuristic solution = best_first_search(problem, start, finish, treegraph, ... @(cost) cost(1) + cost(2), heuristic); endfunction

At this point, the last mile to delivering useful and feasible results is to reduce the amount of memory consumed by A-star. This will be the topic of the next post. Stay tuned!

## One thought on “The A-star algorithm”

Comments are closed.