000 04260nam a22005415i 4500
001 978-3-642-41482-4
003 DE-He213
005 20200421112554.0
007 cr nn 008mamaa
008 131029s2013 gw | s |||| 0|eng d
020 _a9783642414824
_9978-3-642-41482-4
024 7 _a10.1007/978-3-642-41482-4
_2doi
050 4 _aQ334-342
050 4 _aTJ210.2-211.495
072 7 _aUYQ
_2bicssc
072 7 _aTJFM1
_2bicssc
072 7 _aCOM004000
_2bisacsh
082 0 4 _a006.3
_223
100 1 _aHamadi, Youssef.
_eauthor.
245 1 0 _aCombinatorial Search: From Algorithms to Systems
_h[electronic resource] /
_cby Youssef Hamadi.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2013.
300 _aXIII, 139 p. 30 illus., 16 illus. in color.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
505 0 _aChap. 1 - Introduction -- Chap. 2 - Boosting Distributed Constraint Networks -- Chap. 3 - Parallel Tree Search for Satisfiability -- Chap. 4 - Parallel Local Search for Satisfiability -- Chap. 5 - Learning Variables Dependencies -- Chap. 6 - Continuous Search -- Chap. 7 - Autonomous Search -- Chap. 8 - Conclusion and Perspectives.
520 _aAlthough they are believed to be unsolvable in general, tractability results suggest that some practical NP-hard problems can be efficiently solved. Combinatorial search algorithms are designed to efficiently explore the usually large solution space of these instances by reducing the search space to feasible regions and using heuristics to efficiently explore these regions. Various mathematical formalisms may be used to express and tackle combinatorial problems, among them the constraint satisfaction problem (CSP) and the propositional satisfiability problem (SAT). These algorithms, or constraint solvers, apply search space reduction through inference techniques, use activity-based heuristics to guide exploration, diversify the searches through frequent restarts, and often learn from their mistakes. In this book the author focuses on knowledge sharing in combinatorial search, the capacity to generate and exploit meaningful information, such as redundant constraints, heuristic hints, and performance measures, during search, which can dramatically improve the performance of a constraint solver. Information can be shared between multiple constraint solvers simultaneously working on the same instance, or information can help achieve good performance while solving a large set of related instances. In the first case, information sharing has to be performed at the expense of the underlying search effort, since a solver has to stop its main effort to prepare and commu nicate the information to other solvers; on the other hand, not sharing information can incur a cost for the whole system, with solvers potentially exploring unfeasible spaces discovered by other solvers. In the second case, sharing performance measures can be done with little overhead, and the goal is to be able to tune a constraint solver in relation to the characteristics of a new instance - this corresponds to the selection of the most suitable algorithm for solving a given instance. The book is suitable for researchers, practitioners, and graduate students working in the areas of optimization, search, constraints, and computational complexity.
650 0 _aComputer science.
650 0 _aComputers.
650 0 _aComputer science
_xMathematics.
650 0 _aArtificial intelligence.
650 0 _aMathematical optimization.
650 0 _aComputational intelligence.
650 1 4 _aComputer Science.
650 2 4 _aArtificial Intelligence (incl. Robotics).
650 2 4 _aComputational Intelligence.
650 2 4 _aTheory of Computation.
650 2 4 _aOptimization.
650 2 4 _aDiscrete Mathematics in Computer Science.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783642414817
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-642-41482-4
912 _aZDB-2-SCS
942 _cEBK
999 _c59061
_d59061