优化计算slater投票获胜者的Picat方法

来源：计算机应用研究杂志2022年第8期北京时间：

作者：敖欢,王以松,冯仁艳,邓周灰,仝天乐,

单位：1.贵州大学a.计算机科学与技术学院;b.人工智能研究院,贵阳550025；2.贵安科创产业发展有限公司,贵阳550025；3.贵州黔驴科技有限公司,贵阳550025；

摘要：slater投票规则是基于锦标赛的投票规则，主要是通过构造无环锦标赛，找到与原锦标赛差异最小的一个，从中选出获胜者。针对求解难度为NP难的slater投票算法，提出了一种基于相似候选项集的优化求解slater问题的Picat方法。相比于非优化求解slater问题的方法，该方法缩小了slater算法的解空间，有效地减少了求解slater获胜者的计算量，提高了计算速度。实验结果表明，优化求解slater问题的Picat方法的计算速度优于非优化的Picat方法；当候选项人数少于20时，求解slater问题的回答集程序（ASP）方法的计算速度和计算能力优于优化的Picat方法，但当候选项人数超过30时，优化的Picat方法（用可满足问题求解器）的计算速度和计算能力优于ASP方法。

关键词：slater投票问题,NP难问题,约束满足问题,Picat程序设计,锦标赛,线性序列,

基金资助：国家自然科学基金资助项目(61976065,U1836205)；；