Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

communitycreator
algorithm
search

What are informed search algorithms?

Fatima Hasan

Two types of algorithms are used to explore a search spaceset of all possible states to find the goal state from a starting state. These are:

  • uninformed search algorithms
  • informed search algorithms

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.

Heuristic function

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.

Example

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.

Examples of informed search algorithms

1) Best first search

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

  1. Create a priority queue.

  2. Insert the starting node.

  3. 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.

2) A* Search

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), since h(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

  1. Create a Priority Queue.

  2. Insert the starting node.

  3. 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.

RELATED TAGS

communitycreator
algorithm
search
RELATED COURSES

View all Courses

Keep Exploring