A Variable Depth Search Algorithm for Binary Constraint Satisfaction Problems
Author
Source
Mathematical Problems in Engineering
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-10-25
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
The constraint satisfaction problem (CSP) is a popular used paradigm to model a wide spectrum of optimization problems in artificial intelligence.
This paper presents a fast metaheuristic for solving binary constraint satisfaction problems.
The method can be classified as a variable depth search metaheuristic combining a greedy local search using a self-adaptive weighting strategy on the constraint weights.
Several metaheuristics have been developed in the past using various penalty weight mechanisms on the constraints.
What distinguishes the proposed metaheuristic from those developed in the past is the update of k variables during each iteration when moving from one assignment of values to another.
The benchmark is based on hard random constraint satisfaction problems enjoying several features that make them of a great theoretical and practical interest.
The results show that the proposed metaheuristic is capable of solving hard unsolved problems that still remain a challenge for both complete and incomplete methods.
In addition, the proposed metaheuristic is remarkably faster than all existing solvers when tested on previously solved instances.
Finally, its distinctive feature contrary to other metaheuristics is the absence of parameter tuning making it highly suitable in practical scenarios.
American Psychological Association (APA)
Bouhmala, Noureddine. 2015. A Variable Depth Search Algorithm for Binary Constraint Satisfaction Problems. Mathematical Problems in Engineering،Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1074355
Modern Language Association (MLA)
Bouhmala, Noureddine. A Variable Depth Search Algorithm for Binary Constraint Satisfaction Problems. Mathematical Problems in Engineering No. 2015 (2015), pp.1-10.
https://search.emarefa.net/detail/BIM-1074355
American Medical Association (AMA)
Bouhmala, Noureddine. A Variable Depth Search Algorithm for Binary Constraint Satisfaction Problems. Mathematical Problems in Engineering. 2015. Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1074355
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1074355