[mcv]

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.

[towaway1138]

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.