caa a22 4500 463202694 CHVBK 20180405153116.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10732-007-9023-5 doi (NATIONALLICENCE)springer-10.1007/s10732-007-9023-5 Fournier Nicolas EPO, Munich, Germany aut Modelling the dynamics of stochastic local search on k - sat [Elektronische Daten] [Nicolas Fournier] A new analytical tool is presented to provide a better understanding of the search space of k-sat. This tool, termed the local value distribution , describes the probability of finding assignments of any value q′ in the neighbourhood of assignments of value q. The local value distribution is then used to define a Markov model to model the dynamics of a corresponding stochastic local search algorithm for k-sat. The model is evaluated by comparing the predicted algorithm dynamics to experimental results. In most cases the fit of the model to the experimental results is very good, but limitations are also recognised. Springer Science+Business Media, LLC, 2007 Algorithm analysis nationallicence Experimental evaluation nationallicence Stochastic algorithms nationallicence Local search nationallicence k - sat nationallicence Journal of Heuristics Springer US; http://www.springer-ny.com 13/6(2007-12-01), 587-639 1381-1231 13:6<587 2007 13 10732 https://doi.org/10.1007/s10732-007-9023-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10732-007-9023-5 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Fournier Nicolas EPO, Munich, Germany aut NATIONALLICENCE 773 0- Journal of Heuristics Springer US; http://www.springer-ny.com 13/6(2007-12-01), 587-639 1381-1231 13:6<587 2007 13 10732 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer