Register

GO Classes DA Test Series | Artificial Intelligence | Search Algorithms | Question: 15

• edited by
387 views
2 2 votes

Consider the depth-limited search algorithm with depth limit f.
If the only goal state exists at depth $d$ then which of the following statement(s) is/are correct?

  1. If $\mathrm{f>d}$ then it is complete but not optimal.
  2. If $\mathrm{f>d}$ then it is not complete and not optimal.
  3. If $\mathrm{f}<\mathrm{d}$ then it is complete but not optimal.
  4. If $\mathrm{f}<\mathrm{d}$ then it is not complete and not optimal.

2 Answers

2 2 votes

If f > d, then the goal will be visited at some point hence the algorithm is complete. But it is clearly not optimal like depth first search. 

If f < d, then the goal will never be visited and hence the algorithm is not even complete.

1 1 vote

Logic for the option (A) to be correct:-

  • If all step costs are equal, the path to d is indeed the shortest(optimal).

  • However, if step costs vary (e.g., one edge has a weight of 10 and another has 1), DFS/DLS might find a path to depth d that has a much higher cumulative cost than a different path to that same node. Since DLS doesn't compare path costs, it isn't "Optimal."

Hence in totality(weighted or unweighted graph) it is not optimal.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · I am not able to acc...Next → · GO Classes DA Test S...
← Previous in category · GO Classes DA Test S...Next in category → · GO Classes DA Test S...
Position:
Show:

Related questions

1 1 vote
2 2 answers
389
389 views
GO Classes asked Jan 8, 2025
389 views
GO Classes DA Test Series | Artificial Intelligence | Search Algorithms | Question: 11
Consider the following search problem:Node$h_0$$h_1$$h_2$S056A035B042C025D053G000Which of the heuristics are admissible?$\mathrm{h_0}$$\mathrm{h_1}$$\mathrm{h_2}$None of ...
2 2 votes
2 2 answers
309
309 views
GO Classes asked Jan 8, 2025
309 views
GO Classes DA Test Series | Artificial Intelligence | Search Algorithms | Question: 13
Consider the game tree shown below. For which of the following values of $\mathrm{U}$,will the indicated pruning take place? $\mathrm{U=3}$$\mathrm{U=5}$$\mathrm{U=1}$$\m...
3 3 votes
4 4 answers
432
432 views
GO Classes asked Jan 8, 2025
432 views
GO Classes DA Test Series | Artificial Intelligence | Search Algorithms | Question: 14
Which of the following statements about search algorithms is/are true?Breadth-First Search is optimal when all edge costs are equal and non-negative.Depth-First Search is...
1 1 vote
1 1 answer
364
364 views
GO Classes asked Jan 8, 2025
364 views
GO Classes DA Test Series | Artificial Intelligence | Search Algorithms | Question: 3
Which of the following algorithms is/are guaranteed to give an optimal solution ( given no negative edges )?Greedy Best First Search$\mathrm{A}^{*}$ with zero heuristic$\...