基于离散Lagrange方法的分布式SAT问题求解

Distributed SAT Solving Based on EDLM Method

基于对离散Lagrange方法(DLM)的扩充,提出一个分布式SAT求解算法:EDLMSAT。求解过程中,单个Agent的行为由预先定义的EDLM规则所决定,这些局部的行为聚集起来,形成整个系统对问题的求解趋势。设计了一些对3＿SAT基准问题的模拟实验,实验结果表明了这个算法良好的求解性能。

Distributed CSP solving is an active research field in artificial intelligence. Based on the method of extended discrete Lagrange multiplier (EDLM),a method for distributed SAT solving is proposed. During the SAT solving, each agent will determine its local behavior on some predefined EDLM rules. Although the behaviors are local, the agents can be corporately organized and aggregated to a coherent behavior to a solution. The Lagrange multipliers provide a more global level for agents to consider the SAT solving. Simulated experiments on some 3-SAT benchmark problems are conducted. The results show a competitive performance in solving.