Answers.Body: <p>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. </p>
  
  <p>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 href="https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf" rel="nofollow noreferrer">A*</a> has exponential time and space complexities (with respect to the <a href="https://en.wikipedia.org/wiki/Branching_factor" rel="nofollow noreferrer">branching factor</a> and the depth of the tree), but, in practice, it tends to perform decently well. It tends to have an <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#cite_note-nilsson-3" rel="nofollow noreferrer">effective branching factor</a> (that is, the branching factor for specific problem instances) quite "small" (for several problems).</p>
  
  <p>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 <span class="math-container">$h$</span> the heuristic function. If <span class="math-container">$h(n)=0$</span>, for all nodes <span class="math-container">$n$</span>, then this is an admissible heuristic, because it always underestimates the distance to the goal (that is, it always returns <span class="math-container">$0$</span>). 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 <span class="math-container">$h_1$</span> and <span class="math-container">$h_2$</span>, <span class="math-container">$h_2$</span> is more informed than <span class="math-container">$h_1$</span> if <span class="math-container">$h_1(n) \leq h_2(n)$</span>, for all nodes <span class="math-container">$n$</span>.</p>
  
  <p>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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-16T13:53:37.353Z
Answers.LastActivityDate: 2019-04-16T14:05:51.040Z
Answers.LastEditDate: 2019-04-16T14:05:51.040Z
Answers.UserDisplayName: nbro
Body: <p>Why does informed search more efficiently finds a solution than an uninformed search? </p>
  
Tags: <search><comparison><efficiency>
Title: Why is informed search more efficient than uninformed search?
UserDisplayName: Lexi
ThreadText: # Why is informed search more efficient than uninformed search?
  
  (Asked by: username_0 on 2019-04-16)
  
  Why does informed search more efficiently finds a solution than an uninformed search?
  
  **Tags:** search, comparison, efficiency
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-04-16. Score: 1 | Accepted 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\*](https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf) has exponential time and space complexities (with respect to the [branching factor](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/A*_search_algorithm#cite_note-nilsson-3) (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).
  
  
  ---
  
  