aima.core.search.local

Class HillClimbingSearch

java.lang.Object

aima.core.search.local.HillClimbingSearch

All Implemented Interfaces:

SearchForActions, SearchForStates

public class HillClimbingSearch
extends java.lang.Object
implements SearchForActions, SearchForStates

Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.2, page 122.

 function HILL-CLIMBING(problem) returns a state that is a local maximum
                    
   current <- MAKE-NODE(problem.INITIAL-STATE)
   loop do
     neighbor <- a highest-valued successor of current
     if neighbor.VALUE <= current.VALUE then return current.STATE
     current <- neighbor
 

Figure 4.2 The hill-climbing search algorithm, which is the most basic local search technique. At each step the current node is replaced by the best neighbor; in this version, that means the neighbor with the highest VALUE, but if a heuristic cost estimate h is used, we would find the neighbor with the lowest h.

Author:

Ravi Mohan, Mike Stampone, Ruediger Lunde

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HillClimbingSearch.SearchOutcome

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	METRIC_NODE_VALUE
static java.lang.String	METRIC_NODES_EXPANDED

Constructor Summary

Constructors

Constructor and Description
HillClimbingSearch(HeuristicFunction hf) Constructs a hill-climbing search from the specified heuristic function.
HillClimbingSearch(HeuristicFunction hf, NodeExpander nodeExpander)

Method Summary

Modifier and Type	Method and Description
java.util.List<Action>	findActions(Problem p) Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.
java.lang.Object	findState(Problem p) Returns a state which is might be but not necessary is a goal state of the problem.
java.lang.Object	getLastSearchState() Returns the last state from which the hill climbing search found the local maximum.
Metrics	getMetrics() Returns all the search metrics.
NodeExpander	getNodeExpander() Returns the node expander used by the search.
HillClimbingSearch.SearchOutcome	getOutcome() Returns SOLUTION_FOUND if the local maximum is a goal state, or FAILURE if the local maximum is not a goal state.
Node	searchNode(Problem p) Returns a list of actions to the local maximum if the local maximum was found, a list containing a single NoOp Action if already at the local maximum, or an empty list if the search was canceled by the user.

Methods inherited from class java.lang.Object

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

Field Detail

METRIC_NODES_EXPANDED

public static final java.lang.String METRIC_NODES_EXPANDED

See Also:

Constant Field Values

METRIC_NODE_VALUE

public static final java.lang.String METRIC_NODE_VALUE

See Also:

Constant Field Values

Constructor Detail

HillClimbingSearch

public HillClimbingSearch(HeuristicFunction hf)

Constructs a hill-climbing search from the specified heuristic function.

Parameters:

hf - a heuristic function

HillClimbingSearch

public HillClimbingSearch(HeuristicFunction hf,
                          NodeExpander nodeExpander)

Method Detail

findActions

public java.util.List<Action> findActions(Problem p)

Description copied from interface: SearchForActions

Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

Specified by:

findActions in interface SearchForActions

Parameters:

p - the search problem

Returns:

a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

findState

public java.lang.Object findState(Problem p)

Description copied from interface: SearchForStates

Returns a state which is might be but not necessary is a goal state of the problem.

Specified by:

findState in interface SearchForStates

Parameters:

p - the search problem

Returns:

a state.

searchNode

public Node searchNode(Problem p)

Returns a list of actions to the local maximum if the local maximum was found, a list containing a single NoOp Action if already at the local maximum, or an empty list if the search was canceled by the user.

Parameters:

p - the search problem

Returns:

a list of actions to the local maximum if the local maximum was found, a list containing a single NoOp Action if already at the local maximum, or an empty list if the search was canceled by the user.

getOutcome

public HillClimbingSearch.SearchOutcome getOutcome()

Returns SOLUTION_FOUND if the local maximum is a goal state, or FAILURE if the local maximum is not a goal state.

Returns:

SOLUTION_FOUND if the local maximum is a goal state, or FAILURE if the local maximum is not a goal state.

getLastSearchState

public java.lang.Object getLastSearchState()

Returns the last state from which the hill climbing search found the local maximum.

Returns:

the last state from which the hill climbing search found the local maximum.

getNodeExpander

public NodeExpander getNodeExpander()

Description copied from interface: SearchForActions

Returns the node expander used by the search. Useful for progress tracing.

Specified by:

getNodeExpander in interface SearchForActions

Specified by:

getNodeExpander in interface SearchForStates

getMetrics

public Metrics getMetrics()

Returns all the search metrics.

Specified by:

getMetrics in interface SearchForActions

Specified by:

getMetrics in interface SearchForStates