Abstract:
Given a set of problems, a set of heuristics, and assuming that everything else is equal, it is never worse and usually better to solve each problem with the heuristic that is best for that problem than to use, for all problems, the heuristic that is best, on average, for the set of problems. Unfortunately, everything else is seldom equal. In particular, the cost of determining which heuristic is best, on average, is usually cheaper than determining for each problem, which is best. But, does this mean that when you include the costs of determining the best heuristic that the former approach (i.e. determining for each problem which is best for it) is always worse, on average, than the latter approach? This is not the case if the average cost of determining the best heuristic, for each problem, is lower than the average cost advantage of using it. However, how low can we bring this cost? This paper introduces two new data structures, minTrees and culprit counter lattices, that lower this cost and then we compare using this approach with these data structures against simply using a known effective compact pattern database variation. The experiments show that the key to success is finding cost-effective predictions of which heuristic will be best for a problem rather than precisely determining which is best. While our experiments do not provide conclusive proof that it is better on average to determine, for each problem, the best heuristic, it does provide evidence that suggests this can be the case.
