Two types of algorithms are used to explore a
Uninformed search algorithms explore the entire search space without any indication of how far away the goal is. On the other hand, informed search algorithms use additional knowledge to increase the efficiency of the search. This knowledge may include the current cost from the starting state, the distance from the goal state, or a combination of the two.
A heuristic function helps the search algorithm choose a branch from the ones that are available. It helps with the decision process by using some extra knowledge about the search space.
Let’s use a simple analogy. If you went to a supermarket with many check-out counters, you would try to go to the one with the least number of people waiting. This is a heuristic that reduces your wait time.
While playing tic tac toe, there are many placements from which one player can start, and each placement has its own chances of winning. However, if the first player starts from the centermost area, they have the most chances of winning. Hence, chances of winning can be a heuristic.
The best first search algorithm is a version of the depth first search using heuristics. Each node is evaluated with respect to its distance from the goal. Whichever node is closest to the final state is explored first. If the path fails to reach the goal, the algorithm backtracks and chooses some other node that didn’t seem to be the best before.
Algorithm
Create a priority queue.
Insert the starting node.
Remove a node from the priority queue.
3.1. Check if it is the goal node. If yes, then exit.
3.2. Otherwise, mark the node as visited and insert its neighbors into the priority queue. The priority of each will be its distance from the goal.
The previous algorithm we discussed only considered the distance of the nodes from the goal. A* uses the path of reaching to the current node from the starting node, and the path of reaching the goal from the current node. So, the heuristic function becomes:
f(n) = g(n) + h(n)
where:
f(n): cost of the optimal path from start to goal
g(n): shortest path of the current node from the start
h(n): shortest path of the goal from the current node
Note: The actual distance from any node to the goal may be greater than
h(n), sinceh(n)is the shortest distance. This distance can be the straight line distance from the current node to the goal. A path with the shortest distance may or may not exist.
Algorithm
Create a Priority Queue.
Insert the starting node.
Remove a node from the priority queue.
3.1. Check if it is the goal node. If yes, then exit.
3.2. Otherwise, mark the node as visited and insert its neighbors into the priority queue. The priority of each node will be the sum of its cost from the start and the goal.