An optimal backtrack algorithm for tree-structured constraint satisfaction problems
| Autor: | Daniel P. Miranker, Roberto J. Bayardo |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Linguistics and Language
Mathematical optimization Open problem Hybrid algorithm (constraint satisfaction) Constraint satisfaction Language and Linguistics Constraint (information theory) Tree (data structure) PEARL (programming language) Artificial Intelligence computer Time complexity Algorithm Constraint satisfaction problem Mathematics computer.programming_language |
| Zdroj: | Artificial Intelligence. 71:159-181 |
| ISSN: | 0004-3702 |
| Popis: | This paper presents and evaluates an optimal backtrack algorithm for solving tree-structured constraint satisfaction problems—a subset of constraint satisfaction problems which can be solved in linear time. Previous algorithms which solve these problems in linear time perform expensive preprocessing steps before attempting solution. The work presented here resolves the open problem posed by Dechter (1990) on the development of an algorithm which avoids this preprocessing. We demonstrate significant improvements in average-case performance over the previous state of the art, and show the benefits provided to backtrack enhancement schemes exploiting the easiness of tree-structured problems such as the cycle-cutset method (Dechter and Pearl, 1987). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|