Exploring the Impact of Early Decisions in Variable Ordering for Constraint Satisfaction Problems

Article English OPEN
José Carlos Ortiz-Bayliss; Ivan Amaya; Santiago Enrique Conant-Pablos; Hugo Terashima-Marín;
  • Publisher: Hindawi Limited
  • Journal: Computational Intelligence and Neuroscience,volume 2,018 (issn: 1687-5265, eissn: 1687-5273)
  • Related identifiers: doi: 10.1155/2018/6103726, pmc: PMC5842740
  • Subject: R858-859.7 | Research Article | Computer applications to medicine. Medical informatics | Neurosciences. Biological psychiatry. Neuropsychiatry | RC321-571 | Article Subject

When solving constraint satisfaction problems (CSPs), it is a common practice to rely on heuristics to decide which variable should be instantiated at each stage of the search. But, this ordering influences the search cost. Even so, and to the best of our knowledge, no ... View more
  • References (48)
    48 references, page 1 of 5

    Garey, M. R., Johnson, D. S.. Computers and Intractability: A Guide to the Theory of NP-Completeness . 1979

    Berlier, J. A., McCollum, J. M.. A constraint satisfaction algorithm for microcontroller selection and pin assignment. : 348-351

    Bochkarev, S. V., Ovsyannikov, M. V., Petrochenkov, A. B., Bukhanov, S. A.. Structural synthesis of complex electrotechnical equipment on the basis of the constraint satisfaction method. Russian Electrical Engineering . 2015; 86 (6): 362-366

    Brailsford, S. C., Potts, C. N., Smith, B. M.. Constraint satisfaction problems: algorithms and applications. European Journal of Operational Research . 1999; 119 (3): 557-581

    Hell, P., Nesetril, J.. Colouring, constraint satisfaction, and complexity. Computer Science Review . 2008; 2 (3): 143-163

    Williams, C. P., Hogg, T.. Using deep structure to locate hard problems. : 472-477

    Dechter, R.. Constraint networks. In Encyclopedia of Artificial Intelligence . 1992: 276-286

    Purdom, P. W.. Backtracking and random constraint satisfaction. Annals of Mathematics and Artificial Intelligence . 1997; 20 (1-4): 393-410

    Christensen, S., Oppacher, F.. What can we learn from no free lunch? a first attempt to characterize the concept of a searchable function. : 1219-1226

    Wolpert, D. H., Macready, W. G.. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation . 1997; 1 (1): 67-82

  • Metrics
    No metrics available
Share - Bookmark