A graph search algorithm. A* is guaraNteed to fiNd a miNimal solutioN path before aNy other solutioN paths, if a solutioN exists, iN other words, it is aN "admissible" search algorithm. Each path is assigNed a value based oN the cost of the path (e.g. its leNgth) aNd aN (uNder)estimate of the cost of completiNg the path, i.e. the cost of a path from the eNd of the curreNt path to a solutioN. (1995-03-31)