HotLink Menu in RightSide Column 
Last Updated 6292010 


Informed Search StrategiesThis section shows how an informed search strategy  one that uses problemspecific knowledge beyond the definition of the problem itself  can find solutions more efficiently than can an uninformed search strategy. The general approach we consider is called best first search. Bestfirst search is an instance of the general TreeSearch or GraphSearch algorithm in which a node is selected for expansion based on an evaluation function, f(n). The evaluation function is construed as a costestimate, so the node with the lowest evaluation is expanded first. The implementation of best first graph search is identical to that for UniformCost Search, except for the use of f instead of g to order the priority queue. The choice of f determines the search strategy. Most bestfit algorithms include as a component of f a heuristic function denoted h(n): h(n) = estimated cost of the cheapest path from the state at node n to a goal state. Notice that h(n) takes a node as an input, but, unlike g(n) it depends only on the state at that node. For example, one might estimate the cost of the cheapest path from Arad to Bucharest via the straightline distance from Arad to Bucharest. Heuristic functions are the most common form in which additional knowledge of the problem is imparted to the search algorithm. We also consider them to be arbitrary, nonnegative, problem specific functions, with one constraint: if n is a goal node, then h(n)=0. Following are two ways to use heuristic information to guide search. Greedy BestFirst SearchGreedy bestfirst search tries to expand the node that is closest to the goal, on the grounds that it is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n)=h(n). Let us see how this works for the routefinding problems in Romania; we use the straightline distance heuristic, which we will call h_{SLD}. If the goal is Bucharest, we need to know the straightline distances to Bucharest, which are shown in Figure ISS1:
Notice that the values of h_{SLD} cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that h_{SLD} is correlated with actual road distances and is, therefore, a useful heuristic. Figure ISS2 shows the progress of a greedy bestfirst search using h_{SLD} to find a path from Arad to Bucharest:
The first node to be expanded from Arad will be Sibiu because it is closer to Bucharest then either Zerind or Timisoara. The next node to be expanded will be Fagaras because it is closest. Fagaras, in turn, generates Bucharest, which is the goal. For this particular problem, greedy bestfirst search using h_{SLD} finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal. It is not optimal, however: the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti. This shows why the algorithm is called "Greedy"  at each step it tries to get as close to the goal as it can.
Greedy bestfirst tree search is also incomplete even in a finite state space, much like depthfirst search. Consider the problem of getting from Iasi to Fagaras. The heuristic suggests that Neamt will be expanded first because it is closest to Fagaras, but it is a dead end street. The solution is to go first to Vaslui  a step that is actually farther from the goal according to the heuristic  and then continue to Urziceni, Bucharest, and Fagaras. The algorithm will never find this solution, however, because expanding neamt puts Iasi back into the frontier, Iasi is closer to Fagaras than Valusi is, and so Iasi will be expanded again, leading to an infinite loop. (The graph search version is complete in finite spaces, but not in infinite ones.) The worst case time and space complexity for the tree version is O(b^{m}), where m is the maximum depth fo the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of reduction depends on the particular problem and on the quality of the heuristic. A* Search: Minimizing the total estimated solution costThe most widely known form of bestfirst search is called A* search (pronounced "Astar 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, the goal node, 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. Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n)+h(n). As it turns out, this strategy is more than just reasonable: provide that the heuristic function, h(n), satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to UniformCost Search except that A* uses g+h instead of g. In order to continue with this guide, and start the discussion of Conditions for Optimality: Admissability and Consistency: Press the Button below: 
Big O Notation NP Completeness Intelligent Agents Formulating Problems Toy Problems Vacuum World 8 Queens The Knuth Sequence Real World Problems Route Finding Problems Touring Problems Traveling Salesperson Problem VLSI Layout Robot Navigation Automatic Assembly Sequencing Search Algorithm Infrastructure Child Node Creation Measuring Algorithm Performance BreadthFirst Search BreadthFirst Characteristics C++ BreadthFirst Search Code BreadthFirst Data Structure BreadthFirst Make Map BreadthFirst Make Neighbor BreadthFirst Point of Origin BreadthFirst Initial Listing BreadthFirst Get Child City C++ BreadthFirst Search Code UniformCost Search DepthFirst C++ Solution DepthFirst Data Structure DepthFirst Display Data DepthFirst Initial Listing DepthFirst Path Record DepthFirst Main() DepthLimited Search Bidirectional Search Comparing Strategies Greedy BestFirst A* Search Optimality of A* A* Search Data Structure A* Search Data Entry C++ Min Priority Queue C++ A* Headers & Prototypes C++ A* Search Main() 