Informed Search Algorithms

Informed Search Algorithms :

uninformed search algorithms look through search space for all possible solutions of the problem without having the additional knowledge about the search space but informed search algorithms contain knowledge such as how far from the goal, path cost, how to reach the goal node etc. This knowledge helps agent to find the goal node more efficiently without exploring all possible search space for all possible solutions for the problem.

Heuristic function:

Heuristic function which is used in informed search and it finds the most promising path. It takes the current state of agent as its input and produces the estimation of how close agent is from the goal. the heuristic method, however, might not always give the best solution, but it guaranteed to find a good solution in reasonable time. heuristic function estimates how close a state to the goal. It represented by h(n), it calculates the cost of an optimal path between pair of states. The value of Heuristic function is always positive.

  • • Admissibility of the heuristic function is given as: h(n) <= h*(n)

Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than or equal to the estimated cost.

Pure Heuristic Search:

Pure heuristic search is the simplest form of heuristic search algorithms. It expands nodes based on their heuristic value h(n). It maintains two lists, OPEN and CLOSED list. In the CLOSED list, it places those nodes which have already expanded and in the OPEN list, it places nodes which have yet not been expanded.
On each iteration, each node n with the lowest heuristic value is expanded and generates all its successors and n is placed to the closed list. The algorithm continues unit a goal state is found.
In the informed search we will discuss two main algorithms which are given below:

  • • Best First Search Algorithm (Greedy search)
  • • A* Search Algorithm

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc