| 一个求解加权MAX-SAT问题的改进算法 |
| |
| 引用本文： | 宋小华,李斌.一个求解加权MAX-SAT问题的改进算法[J].电脑编程技巧与维护,2009(Z1):28-29. |
| |
| 作者姓名： | 宋小华 李斌 |
| |
| 作者单位： | 空军航空大学; |
| |
| 摘 要： | 提出了一种加权MAX-SAT问题求解的改进算法,给出了启发式的命题变量选择方法和新的下界计算方法,改善了加权MAX-SAT问题剪枝效率。当子句规模变大时,其优点更为明显。新的算法具有实现简单、求解速度快、处理变量规模大的特点。
|
| 关 键 词： | 加权MAX-SAT 分支定界 |
A improved algorithm for Solving weighted MAX-SAT problems |
| |
| SONG Xiaohua,Li Bin.A improved algorithm for Solving weighted MAX-SAT problems[J].Computer Programming Skills & Maintenance,2009(Z1):28-29. |
| |
| Authors: | SONG Xiaohua Li Bin |
| |
| Affiliation: | SONG Xiaohua,Li Bin(Aviation University of Air force,Changchun 130022) |
| |
| Abstract: | We present a improved algorithm for weighted MAX-SAT, We provide a heuristic for selecting varible and provide a new method for computing lower bound. It made searching tree more efficient.When the number of clauses has increased,the advantage of the novel algorithm will be seen. The novel algorithm is better than a classical algorithm in the aspects of speed, the computing rate and the solvable problem scales. |
| |
| Keywords: | weighted MAX-SAT Branch and bound |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
