Hacker News new | ask | show | jobs
by towaway1138 2701 days ago
As above, "IDFS" == "iterative deepening DFS".
1 comments

Yeah, I figured that out some time after I succeeded in digging through some old memory for the phrase "iterative deepening". It's been a while since I've had those classes. I do remember that at the time I didn't see the point in iterative deepening. Surely breadth first was faster than redoing the same work every time? But if you see it as a more memory-efficient way to simulate breadth-first through depth-first search, it makes sense.

Still, intuitively I'd expect that it depends a lot on the shape of your search space, the cost of your memory and the cost of traversing your network, which one is actually more efficient.

If you're generating nodes in an abstract graph (e.g., moves in chess), iterative deepening can be incredibly space-efficient, whereas BFS can rapidly consume an exponential amount of space.

As you point out, IDFS (or IDA*, etc) work far better if you have a means to avoid re-exploring the same nodes repeatedly.

Nonetheless, run-time can theoretically be greater, since you're iterating. Theoretically, though, each iteration will take N times longer than the prior, which means that the running time up to the final iteration doesn't matter that much (because it's such a small fraction of the total). The extra bookkeeping required by BFS can easily outmatch that in running time.

Definitely, it all depends.