基于几何规划的布尔可满足问题求解方法

J4 ›› 2013, Vol. 35 ›› Issue (9): 122-126.

基于几何规划的布尔可满足问题求解方法

何安平，吴尽昭，梁艺，熊玲芳，吴昊

（广西民族大学混杂计算与集成电路设计分析重点实验室，广西南宁 530006）

收稿日期:2013-03-09 修回日期:2013-07-29 出版日期:2013-09-25 发布日期:2013-09-25
基金资助:
广西自然科学基金资助项目（2011GXNSFA018154，2012GXNSFGA060003，2013GXNSFAA019342）；广西区主席科技资金（101691）;广西教育厅科研资助项目（201012MS274）;广西“八桂”学者项目

The continuous solution of SAT problem
based on geometric programming

HE Anping,WU Jinzhao,LIANG Yi,XIONG Lingfang,WU Hao

（Guangxi Key Lab of Hybrid Computation and IC Design Analysis,Guangxi University for Nationalities,Nanning 530006,China）

Received:2013-03-09 Revised:2013-07-29 Online:2013-09-25 Published:2013-09-25

摘要/Abstract

摘要：

布尔可满足问题是计算机科学中诸多领域的重要问题，它的快速求解具有十分重要的意义。将具有实际物理背景的Solar算法中的拟物算法与几何规划相结合，提出并实现了一种布尔可满足性问题的连续求解方法。经实验验证，这种算法对布尔可满足性问题的求解具有一定的实用价值。

关键词: 布尔可满足性, 拟物拟人算法（Solar）, 几何规划

Abstract:

The Boolean satisfiability problem (SAT) is fundamental in many fields of computer science; so its fast solution is of great significance. The Solar algorithm is one of the famous quick SAT solutions. We combine the basic Solar algorithm with geometric programming method to propose a novel continuous solution of SAT problem. Experiments demonstrate that the proposal has potential applicable value for solving SAT problems.

Key words: SAT;solar algorithm;geometric programming

何安平，吴尽昭，梁艺，熊玲芳，吴昊. 基于几何规划的布尔可满足问题求解方法[J]. J4, 2013, 35(9): 122-126.

HE Anping,WU Jinzhao,LIANG Yi,XIONG Lingfang,WU Hao. The continuous solution of SAT problem
based on geometric programming [J]. J4, 2013, 35(9): 122-126.