Show Summary Details

Page of

PRINTED FROM OXFORD REFERENCE (www.oxfordreference.com). (c) Copyright Oxford University Press, 2013. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single entry from a reference work in OR for personal use (for details see Privacy Policy and Legal Notice).

Subscriber: null; date: 20 August 2018

A* algorithm

Source:
A Dictionary of Computing
Author(s):

John Daintith,

Edmund Wright

A* algorithm 

A member of the class of best-first heuristic search techniques that attempt to find a “best” path from a given start node to a designated goal node in a problem graph. An evaluation function is used to estimate the cost of the (unknown) distance from the current node being explored to the goal and this is then added to the (known) cost of the shortest path from the start node to the current node to give a figure of merit for the current node. At each iteration the node with the best cost figure is used to pursue the search. The operation of the algorithm displays a behavior that is a mixture of depth-first and breadth-first searching.