Paper Info
Title
Vectorial Pattern Databases.
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.
Year
DOI
Venue
2015
10.3233/AIC-150666
AI COMMUNICATIONS
Keywords
DocType
Volume
Heuristic search,Pattern Databases,inconsistent heuristics
Journal
28
Issue
ISSN
Citations 
3
0921-7126
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Carlos Linares López19315.67