کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426684 686154 2009 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Revisiting constraint-directed search
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Revisiting constraint-directed search
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 207, Issue 3, March 2009, Pages 438-457