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}$.

   

Answer 1

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 2

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

Comments

Hi!
O(b^d) is the worst case time complexity of these algorithms. The question however asks for how many times will the initial node be expanded. Given the best alternative lies at depth d, there will be d iterations of the algorithm , and hence the initial node should be expanded d times. Not sure if I’m missing something.

---

@Aditya1205 $O(b^d)$ is the worst case complexity for IDDFS but not for $IDA^*$ because this is memory bounded heuristic search and here we are using the cutoff as $f-cost$ i.e. $g+h$ and not the depth $d.$ (if you mean “d” by depth of the tree).

So, here time complexity depends on many factors like the optimal cost function “$f$” in $f(n)=g(n)+h(n)$ and $f$ also depends on heuristic function $h$.

Rest of the things are correct and answer should be A.

---

please don't hide the answer if it contains some relevant comments. It might be useful for others.

There is nothing wrong with doing mistakes. Previously, I have also written some wrong answers here and it is fine to do mistakes. We are here for learning.

---

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))