CAJ | 학술논문

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。
용국부수색산법구해SAT문제．통상도수요재교대적린역중。심조합괄적린해。여과대린역중적매개린해。도통과중신판단매개자구시부위가만족래득도기가만족적자구개수．칙시간모비교다。이경유일사경전적처리방법．례여통과수개린역결구．래감소수색공간。종령외일개각도래고필수색과정．근거당전해화린해적내재관계．개소일충SAT린역적쾌속수색산법。해산법능재불영향해질량적전제하．쾌속심조합괄적린해．종이진일보제고국부수색산법적구해속도。령외．해산법환제공용우제고해질량적신식。유조우연구신적국부수색산법。
Using local search algorithm to solve SAT problem, usually needs to find the appropriate neighboring solution in the large neighborhood. It will be time-consuming to get the number of satisfied clauses for each neighboring solution through re-determine whether each clause is satisfied. There are some classical approaches, such as modifying the neighborhood structure to reduce the search space. Considers the search process from another point of view, and introduces a quick search algorithm of SAT neighborhood, according to the inherent relationship between the current solution and neighboring solutions. The algorithm can find out the appropriate neighboring solution quickly without effect the quality of solution, which will further enhance the solving speed of local search algorithm. In addition, the algorithm also provides information for improving the quality of solution to help research a new local search algorithm.