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

Optimizing Picat method for calculating slater voting winners

作　　者：敖欢 王以松[1,2] 冯仁艳 邓周灰 仝天乐 Ao Huan;Wang Yisong;Feng Renyan;Deng Zhouhui;Tong Tianle(School of Computer Science&Technology,Guizhou University,Guiyang 550025,China;Institute of Artificial Intelligence,Guizhou University,Guiyang 550025,China;Kechuang Industrial Development Co.Ltd.,Guiyang 550025,China;Guizhou Donkey Technologies Co.Ltd.,Guiyang 550025,China)

机构地区：[1]贵州大学计算机科学与技术学院,贵阳550025 [2]贵州大学人工智能研究院,贵阳550025 [3]贵安科创产业发展有限公司,贵阳550025 [4]贵州黔驴科技有限公司,贵阳550025

出　　处：《计算机应用研究》2022年第8期2268-2272,共5页Application Research of Computers

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

摘　　要：slater投票规则是基于锦标赛的投票规则,主要是通过构造无环锦标赛,找到与原锦标赛差异最小的一个,从中选出获胜者。针对求解难度为NP难的slater投票算法,提出了一种基于相似候选项集的优化求解slater问题的Picat方法。相比于非优化求解slater问题的方法,该方法缩小了slater算法的解空间,有效地减少了求解slater获胜者的计算量,提高了计算速度。实验结果表明,优化求解slater问题的Picat方法的计算速度优于非优化的Picat方法;当候选项人数少于20时,求解slater问题的回答集程序(ASP)方法的计算速度和计算能力优于优化的Picat方法,但当候选项人数超过30时,优化的Picat方法(用可满足问题求解器)的计算速度和计算能力优于ASP方法。The slater voting rule is a tournament-based voting rule.It mainly constructs a ringless tournament,finds the one with the smallest difference from the original tournament,and selects the winner from it.Aiming at the NP-hard slater voting algorithm,this paper proposed a Picat method to solve the slater problem based on the optimization of similar candidate item sets.Compared with the non-optimized Picat method for solving the slater problem,this method reduced the solution space of the slater algorithm,effectively reduced the amount of calculation for solving the slater winner,and improved the calculation speed.The experimental results show that the computational speed of the optimized Picat method for solving the slater problem is better than that of the non-optimized.When the number of candidates is less than 20,the computational speed and computing power of the answer set program(ASP)method for solving the slater problem are better than those of the optimized Picat method,but when the number of candidates exceeds 30,the optimized Picat method(with a satisfiable problem solver)outperforms the ASP method in terms of computational speed and computational power.

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

分 类 号：TP305[自动化与计算机技术—计算机系统结构]