Searching Algorithm(A*,Admissible Heuristic)

-

Artificial Intelligence: Searching

Do you know the different way AI uses for searching?

A search strategy is defined by picking the order of the node expansion:

Strategies are evaluated along the following dimensions:

1)Completeness

Does it always find a solution if one exists?

2)Time Complexity

A number of nodes generated/expanded.

3)Space Complexity

Maximum no of nodes in memory

4)Optimality

Does it always find the least cost Solution?
                                      
Time and Space complexity is measured in terms of

B: Maximum branching factor if the search tree

D:Depth of the solution

M: maximum depth of the state space(maybe infinity)

Type of Searches available:

Uninformed Search are the search agent that do not require domain knowledge to search through the search space.

Breadth First search are the type of the search in which we expand the shallowest node first.

Depth First Search expand the deepest node.

Breadth First Search


Shallowest node means that one on the top, Just to keep in mind that by shallowest node we need to do some kind of level search. We need to go from one level to another level We would not go from from one level to the previous level unless the previous level is all done.So, Starting from A, if A is not the goal test then we put it in fringe now if A is not the goal test then we put it in fringe and explore its children. So, the next thing is to do is to explore B & then C.When we explore B then if B is the goal test then we stop, if B is not the goal test then we expand its children D & E and put them in the fringe.

Algorithm:

Function BREADTH FIRST SEARCH(initial state,goal Test)
Return SUCCESS or Failure:
Frontier=Queue.new(initial State)
Explored=Set.new()
While not frontier.isEmpty
State=frontier.deque
Explored.add(state)
If goalTest(State)
Return SUCCESS(State)
For neighbour in State.neighbours():
If neighbours not in frontier U explored
Frontier.enqueue(neighbour)
Return FAILURE

Informed Search

In inform search, we don’t have any information about how we are getting closer to the goal?
So fir this we use a heuristic function that uses a heuristic function that estimates how close a state is to goal. A heuristic does not have to be perfect.

Examles of Search:
1)Greedy Best First Search
2)A* Search
3)IDA*

The distance is straight line distance. The goal is to get distance from each city.

Greedy Search

Evaluates function h(n) heuristic.H(n)estimates cost from n to the closest goal.
Exmple:-Straight line distance from n to any place

Greedy Search expand the node that appears to be closest to the goal.

Function GREEDY_BEST_FIRST_SEARCH(initialState,goalTest)
Return SUCCESS or FAIlure:
Frontier=Heap.new(initial State)
Explored=Set.new()
While not frontier.isEmpty
State=frontier.deleteMin
Explored.add(state)
If goalTest(State)
Return SUCCESS(State)
For neighbour in State.neighbours():
If neighbours not in frontier U explored
Frontier.insert(neighbour)
Else If neighbours in frontier
Frontier.decreaseKey(neighbour)
Return FAILURE


Greedy Search is doing the job but not always the best job.

For Example, Between St Mary, We are not getting the shortest path to the goal Alternative to the greedy search is A* Search.

A*Search


  1. Minimize the total estimated solution cost.
  2. Combines:-
    1. Cost to reach node n
    2. Cost to get from n to the goal
            1. f(n)=g(n)+h(n)


g(n)=Cost to reach node n
h(n)=Cost to get from n to the goal

where n is the previous node on the path

h(n) is the heuristic that estimates the cost of the cheapest path from n to the target node.
Algorithm will remain same as:

F(n)=g(n)+h(n)
A good heuristic can be powerful only of t is of good quality and it is admissible.

Admissible Heuristic

Admissible Heuristic never overestimates the cost to reach the goal i.e. it is optimistic.A heuristic h is admissible if for all node n, h(n)<=h*(n).Hsld used as a heuristic in the map example is admissible because it is by definition shortest distance between 2 points.


A* Search Criteria


  1. It is Complete
  2. It is exponential in the time complexity.
  3. It keeps every node in the memory so its space complexity is also exponential.
  4. It is optimal as it will find the best possible solution of least cost in your search.
  5. When you will solve this, you will find that the solution is 26 steps long but if define heuristic function here than one heuristic can be
H(1)=No of misplace tiles=8
H(2)=Total Manhattan Distance(Sum of horizontal and vertical distance)
Tile s1 to 8 to move to its initial no of stpes nedded =18 which also do not overestimates the true cost.
N is on the shortest path to G0

f(Gs)=g(GS)







Comments

Post a Comment