Inconsistency and Accuracy of Heuristics with A* Search
  Many studies in heuristic search suggest that the accuracy of the heuristic
used has a positive impact on improving the performance of the search. In
another direction, historical research perceives that the performance of
heuristic search algorithms, such as A* and IDA*, can be improved by requiring
the heuristics to be consistent -- a property satisfied by any perfect
heuristic. However, a few recent studies show that inconsistent heuristics can
also be used to achieve a large improvement in these heuristic search
algorithms. These results leave us a natural question: which property of
heuristics, accuracy or consistency/inconsistency, should we focus on when
building heuristics? While there are studies on the heuristic accuracy with the
assumption of consistency, no studies on both the inconsistency and the
accuracy of heuristics are known to our knowledge.
  In this study, we investigate the relationship between the inconsistency and
the accuracy of heuristics with A* search. Our analytical result reveals a
correlation between these two properties. We then run experiments on the domain
for the Knapsack problem with a family of practical heuristics. Our empirical
results show that in many cases, the more accurate heuristics also have higher
level of inconsistency and result in fewer node expansions by A*.
