Why does informed search more efficiently finds a solution than an uninformed search?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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).