期刊文献+
任意字段
题名或关键词
题名
关键词
摘要
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到1篇文章
< 1 >
每页显示 20 50 100
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
On Optimizing the Satisfiability (SAT) Problem 认领 引用 被引量：2
1
作者 顾钧 堵丁柱 《Journal of Computer Science & Technology》 SCIE EI 1999年第1期1-17,共17页
The satisfiability(SAT) problem is a basic problem in computing theory. Presently, an active area of research on SAT problem is to design efficient optimization algorithms for finding a solution for a satisfiable CNF ... The satisfiability(SAT) problem is a basic problem in computing theory. Presently, an active area of research on SAT problem is to design efficient optimization algorithms for finding a solution for a satisfiable CNF formula. A new formulation, the Universal SAT problem model, which transforms the SAT problem on Boofean space into an optimization problem on real space has been developed. Many optimization techniques, such as the steepest descent method, Newton's method, and the coordinate descent method, can be used to solve the Universal SAT problem. In this paper, we prove that, when the initial solution is sufficiently close to the optimal solution, the steepest descent method has a linear convergence ratio β<1, Newton's method has a convergence ratio of order two, and the convergence ratio of the coordinate descent method is approximately (1-β/m) for the Universal SAT problem with m variables. An algorithm based on the coordinate descent method for the Universal SAT problem is also presented in this paper. 展开更多
关键词 satisfiability problem optimization algorithm nonlinear program- ming convergence ratio time complexity
暂未订购 下载PDF
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
在线咨询 使用帮助 返回顶部 意见反馈