When does pruning stop being efficient in a depth-first search? I've been working on an efficient method to solve the N-Queens problem and I'm looking at pruning for the first time. I've implemented it for the first two rows, but when does it stop being efficient? How far should I prune to?
+4
A:
The N-Queens problem is typically recursive. Implementing pruning at one depth should mean implementing it at any depth.
The answer would depend on what sort of pruning you're doing. If you're pruning for symmetric moves, then it's not worth pruning when the cost of checking is more than the cost of evaluating a whole branch times the probability of the branch being symmetric. For the N-Queens problem, symmetry is probably not a very fruitful pruning method after the first two rows.
Geoff
2010-04-23 20:36:42
A:
I once saw a quote regarding this, "Prune early; prune often." And another, "Don't do anything stupid; don't do anything twice."
I think that the amount of pruning that you do should be determined by your goals for the problem, or your boundaries on N.
hehewaffles
2010-04-23 23:51:55