package aima.core.search.local;
import java.util.ArrayList;
import java.util.List;
import aima.core.agent.Action;
import aima.core.search.framework.HeuristicFunction;
import aima.core.search.framework.Node;
import aima.core.search.framework.NodeExpander;
import aima.core.search.framework.Problem;
import aima.core.search.framework.Search;
import aima.core.search.framework.SearchUtils;
import aima.core.util.CancelableThread;
/**
* 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 * @author Mike Stampone */ public class HillClimbingSearch extends NodeExpander implements Search { public enum SearchOutcome { FAILURE, SOLUTION_FOUND }; private HeuristicFunction hf = null; private SearchOutcome outcome = SearchOutcome.FAILURE; private Object lastState = null; /** * Constructs a hill-climbing search from the specified heuristic function. * * @param hf * a heuristic function */ public HillClimbingSearch(HeuristicFunction hf) { this.hf = hf; } /** * 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. * * @param p * the search problem * * @return 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. */ // function HILL-CLIMBING(problem) returns a state that is a local maximum public List