Artificial Intelligence

Informed Searching Algorithms

We discussed the uninformed algorithms in our previous topic. Now another category of the searching strategy in AI is the informed search algorithms. 
Informed search algorithms contain information about the goal state. This will help in more efficient searching. It contains an array of knowledge about how close is the goal state to the present state, path cost, how to reach the goal, etc. Informed search algorithms are useful in large databases where uninformed search algorithms can’t make an accurate result.  Informed search algorithms are also called heuristic search since it uses the idea of heuristics.
The heuristic function is a function used to measure the closeness of the current state to the goal state and heuristic properties are used to find out the best possible path to reach the goal state concerning the path cost.
Consider an example of searching a place you want to visit on Google maps. The current location and the destination place are given to the search algorithm for calculating the accurate distance, time taken, and real-time traffic updates on that particular route. This is executed using informed search algorithms.  

Informed search algorithms can be classified into 4 major types.

AI - Informed Searching Algorithms?

1. Pure Heuristic Search

It is a simple search performed based on a heuristic value denoted by h(n). It maintains two lists OPEN for new and unexpanded nodes and CLOSE  for expanded nodes. The node with the smallest heuristic value is expanded for every iteration. And then all its child nodes are expanded and added to the closed list. A heuristic function is then applied to the closed list and the node with the shortest path is saved and the others are dispersed.  The algorithm starts with the initial state node on the open list. Node with the minimum h(n) value on the open list is expanded at each cycle and generates its child nodes and is kept in the closed list. The heuristic function is then applied to the child nodes and is placed on the open list based on their heuristic values.

The procedure continues until the goal state is selected for expansion.

In pure heuristic search for a given heuristic function, The simplest method used is

f(n) = h(n)

where f(n) is the cost function and h(n) is the heuristic function. For a PHS algorithm, it doesn’t guarantee to terminate with an infinite graph even if there exists a goal node.

Here a solution of length 4 is returned even there exists one with length 3. PHS only considers h(n), the heuristic function or the estimated cost to the goal while expanding a node, or the cost to reach the goal node from the node n. It doesn’t consider the cost to reach node n from start state g(n) 

Advantages Disadvantages
  • Provides a quick feedback
  • Early feedback in the design process
  • For applying heuristic effectively, knowledge and experience are required.
  • The evaluation concern more minor issues and fewer major issues.

2. Best-First Search Algorithm (Greedy Search)

As like the name best at first, is selected. It always selects the path which seems to be the best at that moment. It is a combination of both breadth-first search and depth-first search algorithms and takes the advantage of both algorithms. It also uses the heuristic function and performs the searching procedure. It helps to choose the most optimistic node at each step. The closest node to the goal node is expanded and the closest cost is approximated by the heuristic function.

Let us discuss with the help of traveling salesman problem.
A salesman is provided with a list of places to visit in a city. He has to find the optimum route to travel in such a way that the traveling time is reduced as much as possible. Here he can choose between 2 or more places from his current place to go to. He has to choose the one with the least distance.      

The node costs are stored in a priority queue pq.
The procedure can be like 
Our source or starting node is S and the goal node is G. pq initially is with S. we remove S from pa and add the child node {A, C, B} (C is put before B because C is with less cost).
Now A is removed and a, b is added to pq {C, B, a, b}. Remove C and add e to pq {B, e, a, b} B is removed and c, d added to pq { e, a, b, c, d}  . now e is removed since our goal has been reached   

Advantages Disadvantages
Advantages of both BFS and DFS are gained. More efficient than DFS and BFS. Not optimal. May get stuck in a loop as DFS.