aima.core.search.informed

Class AStarSearch

java.lang.Object

aima.core.search.framework.PrioritySearch

aima.core.search.informed.BestFirstSearch

aima.core.search.informed.AStarSearch

All Implemented Interfaces:

SearchForActions, SearchForStates

public class AStarSearch
extends BestFirstSearch

Artificial Intelligence A Modern Approach (3rd Edition): page 93.

The most widely known form of best-first search is called A* Search (pronounced "A-star search"). It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
f(n) = g(n) + h(n).

Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have
f(n) = estimated cost of the cheapest solution through n.

Author:

Ravi Mohan, Mike Stampone, Ruediger Lunde

Constructor Summary

Constructors

Constructor and Description
AStarSearch(QueueSearch impl, HeuristicFunction hf) Constructs an A* search from a specified search space exploration strategy and a heuristic function.

Method Summary

Methods inherited from class aima.core.search.informed.BestFirstSearch

getEvaluationFunction

Methods inherited from class aima.core.search.framework.PrioritySearch

findActions, findState, getComparator, getMetrics, getNodeExpander

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AStarSearch

public AStarSearch(QueueSearch impl,
                   HeuristicFunction hf)

Constructs an A* search from a specified search space exploration strategy and a heuristic function.

Parameters:

impl - a search space exploration strategy (e.g. TreeSearch, GraphSearch).

hf - a heuristic function h(n), which estimates the cost of the cheapest path from the state at node n to a goal state.