摘要： 针对求解复杂度为NP难问题的Slater选举，提出一种回答集程序设计（ASP）方法用于求解选举结果。通过ASP构造尽可能少的无回路锦标赛，找到与原锦标赛差别最小的一个并从中选出获胜者。实验结果表明，该方法的编码方式不依赖于候选人的数量，时间复杂度低，可读性强，并且适用于Kemeny选举。

关键词: Slater选举, Kemeny选举, NP难问题, 回答集程序设计, 锦标赛

Abstract: To address Slater voting which is NP-hard problem,this paper proposes an Answer Set Programming (ASP) method for calculating voting result.The method constructs the minimum number of no circuit tournament,finds the one with the smallest difference from the original tournament,and selects the winner.Experimental results show that the method is coded in a way independent of the number of candidates.Also,the readable method has a low time complexity,and is suitable for Kemeny elections.

Key words: Slater voting, Kemeny voting, NP-hard problem, Answer Set Programming(ASP), tournament

中图分类号: 

• TP18