基于回答集程序的基于选举问题研究

来源 :华南师范大学 | 被引量 : 0次 | 上传用户:yydxpjg
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
选举问题主要研究各种不同的选举规则可能带来的不同结果,它是社会选择理论中的一个重要研究方向。在选举理论中,孔多塞提出了用配对的比较结果来描述基于锦标赛形式的选举,并将获得最多选票的候选人称为孔多塞获胜者。但是,当不存在孔多塞获胜者的时候,判定哪个候选人是获胜者将变得是一项困难的任务。为了计算出一个获胜者,研究人员提出了许多不同的解决方案,这些不同的方案经常会使得选举结果产生不同的获胜者。同时,这些不同的解决方案也称为不同的选举问题。在已有的选举问题中,其中一些选举问题是NP完全问题。当这些选举问题采用启发式算法进行求解时存在执行效率低的问题,为此,提出一种基于回答集程序的求解方法,将选举问题转化为回答集程序的问题进行求解。   回答集程序设计是知识表示与推理领域中的一种新方法,同时也是用于问题求解的一个工具。回答集语义除了具有理论上的意义之外,基于该语义的逻辑程序也应用在许多实践中。在相关应用的推动下,回答集求解器的研究和开发成为了一个热门而且非常重要的方向。最近几年,已经研究出很多的回答集求解器,并将其用来计算逻辑程序的回答集。回答集求解器一般都是为了计算命题逻辑程序的回答集而设计的。为了处理包含变量的程序,回答集求解器通常都采用两层体系结构。其中整个求解器第一层的作用是专门把包含变量的程序转换为命题程序,即用来进行逻辑程序的实例化,它也称为求解器的前端部分;第二层的作用是接收由前端求解器实例化后得到的命题程序,并计算出回答集,它也称为整个求解器中最核心的部分,即回答集求解引擎。   本文首先使用回答集程序设计的方法来描述选举问题中的数据结构,并给出 Banks选举问题的回答集程序模型,同时用反证法证明了所建立的模型是具有正确性的;然后利用高效的回答集求解器实现对Banks选举问题的求解;最后用Java语言实现用户界面,提供数据输入以及结果输入等界面操作,取得了良好的交互效果。   由于高效的回答集求解器在求解NP完全问题上会表现出很好的效果,所以通过建立选举问题到回答集程序问题的映射,编写相对应的回答集程序,再调用回答集求解器进行求解,得到的每一个回答集模型就是选举问题的一个解。实验结果表明,采用这种实现方式能适应选举条件的变化,具有灵活和可扩展的特点,执行效率比采用专门针对这个特定问题的启发式算法要高。
其他文献
超高层建筑的施工是一个复杂的系统工程,涉及到大量的人员、设备和材料。如何在保证施工质量的前提下,尽可能的缩短工程施工时间以节约施工成本,这是每个建筑施工企业都非常关注
XML以其强大的功能,在计算机领域得到了广泛的应用,已经成为信息描述和交换的一种标准技术。XQuery被设计用来查询XML数据,树模式查询作为XQuery查询的核心,其查询效率问题成
OLAP(On-Line Analytical Processing)是一种强有力的数据可视化工具,它专门设计各种用于支持复杂分析的操作,使得管理决策人员能够对数据仓库中海量数据进行深入观察。但是,OLA
随着我国计算机网络的快速发展,黑客入侵攻击事件发生的概率随之增大,对网络安全的研究也越来越引起人们的重视。而计算机系统和网络设备上广泛存在的漏洞是成为被黑客攻击的最
关键词检索是互联网中使用最广泛的检索技术之一,也是世界上一些著名互联网站点比如谷歌、维基百科、亚马逊和IMDB等的默认检索方式。传统的关键词检索技术主要是针对无结构化
语音增强技术是进行一系列语音信号处理中的基本问题,是语音处理系统里的核心技术之一。近年来,麦克风阵列语音增强方法由于融合了语音信号空时信息,能够获得较单通道更好的增强
随着信息科学技术的发展,虚拟现实系统中的数据量和计算量正在呈爆炸式增长,传统的依靠本地文件系统和私有协议存储、管理和分发数据的方式已经难以满足快速增长的用户需求。因
在计算机网络高度繁荣的今天,众多的计算机恶意程序时刻威胁着计算机安全。近年来许多已知恶意程序以新变种的方式死灰复燃,而完全未知的恶意程序利用传统恶意程序检测方法响应
随着计算机技术在行业应用中的不断深入,数据库技术和时态信息技术不断获得发展的动力。技术的关注点已从过去的信息记录处理逐步延伸到信息的有效性和时间性。特别是在电信、
近几年来,移动互联网技术和应用快速发展,移动多媒体服务随着智能手机的普及而日益成为人们的新需求。同时,显示技术的不断进步使得智能手机能够支持高清甚至是超高清视频的显示