Search Classification

AI plays a vital role in searching algorithms. As we already know that AI means a thinking machine,
capable of acting like Humans. Humans have the capability to improvise in the middle of doing a
work. Similarly, machines can also be programmed to improvise while searching. Now we will see
how this can be achieved.

The searching algorithms can be divided into two main categories :
1. Blind / Uninformed
2. Heuristic / Informed

1. Blind / Uninformed searching technique means that search is not aware of its position
in the search space. For example - Breadth First Search, Depth First Search, etc.

2. Heuristic / Informed searching technique means that the search is aware of its position
in the search space. It uses a heuristic function to improvise its searching technique.
It can calculate how much distance it has covered and predict how many calculations
are required to reach its target.
For example - Simple Hill Climbing, Best First Search, A*, AO*, etc.

A heuristic function is a function that maps from the problem
state descriptions to measures of desirability, usually
represented as numbers.

The best example for demonstrating heuristic function is the 8-puzzle problem.
The 8-puzzle is a small board game for a single player; it consists of 8
square tiles numbered 1 through 8 and one blank space on a 3 x 3 board.
Moves of the puzzle are made by sliding an adjacent tile into the position
occupied by the blank space, which has the effect of exchanging the positions
of the tile and blank space. Only tiles that are horizontally or vertically
adjacent (not diagonally adjacent) may be moved into the blank space.
The goal is to set all the numbered tiles in ascending order starting
from the top left corner.

Let the heuristic function be like the total number of numbered tiles that
are exactly in its place. For example, Tile 4 is at the position 4.

From the above picture it is clear that we will select that state which has
higher heuristic value as it leads us to the goal perfectly.

That's an example of heuristic function. There is no hard and fast rule that
a problem will have same heuristic function. It completely depends on the
programmer how to solve the problem. For instance, anyone can make a heuristic
function that counts how tiles are not in places.

Now a formal definition of heuristic search process:
A heuristic is a technique that improves the efficiency of a search process,
possibly by sacrificing claims of completeness.

I will describe the heuristic algorithms in the next blog. Till then, keep coding.