title   
  

Revisiting constraint-directed search

Agren, Magnus and Flener, Pierre and Pearson, Justin (2009) Revisiting constraint-directed search. Information and Computation, 207 (3). pp. 438-457. ISSN 0890-5401

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1016/j.ic.2008.12.001

Abstract

In constraint-based local search the solutions are described declaratively by a conjunction of (often high-level) constraints. In this article we show that this opens up new ideas for constraint-directed search. For a constraint we introduce three neighbourhoods, where the penalty for that constraint alone is decreasing, increasing, or unchanged. We give specialised algorithms for common constraints that efficiently implement these neighbourhoods. Further, we give a general algorithm that implements these neighbourhoods from specifications of constraints in monadic existential second-order logic. Finally, we show how common constraint-directed local search algorithms are often easier to express using these neighbourhoods.

Item Type:Article
Uncontrolled Keywords:Constraint-based local search; Constraint-directed search; Monadic existential second-order logic
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:15041
Deposited By:Pierre Flener
Deposited On:05 Nov 2010 15:18
Last Modified:25 May 2011 14:20

Repository Staff Only: item control page