# Artificial Intelligence Questions and Answers – Informed Search and Exploration

«
»

This set of Artificial Intelligence (AI) Questions and Answers for Aptitude test focuses on “Informed Search and Exploration”.

1. A heuristic is a way of trying ___________
a) To discover something or an idea embedded in a program
b) To search and measure how far a node in a search tree seems to be from a goal
c) To compare two nodes in a search tree to see if one is better than another
d) All of the mentioned

Explanation: In a heuristic approach, we discover certain idea and use heuristic functions to search for a goal and predicates to compare nodes.

2. A* algorithm is based on ___________
b) Depth-First –Search
c) Best-First-Search
d) Hill climbing

Explanation: Best-first-search is giving the idea of optimization and quick choose of path, and all these characteristic lies in A* algorithm.

3. The search strategy the uses a problem specific knowledge is known as ___________
a) Informed Search
b) Best First Search
c) Heuristic Search
d) All of the mentioned

Explanation: The problem specific knowledge is also known as Heuristics and Best-First search uses some heuristic to choose the best node for expansion.

4. Uninformed search strategies are better than informed search strategies.
a) True
b) False

Explanation: Informed search strategies uses some problem specific knowledge, hence more efficient to finding goals.

5. Best-First search is a type of informed search, which uses ________________ to choose the best next node for expansion.
a) Evaluation function returning lowest evaluation
b) Evaluation function returning highest evaluation
c) Evaluation function returning lowest & highest evaluation
d) None of them is applicable

Explanation: Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f (n). Traditionally, the node with the lowest evaluation is selected for expansion, because the evaluation measures distance to the goal.

6. Best-First search can be implemented using the following data structure.
a) Queue
b) Stack
c) Priority Queue
d) Circular Queue

Explanation: Best-first search can be implemented within our general search framework via a priority queue, a data structure that will maintain the fringe in ascending order of f-values.

7. The name “best-first search” is a venerable but inaccurate one. After all, if we could really expand the best node first, it would not be a search at all; it would be a straight march to the goal. All we can do is choose the node that appears to be best according to the evaluation function.
a) True
b) False

Explanation: If the evaluation function is exactly accurate, then this will indeed be the best node; in reality, the evaluation function will sometimes be off, and can lead the search astray.

8. Heuristic function h(n) is ________
a) Lowest path cost
b) Cheapest path from root to goal node
c) Estimated cost of cheapest path from root to goal node
d) Average path cost

Explanation: Heuristic is an estimated cost.

9. Greedy search strategy chooses the node for expansion in ___________
a) Shallowest
b) Deepest
c) The one closest to the goal node
d) Minimum heuristic cost

Explanation: Sometimes minimum heuristics can be used, sometimes maximum heuristics function can be used. It depends upon the application on which the algorithm is applied.

10. What is the evaluation function in greedy approach?
a) Heuristic function
b) Path cost from start node to current node
c) Path cost from start node to current node + Heuristic cost
d) Average of Path cost from start node to current node and Heuristic cost

Explanation: Greedy best-first search3 tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function: f (n) = h(n).

11. What is the space complexity of Greedy search?
a) O(b)
b) O(bl)
c) O(m)
d) O(bm)

Explanation: O(bm) is the space complexity where b is the branching factor and m is the maximum depth of the search tree. Since this algorithm resembles the DFS.

12. What is the evaluation function in A* approach?
a) Heuristic function
b) Path cost from start node to current node
c) Path cost from start node to current node + Heuristic cost
d) Average of Path cost from start node to current node and Heuristic cost

Explanation: The most widely-known form of best-first search is called A* search. It evaluates nodes by combining g(n), the cost to reach the node, and h(n.), the cost to get from the node to the goal: f(n) = g(n) + h(n). Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal.

13. A* is optimal if h(n) is an admissible heuristic-that is, provided that h(n) never underestimates the cost to reach the goal.
a) True
b) False

Explanation: A* is optimal if h(n) is an admissible heuristic-that is, provided that h(n) never overestimates the cost to reach the goal. Refer both the example from the book for better understanding of the algorithms.

Sanfoundry Global Education & Learning Series – Artificial Intelligence.

To practice all areas of Artificial Intelligence for Aptitude test, here is complete set of 1000+ Multiple Choice Questions and Answers on Artificial Intelligence. 