Modelling the dynamics of stochastic local search on <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="SmallCaps">sat</Emphasis> |
| |
Authors: | Nicolas G Fournier |
| |
Institution: | (1) EPO, Munich, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Algorithm analysis Experimental evaluation Stochastic algorithms Local search sat" target="_blank">k-sat |
本文献已被 SpringerLink 等数据库收录! |
|