Question

Which of the following algo is NOT an example of uninformed search?

• A. DFS
• B. A*
• C. Depth Limited Search
• D. BFS

Hint:

The quickest way to tell if a search algorithm is informed is to check if it uses a heuristic function (often denoted as h(n)). If it does (like A* or Greedy Best-First Search), it's informed. If it doesn't (like BFS, DFS, UCS), it's uninformed.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks to distinguish between uninformed and informed search algorithms and identify the one that does not belong to the uninformed category.
Step 2: Defining Search Algorithm Types:
- Uninformed Search (Blind Search): These algorithms explore the search space without having any information about the problem domain beyond the problem definition itself. They don't know if one non-goal state is "better" or "closer" to a goal than another. They simply follow a fixed strategy for generating and exploring nodes.
- Informed Search (Heuristic Search): These algorithms use problem-specific knowledge, in the form of a heuristic function, to guide the search. The heuristic function, h(n), estimates the cost of the cheapest path from the current state 'n' to a goal state. This allows the algorithm to prioritize exploring nodes that appear to be more promising.
Step 3: Detailed Explanation:
Let's categorize the given algorithms:
- (A) DFS (Depth-First Search): This algorithm explores as far as possible along each branch before backtracking. It does not use any heuristic to guide its path. It is a classic example of an uninformed search.
- (B) A* Search: This algorithm uses an evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the actual cost from the start node to node n, and $h(n)$ is the heuristic estimate of the cost from n to the goal. Because it uses the heuristic function $h(n)$, it is an informed search algorithm.
- (C) Depth Limited Search (DLS): This is a modification of DFS that imposes a depth limit on the search to prevent it from getting stuck in infinite paths. It is still an uninformed search strategy.
- (D) BFS (Breadth-First Search): This algorithm explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It does not use any heuristic. It is another classic uninformed search algorithm.
Step 4: Final Answer:
A* is the only algorithm in the list that uses a heuristic function to guide its search, making it an informed search algorithm. Therefore, it is NOT an example of an uninformed search.