DOC PREVIEW
Texas State CS 5346 - The Best-First Search Algorithm

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17The Best-First Search AlgorithmImplementing Best-First SearchIn spite of their limitations, algorithms such as backtrack, hill climbing, and dynamic programming can be used effectively if their evaluation functions are sufficiently informative to avoid local maxima, dead ends, and related anomalies in a search space. In general, however, use or heuristic search requires a more flexible algorithm: this is provided by best-first search, where, with a priority queue, recovery from these situations is possible. Like the depth-first and breadth-first search algorithms or Chapter 3, best-first search uses lists to maintain states: open to keep track or the current fringe of the search and closed to record states already visited. An added step in the algorithm orders the states on open according to some heuristic estimate or their "closeness" to a goal. Thus, each iteration or the loop considers the most "promising" state on the open list. The pseudo code for the function best-first search appears below.begin open := [Start]; % initialize closed :=[]; while open ≠ [] do % states remain begin remove the leftmost state from open, call it X; if X = goal then return the path from Start to X else begin generate children of X; for each child of X do case the child is not on open or closed:begin assign the child a heuristic value; add the child to openend; the child is already on open:if the child was reached by a shorter paththen give the state on open the shorter path the child is already on closed:if the child was reached by a shorter path then begin remove the state from closed; add the child to open end; end; % case put X on closed; re-order states on open by heuristic merit (best leftmost) end;return FAIL % open is emptyend.At each iteration, best_first_search removes the first element from the open list. If it meets the goal conditions, the algorithm returns the solution path that led to the goal. Note that each state retains ancestor information to determine if it had previously been reached by a shorter path and to allow the algorithm to return the final solution path. (See Section 3.2.3.)If the first element on open is not a goal, the algorithm applies all matching production rules or operators to generate its descendants. If a child state is already on open or closed, the algorithm checks to make sure that the state records the shorter of the two partial solution paths. Duplicate states are not retained. By updating the ancestor history of nodes on open and closed when they are rediscovered, the algorithm is more likely to find a shorter path to a goal. best_first_search then applies a heuristic evaluation to the states on open, and the list is sorted according to the heuristic values of those states. This brings the "best" states to the front of open. Note that because these estimates are heuristic in nature, the next state to be examined may be from any level of the state space. When open is maintained as a sorted list, it is often referred to as a priority queue.Figure 4.10 shows a hypothetical state space with heuristic evaluations attached to some of its states. The states with attached evaluations arc those actually generated in best_first_search. The states expanded by the heuristic search algorithm are indicated in bold; note that it does not search all of the space. The goal of best-first search is to find the goal state by looking at as few states as possible; the more informed (Section 4.2.3) the heuristic, the fewer states arc processed in finding the goal.A trace of the execution of best_first_search on this graph appears below. Suppose P is the goal state in the graph of Figure 4.10. Because P is the goal, states along the path to P tend to have low heuristic values. The heuristic is fallible: the state 0 has a lower value than the goal itself and is examined first. Unlike hill climbing, which does not maintain a priority queue for the selection of "next" states, the algorithm recovers from this error and finds the correct goal.1. open = [A5]; closed = []2. evaluate A5; open = [B4,C4,D6]; closed = [A5]3. evaluate B4; open = [C4,E5.F5,D6]; closed = [B4,A5]4. evaluate C4; open = [H3,G4,ES,F5,D6]; closed = [C4,B4,A5]5. evaluate H3; open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5]6. evaluate o2; open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5)7. evaluate P3; the solution is found!Figure 4,11 shows the space as it appears after the fifth iteration of the while loop. The states contained in open and closed are indicated. open records the current frontier of the search and closed records states already considered. Note that the frontier of the search is highly uneven, reflecting the opportunistic nature of best-first search.The best-first search algorithm always selects the most promising state on open for further expansion. However, as it is using a heuristic that may prove erroneous, it does not abandon all the other states but maintains them on open. In the event a heuristic Ieads the search down a path that proves incorrect, the algorithm will eventually retrieve some previously generated, "next best" state from open and shift its focus to another part of the space. In the example of Figure 4.10, after the children of state B were found to have poor heuristic evaluations, the search shifted its focus to state C. The children of B were kept on open in case the algorithm needed to return to them later. In best_first_search, as in the algorithms of Chapter 3, the open list allows backtracking from paths that fail to produce a goal.We now evaluate the performance of several different heuristics for solving the 8-puzzle. Figure 4.12 shows a start and goal state for the 8-puzzle, along with the first three states generated in the search.The simplest heuristic counts the tiles out of place in each state when it is compared with the goal. This is intuitively appealing, because It would seem that, all else being equal, the state that had fewest tiles out of place is probably closer to the desired goal and would be the best to examine next.However, this heuristic does not use all of the information available in a board configuration, because it does not take into account the distance the tiles must be moved.A "better“ heuristic would sum all the distances by which the tiles are out of place, one for each


View Full Document

Texas State CS 5346 - The Best-First Search Algorithm

Download The Best-First Search Algorithm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Best-First Search Algorithm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Best-First Search Algorithm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?