3 ms·
This is not the case, though. It is possible to eliminate vast portions of the full search space for some problems. I will not claim a full understanding of t
by taeric 12y ago
This is not the case, though. It is possible to eliminate vast portions of the full search space for some problems.
I will not claim a full understanding of this, but the latest volume of the Art of Computer Programming has some really deep treatments of this. The main takeaway being that it is possible to work with such things for many problems without just approximating. (Though, yes, for large N you do both approximations and clever algorithms that let you deal with as large of an N as possible.)
- raverbashing 12y agoYes, but vast portions of an even vast space is still a lot Of course, you can join both techniques and prune as much space heuristically then apply other algorithms to the remaining space.
- taeric 12y agoAgreed on it still being vast. I think I am just taking (unreasonable) exception to the term of heuristic here. Yes, naive brute force would have you look at about 10^7 positions for the classic 8-queens solution. However, there is no need to do this. Dancing links drops that number down to just over 10^3. Without sacrificing correctness/exactness.
- TheLoneWolfling 12y agoAnd for 100-queens? Or 1,000,000-queens?
- deleted 12y ago[deleted]
- taeric 12y agoNot sure where you think I am disagreeing that large problems are large. Consider, how long will it take for you to find the smallest of 10^99999 numbers? And again, I was probably just overly reacting to the term heuristic. That is usually used when it is implied you can't guess on the final outcome somehow. At least, that is how I typically read it. So yeah, odds are I'm just wrong. :)