Re:The Prolog Story
by barrkel on Thursday May 20, 2010 @05:38PM
(#1365521)
For 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.
The knapsack problem, as you know, is NP-Complete.