Have Geek Brain

Trimming: When to Stop?

When does cropping stop being effective in depth-first search? I've been working on an effective method for solving the N-Queens problem and I'm looking at pruning for the first time. I've implemented it for the first two lines, but when does it stop being effective? How far should I crop?

+2


a source to share


2 answers


The N-Queens problem is usually recursive. Implementing trim at one depth should mean implementing trim at any depth.



The answer will depend on what you are doing. If you are pruning symmetrical moves, then it is not worth pruning when the verification cost is greater than the cost of evaluating the whole branch than the probability that the branch will be symmetric. For the N-Queens problem, symmetry is probably not a very fruitful trimming procedure after the first two lines.

+4


a source


I once saw a quote in this regard: "Trim early, trim often." And also: "Don't do anything stupid, don't do anything twice."



I think the amount of cropping you do should be dictated by your goals for the problem, or your boundaries on N.

+1


a source






More articles:


All Articles