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

摘要

Slater election is an optimization problem and NP-hard problem, which is generally considered that polynomial time ’s algorithms do not exist for solving .Given its complexity of solving is consistent with the complexity of answer set solving .There-fore, the paper proposes a new method of using ASP (answer set programming) to solve Slater election.First, it uses the satura-tion technology to build ASP model of logically equivalent for Slater election ;secondly , proves the correctness of the model;final-ly, calls the answer set solver DLV to solve specific examples of Slater election and shows its feasibility in the experimental re -sults.The proposed method can not only solve the Slater election problem , but also is the saturation technique used in ASP and provides a new logical representation approach for other similar optimization problem .%Slater选举是最优化问题，也是NP-hard问题，此类问题一般被认为不存在多项式时间的算法。考虑到其求解的复杂度与回答集求解的复杂度是一致的，为此，提出一种利用回答集程序（ Answer Set Programming ， ASP）求解Slater选举的新方法。首先，使用饱和技术为Slater选举建立逻辑上等价的ASP模型；其次，对模型进行正确性证明；最后，调用回答集求解器DLV求解Slater选举的具体实例，并在实验结果中说明其可行性。该方法不仅可求解Slater选举问题，而且在ASP中所使用的饱和技术还为其他同类的最优化问题提供了一种新的逻辑表示途径。