|
Abstract : |
Randomized algorithms for solving hard satisfiability problems have been successfully applied to many application areas, but are still poorly understood. In this work, we show that, applied to SAT-encoded Hamilton circuit problems, GSAT with Random Walk (GWSAT) displays a very regular behaviour. In particular, the dependency of the success-rate on the maxSteps parameter for optimal walk probability can be charactarized by a simple algebraic function. We found an almost identical situation for GHC, a GSAT-variant adapted to the structure of the given problems class. Based on this observation, runtime estimates for given test-sets and parameter settings can be obtained. Furtheron this result shows that optimal speedup can be achieved for GWSAT (and GHC) when performing tries in parallel. The observed behaviour gives also rise to a novel interpretation of the search performed by GWSAT (and GHC) as an iterated blind probing in a much smaller, "virtual " searchspace the size of which is a measure for the search algorithms performance. We have evidence, that this concept can be also applied to other problem classes and local search algorithms. 1, |
