一种用于Slater与Kemeny选举求解的ASP方法  

An ASP Method for Calculating Slater and Kemeny Voting

作　　者：徐珩僭 王以松[1] 冯仁艳 XU Hengjian;WANG Yisong;FENG Renyan(School of Computer Science and Technology,Guizhou University,Guiyang 550025,China)

机构地区：[1]贵州大学计算机科学与技术学院

出　　处：《计算机工程》2019年第9期198-203,共6页Computer Engineering

基　　金：国家自然科学基金“基于增强学习的动态优化问题模型及算法研究”(61562009);贵州省优秀科技人才基金(2015(01))

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]