Why is informed search more efficient than uniformed search?

Why does informed search more efficiently finds a solution than uniformed search?

If there was an example, it would be easy to understand.

• Have a look at ai.stackexchange.com/q/7179/2444. – nbro Apr 16 at 10:45
• What do you mean by "efficient"? Do you mean in terms of time and space complexity? – nbro Apr 16 at 11:14
• @nbro yes in terms of time and space complexity – Lexi Apr 16 at 12:31
• There are several informed and non-informed search algorithms and they do not all have the same time complexity. I could create an informed search algorithm that is highly inefficient in terms of time or space complexity. So, in general, informed search algorithm are not more efficient than uninformed ones, in terms of space and time complexity. So, you have to reformulate your question. For example, you could ask a list of the time complexities of the most commonly used/known informed and uninformed search algorithms. – nbro Apr 16 at 13:22
• @nbro how is it efficient? not in terms of space and time complexity – Lexi Apr 16 at 13:50

1 Answer

There are several informed and uninformed search algorithms. They do not all have the same time and space complexity (which also depends on the specific implementation). I could come up with an informed search algorithm that is highly inefficient in terms of time or space complexity. So, in general, informed search algorithm are not more efficient than uninformed ones, in terms of space and time complexity.

However, given that informed search algorithms use "domain knowledge" (that is, an heuristic function that estimates the distance to the goal nodes), in practice, they tend to find the goal node more rapidly, given a more informed "heuristic" (which needs to be admissible in order to find the optimal solution). For example, in theory, A* has exponential time and space complexities (with respect to the branching factor and the depth of the tree), but, in practice, it tends to perform decently well. It tends to have an effective branching factor (that is, the branching factor for specific problem instances) quite "small" (for several problems).

What is a more informed heuristic? Intuitively, it is an heuristic that more rapidly focuses on the promising parts of the search space. Let's denoted by $$h$$ the heuristic function. If $$h(n)=0$$, for all nodes $$n$$, then this is an admissible heuristic, because it always underestimates the distance to the goal (that is, it always returns $$0$$). However, it is a quite uninformed heuristic: either if you are at the start or goal nodes, the estimation is always the same (so you cannot distinguish the start and goal nodes, in terms of estimates). Given two admissible heuristics $$h_1$$ and $$h_2$$, $$h_2$$ is more informed than $$h_1$$ if $$h_1(n) \leq h_2(n)$$, for all nodes $$n$$.

An uninformed search algorithm performs an exhaustive search. There are several ways of performing such exhaustive search (e.g. breadth-first or depth-first), which are more efficient than others (depending on the search space or problem). Given that they perform an exhaustive search, they tend to explore "uninteresting" parts of the search space. Hence, in practice, they might be more inefficient than informed search algorithms (that is, they might require more time to find the solution).

• ! thank you. helped me a lot! – Lexi Apr 16 at 14:26