Difference between Informed and Uninformed search in AI

The Uninformed Search (or Blind Search) as the name suggests is searching without “information” about the goal node. For example, in Breadth-First Search (BFS) the nodes at the same level are traversed first and then it moves to the next successive level and it does not stop until it has found the node with values that it was searching for. There is no requirement of information for selecting the nodes to traverse. You can also think of an uninformed search strategy as a brute-force search strategy. 

The Informed Search (or Heuristic Search) is searching with “information” about the goal node. For example, in the A* search algorithm, first, we gather information about the goal node such as its location in cartesian coordinate form and then we write a function that can guide our node traversal, for example, finding its Euclidean distance, also this function is called Heuristic Function. The heuristic function will guide our node traversal by stating the distance left from each node to the goal node. You can also think of Informed Search Strategy as a Guided Search Strategy.

Also, the informed search strategy is more efficient than the uninformed search strategy when we have information about the goal node but if the information is not present then the uninformed search strategy has to be applied.

 

Informed and Uninformed Search strategies are the heart and soul of Artificial Intelligence. In real life, the informed and the uninformed searching can look in this way. The uninformed searching occurs when you are looking from one website to another or flipping through the magazine books without really any need for finding the information. But the informed searching is the opposite in nature, for example, you are at work or you are studying something and there comes a term that you do not understand at that time you will not be browsing the internet for some random information but specifically you want to find the particular term and that is the informed searching.

As we can understand from the names that informed searching is working on algorithms based on some provided data and in uninformed searching, there is no provided data available for the learning algorithms to work on. Also for this reason the uninformed searching is called blind searching

 

Difference between Informed and Uninformed Search in AI

Difference between Informed and Uninformed search in AI

 

Uninformed Search (or Blind Search) in artificial Intelligence

In this method, the start state and the end state is provided to the learning algorithm, and initially, it starts searching from the start state and goes on exploring every state from the start state and does the same for every state and ultimately reach the goal state. This is similar to checking out every option available but the consequence of this is that artificial intelligence may be able to reach the goal state but the method it chooses will not be an ideal one. The algorithm does not have any knowledge about the problem and also there is no guide as in supervised machine learning to tell whether to take the path or not.

The uninformed search strategy is also called the blind search strategy and it is used by the brute force method. There are two types of brute force method – depth-first search and breadth-first search. The reason the BFS and DFS lie in the blind search strategy is that when they traverse the nodes in a graph they have no function available to check for optimum cost and distance instead they start from one node and keep on searching as per their algorithm till they reach the node with the desired value. These algorithms such as DFS and BFS have no algorithm in determining the preference for selecting the child node. The Uninformed Searches do not use domain-specific knowledge and do not have information beyond the problem definition.

 

Example of Uninformed Search in AI are:

  1. Breadth-First Search 
  2. Depth First Search
  3. Bidirectional search
  4. Uniform Cost Search

 

Informed Search (or Heuristic Search) in Artificial Intelligence

The informed search strategy as compared to the uninformed search has more information about the problem definition and this information of the problem state which is called the heuristic. An informed search also attempts to optimize the solution repeatedly based on the heuristic function. The informed search method may not always find the best solution as it works on an approximation basis but delivers an acceptable solution within a reasonable time. 

The Fundamental things that are required in carrying out an ideal search process are – the initial state, the set of operators, and the final state. The set of operators is the rule that we will be using to give the preference to some nodes when we will be traversing the graph. The preference of one child node over another is given based on assumptions. And also these assumptions make the informed search strategy more efficient than the uninformed search strategy. These assumption values are called the heuristic values which are calculated from the heuristic function.

For example, in graph traversal, the informed search strategy has information such as the path distance which can suggest how far we are from the goal from some arbitrary node, and information such as the path cost which can suggest how much we have spent in reaching some arbitrary node. All these costs and the path determination is done through the heuristic function.

 

Let’s Understand what is Heuristic Function:

Heuristic is a technique for solving problems faster when the classic method fails to solve in an optimum amount of time. This can be done with some tradeoffs such as accuracy, completeness, or exactness for the speed of problem-solving.

As quoted by Wikipedia:

 “ A Heuristic Function, also simply called heuristic, is a function that ranks alternatives in search algorithms at each branching step based on information available to decide which branch to follow.”

 

For example in A* algorithm, the sum of heuristic function and movement function:

f(n)=g(n) + h(n)

Where, g(n) = cost of the movement on graph from start node to node ‘n’.

And, h(n) = heuristic function that estimates the cheapest path which will result in the traversal.   

Now, you may have understood how much heuristic function is important for informed searches as the heuristic function is what differentiate the informed search from uninformed search. If you remove the heuristic function from the A* algorithm you will get the breadth-first search algorithm which is an uninformed search strategy. For some interesting fact, if you remove the movement function from the A* algorithm you will end up in Best First Search which will solely be based on heuristic function and will be a part of the informed search strategy.

A* (A Star) Search Algorithm

Examples of Informed Search in AI are:

  1. A* Algorithm
  2. Best First Search
  3. AO* Algorithm
  4. Constraints satisfaction
  5. Hill Climbing algorithm
  6. beam search

 

Difference between Informed and Uninformed search with TSP

Let’s take an example, the Traveling Salesman Problem(TSP) in which the salesman has to travel from its origin city to another city and then return to the origin city by covering the minimum distance possible. When we apply the uninformed searching in this problem then we have to check (n-1)! states say for example there are 5 number of cities and the uninformed searching is applied on it then 4! states will be checked by the uninformed searching and this will very much increase the time that is required in solving the algorithm and therefore this type of searching may not be the best approach. Also if you increase the number of cities up to 100 and apply the uninformed searching method then the time taken will exponentially increase and this is the biggest drawback.

In the informed searching we use the heuristic method, the heuristic method is more about making an approximate solution to the problem. The heuristic method is used when the state space grows in exponential power and therefore it increases the space as well as the time complexity of the problem. In such cases, the complexity can increase drastically and the problem may become an NP problem or Non-Polynomial problem and this will thereby increase the time complexity. When space and time complexity goes up the cost of solving the problem in the real world goes up. In such cases, we need that our problem can be solved in polynomial time, but doing so is not an easy task. 

To solve the problem in a polynomial-time the heuristic method is used. For example the same problem of the traveling salesman, the heuristic method is applied which uses the knowledge of the neighboring city. The uninformed searching used the method in which it is taking all the combination that was possible that may be good for a small number of the city but as the number of cities increases the states become practically impossible to follow, but in the heuristic approach used in the informed searching we can take the information about the neighboring city and with this information to act on our time complexity and space complexity both decreases.

Also, the heuristic approach may not always be able to provide the optimal solution but the uninformed searching will be guaranteed to find the optimal solution always, as the uninformed searching the amount of time that is required for finding the optimum solution but this also increases the space and the time complexity and thereby will increase the cost of the operation. 

 

Examples of informed and uninformed search in artificial intelligence 

There are many examples of uninformed learning and informed learning. For example, the depth-first search, as well as the breadth-first search, are the example of the uninformed learning as it starts from an initial state and from there it covers all the state that is possible form the initial state, there is more state space in this kind of algorithms. The A-star algorithm, the heuristic breadth-first search, heuristic depth-first search, and best first search are examples of the informed searching.

One thought on “Difference between Informed and Uninformed search in AI

  • October 21, 2020 at 1:38 pm
    Permalink

    Lot of work can be seen in the article !! Great content

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *