论文部分内容阅读
选举问题主要研究各种不同的选举规则可能带来的不同结果,它是社会选择理论中的一个重要研究方向。在选举理论中,孔多塞提出了用配对的比较结果来描述基于锦标赛形式的选举,并将获得最多选票的候选人称为孔多塞获胜者。但是,当不存在孔多塞获胜者的时候,判定哪个候选人是获胜者将变得是一项困难的任务。为了计算出一个获胜者,研究人员提出了许多不同的解决方案,这些不同的方案经常会使得选举结果产生不同的获胜者。同时,这些不同的解决方案也称为不同的选举问题。在已有的选举问题中,其中一些选举问题是NP完全问题。当这些选举问题采用启发式算法进行求解时存在执行效率低的问题,为此,提出一种基于回答集程序的求解方法,将选举问题转化为回答集程序的问题进行求解。
回答集程序设计是知识表示与推理领域中的一种新方法,同时也是用于问题求解的一个工具。回答集语义除了具有理论上的意义之外,基于该语义的逻辑程序也应用在许多实践中。在相关应用的推动下,回答集求解器的研究和开发成为了一个热门而且非常重要的方向。最近几年,已经研究出很多的回答集求解器,并将其用来计算逻辑程序的回答集。回答集求解器一般都是为了计算命题逻辑程序的回答集而设计的。为了处理包含变量的程序,回答集求解器通常都采用两层体系结构。其中整个求解器第一层的作用是专门把包含变量的程序转换为命题程序,即用来进行逻辑程序的实例化,它也称为求解器的前端部分;第二层的作用是接收由前端求解器实例化后得到的命题程序,并计算出回答集,它也称为整个求解器中最核心的部分,即回答集求解引擎。
本文首先使用回答集程序设计的方法来描述选举问题中的数据结构,并给出 Banks选举问题的回答集程序模型,同时用反证法证明了所建立的模型是具有正确性的;然后利用高效的回答集求解器实现对Banks选举问题的求解;最后用Java语言实现用户界面,提供数据输入以及结果输入等界面操作,取得了良好的交互效果。
由于高效的回答集求解器在求解NP完全问题上会表现出很好的效果,所以通过建立选举问题到回答集程序问题的映射,编写相对应的回答集程序,再调用回答集求解器进行求解,得到的每一个回答集模型就是选举问题的一个解。实验结果表明,采用这种实现方式能适应选举条件的变化,具有灵活和可扩展的特点,执行效率比采用专门针对这个特定问题的启发式算法要高。