Vectorial Pattern Databases

Article type: Research Article

Authors: Linares López, Carlos

Affiliations: Computer Science Department, Universidad Carlos III de Madrid, Leganes (Madrid), Spain. E-mail: carlos.linares@uc3m.es

Abstract: Pattern Databases are among the most capable means for solving hard combinatorial problems. Since their conception, they have been enhanced along different directions. Recently, it has been shown that Pattern Databases can induce non-consistent heuristic functions and it has been conjectured that this sort of heuristic functions can be better informed than others. As a matter of fact, non-consistent heuristic functions allow specific rules to take place in order to propagate these inconsistencies with the hope of improving the heuristic estimates at some nodes. Also, it has been studied how to recognize infeasible values in Pattern Databases with the hope of being able to introduce corrections that would allow for more prunes. In this work, a new approach is suggested that fulfills both ideas simultaneously: inducing naturally non-consistent heuristic functions just by recognizing feasible, yet admissible, heuristic values which serve to improve even further the bidirectional pathmax propagation rules. Appealing as it might seem, this idea has various pros and cons which are examined. Experiments on different benchmarks show a noticeable improvement in the number of generated nodes over classical Pattern Databases when applicable, though the difference does not necessarily payoff in running time.

Keywords: Heuristic search, Pattern Databases, inconsistent heuristics

DOI: 10.3233/AIC-150666

Journal: AI Communications, vol. 28, no. 3, pp. 441-452, 2015