基于回答集程序的 Slater 选举求解方法

摘要：

Slater选举是最优化问题，也是NP-hard问题，此类问题一般被认为不存在多项式时间的算法。考虑到其求解的复杂度与回答集求解的复杂度是一致的，为此，提出一种利用回答集程序（ Answer Set Programming ， ASP）求解Slater选举的新方法。首先，使用饱和技术为Slater选举建立逻辑上等价的ASP模型；其次，对模型进行正确性证明；最后，调用回答集求解器DLV求解Slater选举的具体实例，并在实验结果中说明其可行性。该方法不仅可求解Slater选举问题，而且在ASP中所使用的饱和技术还为其他同类的最优化问题提供了一种新的逻辑表示途径。

关键词：回答集程序、Slater选举、饱和技术、求解器、启发式算法、最优化问题、NP-hard

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金资助项目61173010

在线出版日期：2015-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：6-10,14