GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 1

Question

Let $\text{b}$ be the branching factor of a search tree. If the optimal goal is reached after $\text{d}$ actions from the initial state, in the worst case, how many times will the initial state be expanded for iterative deepening depth-first search $\text{(IDDFS)}$ and iterative Deepening $\text{A*}$ search $\text{(IDA*)}$?

• A. $\text{IDDFS -d}$, $\text{IDA}$ $^{*}\text{-d}$.
• B. $\text{IDDFS}$ - $\text{d}$, $\text{IDA}$ $^{*}-\text{b}^{d}$
• C. $\text{IDDFS}$ $\text{-b}^{d}, \mathrm{IDA}^{*}\text{-d}$.
• D. $\text{IDDFS}$ $\text{-b}^{d}, \mathrm{IDA}^{*}\text{-b}^{d}$.

   

Comments

option B

Answer 1

Ans: D (not sure, please also read the comments below)
Reference : https://www.cs.ubc.ca/~mack/CS322/lectures/2-Search6.pdf

Comments

The answer will be D).

reference: Check comments of this stackoverflow page :

Link:  algorithm - Artificial Intelligence: Time Complexity of IDA* Search - Stack Overflow

(also can search: Korf, Time complexity of iterative-deepening-A∗ (2001))

---

@Sachin+Mittal+1

---

There are mentioned that how many times the initial state be expanded.. So, I think it is o(b+1)≈o(b) times.. If it given for depth state then it will be o(b^k).. May be..

Answer 2

Answer A. (Correct me if I wrong)

As they have ask how many time root(start/initial stage) expand so in both they expand(iterate) it d+1 time so answer should be A.

If IDDFS storing state previously visited it may be less than it is 1 in IDDFS

Comments

I think the answer should be B. The first node is expanded more than d times, and in worst-case scenarios, it can be b^d.we  choose threshold based on minimum proned node value.

Answer 3

IDA* we use cost function here,if evry child node has increasing values then we need to revisit start node. For we exploring a new node O(#total nodes:O(b^d)
same with IDDFS

so answer is option:D
Correct me if am wrong