Best-First search
1. Put the initial state to the front search.
2. If the front is blank then search stopped.
3. Take the first in a series of state of the search front.
4. If the situation is a member of the closed set, then go to 2.
5. If the statement is an end then said the solution and stop.
6. Apply the transport operators to produce the statements-children.
7. Apply the heuristic function to each child.
8. Put the kids in situations-front search.
9. Search rearranged the front, so that the state with the best heuristic value being first.
10. Put the state in parent-closed set.
11. Go to step 2.

advantages & disadvantages of BestFS
advantages
1. It tries to give you a quick solution to a problem (depends a lot from the heuristics).
2. Complete - provided that includes a mechanism
control loops.

  disadvantages
1. Forehead search grows at a high rate and with him the space needed for storage.
2. Does not guarantee that the solution found will be optimal.

Α* search algorithm
The algorithm A * (Alpha Star) is on the basis BestFS, but with a heuristic function: f (S) = g (S) + h (S)
- The g (S) gives the distance of S from the initial state, which is true and known.
- The h (S) gives the estimate of the distance of S from the final state by a heuristic function, just as in BestFS.

If for every situation the value h (S) is less than or equal to the real distance of S from the final state, then A * always finds the optimum solution.
- In this case the heuristic called admissible (admissible).

Heuristic Search: A * Algorithm
1. OPEN: = [so], CLOSED: = []
2. If OPEN = [] then ended. There is no solution.
3. Remove the situation, si, the OPEN list, for which f (si) <= f (sj) for all other open state sj and added to CLOSED.
4. Created the successors si, and give one to each successor index prostin si, as its predecessor.
5. If s(g) belongs to the successors si, then returned and finished the route from the sg so.
6. Otherwise reiterated the following for each successor, sj, the si:
6.1 Calculate the value f (sj).
6.2 If sj is neither in OPEN or CLOSED on
situations, then added the OPEN sj in the price evaluation, f (sj).
6.3 If sj is already on OPEN or CLOSED then compare the new value evaluation, whether new, with the oldest, even old. If old <= new, then expelled the new node to the state sj. Otherwise, remove the item (sj, old) from the list to which it belongs (OPEN or CLOSED) and add the item (sj, news) to OPEN.
7. Repeated the command 2.

Observations on A * Algorithm
1. Based on the function f open situations are evaluated and selected for further investigation, namely expansion, one which has the smallest value for f.
2. For the initial state, f (so) = h (so) and the final state f (sg) = g (sg).
3. Lists OPEN and CLOSED have the same meanings as before. Now the list OPEN is used as an ordered list (ordered list). The details of these lists are pairs of the form (s, ​​f (s)), where, as previously, the element s is a pointer to the relevant node of the ongoing search space.

Heuristic Searches - Example Problem

Typical solution is about twenty steps
Branching factor is approximately three. Therefore a complete search would need to search 320 states. But by keeping track of repeated states we would only need to search 9! (362,880) states
But even this is a lot (imagine having all these in memory)
Our aim is to develop a heuristic that does not over estimate (it is admissible) so that we can use A* to find the optimal solution

H1 = the number of tiles that are in the wrong position (=7)

H2 = the sum of the distances of the tiles from their goal positions using the Manhattan Distance (=18)

Both are admissible but which one is best?