4 ms·
Well a lot of prolog implementations also feature finite domain and rational domain solvers, global constrains that I don't think your 15 year old buddies would
by pdany 16y ago
Well a lot of prolog implementations also feature finite domain and rational domain solvers, global constrains that I don't think your 15 year old buddies would be able to code in an hour.
Having said that, most problems we solve here are NP-Complete, most of the time the trivial pruning you are mentioning does not really extend the limits for the computation.
- barrkel 16y agoFor sure, I was speaking in the context of the packing problems, and even simpler discrete combinatorial problems, which really are pretty simple. But I wouldn't dismiss trivial pruning lightly; many problems can have their search branches pruned early based on their costs exceeding the current best solution, and as that solution gets better, it will start pruning higher up the search tree. The knapsack problem, as you know, is NP-Complete.