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

摘要

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