论文部分内容阅读
本文对SAT问题的随机局部搜索算法的执行轨迹进行Markov建模，并推导出算法的转移矩阵模型，分析随机局部搜索算法的通用框架，及三种算法变种：GSAT、RandomWalk、WalkSAT在选取子句和翻转原子上的不同策略；选用Markov建模方法来建立我们的转移矩阵的理论模型；通过概率方法抽象和定义，给出RandomWalk算法的基本转移矩阵模型。然后进一步推导出其他策略上的转移概率模型，包括GSAT、GCWSAT、WalkSAT等策略；对搜索空间的某些属性进行实验统计分析，得出其概率分布，并代入上述模型中，得到模型上的转移矩阵概率；通过大量随机SAT实例上的实验统计，得到实例规模上的转移矩阵概率。通过和上述理论模型上概率之间的比较，实验结果进一步验证我们的转移矩阵模型的正确性。