基于回答集程序的Slater选举求解方法

doi:10.3969/j.issn.1006-2475.2014.12.002

计算机与现代化

基于回答集程序的Slater选举求解方法

（广东司法警官职业学院，广东广州 510520)

收稿日期:2014-09-17 出版日期:2014-12-22 发布日期:2014-12-22
作者简介:赖河蒗（1985-），男，广东罗定人，广东司法警官职业学院助教，硕士，研究方向：决策支持系统，自动推理。
基金资助:
国家自然科学基金资助项目(61173010)

Slater Election Solving Method Based on Answer Set Programming

(Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Received:2014-09-17 Online:2014-12-22 Published:2014-12-22

摘要/Abstract

摘要： Slater选举是最优化问题，也是NP-hard问题，此类问题一般被认为不存在多项式时间的算法。考虑到其求解的复杂度与回答集求解的复杂度是一致的，为此，提出一种利用回答集程序（Answer Set Programming, ASP）求解Slater选举的新方法。首先，使用饱和技术为Slater选举建立逻辑上等价的ASP模型；其次，对模型进行正确性证明；最后，调用回答集求解器DLV求解Slater选举的具体实例，并在实验结果中说明其可行性。该方法不仅可求解Slater选举问题，而且在ASP中所使用的饱和技术还为其他同类的最优化问题提供了一种新的逻辑表示途径。

关键词: 回答集程序, Slater选举, 饱和技术, 求解器, 启发式算法, 最优化问题, NP-hard

Abstract: Slater election is an optimization problem and NP-hard problem, which is generally considered that polynomial time’s algorithms do not exist for solving. Given its complexity of solving is consistent with the complexity of answer set solving. Therefore, the paper proposes a new method of using ASP (answer set programming) to solve Slater election. First, it uses the saturation technology to build ASP model of logically equivalent for Slater election; secondly, proves the correctness of the model; finally, calls the answer set solver DLV to solve specific examples of Slater election and shows its feasibility in the experimental results. The proposed method can not only solve the Slater election problem, but also is the saturation technique used in ASP and provides a new logical representation approach for other similar optimization problem.

Key words: answer set programming (ASP), Slater election, saturation technique, solver, heuristic algorithm, optimization problem, NP-hard

中图分类号:

TP18

赖河蒗. 基于回答集程序的Slater选举求解方法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2014.12.002.

LAI He-lang. Slater Election Solving Method Based on Answer Set Programming[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.12.002.

参考文献

[1] Chevaleyre Y, Endriss U, Lang J, et al. A short introduction to computational social choice[C]// Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science. 2007:51-69.

[2] Hudry O. On the complexity of Slater's problems[J]. European Journal of Operational Research, 2010,203(1):216-221.

[3] Slater P. Inconsistencies in a schedule of paired comparisons[J]. Biometrika, 1961,48(3-4):303-312.

[4] Lifschitz V. Answer set programming and plan generation[J]. Artificial Intelligence, 2002,138(1-2):39-54.

[5] Apt K, Bol B. Logic programming and negation: A survey[J]. Journal of Logic Programming, 1994,19-20(S1):9-71.

[6] Gelfond M, Lifschitz V. The stable model semantics for logic programming[C]// Proceedings of the 5th International Conference and Symposium on Logic Programming. 1988:1070-1080.

[7] Baral C, Gelfond M. Logic programming and knowledge representation[J]. Journal of Logic Programming, 1994,19-20(S1):73-148.

[8] Leone N, Pfeifer G, Faber W, et al. The DLV system for knowledge representation and reasoning[J]. ACM Transactions on Computational Logic, 2006,7(3):499-562.

[9] Simons P, Niemela I, Soininen T. Extending and implementing the stable model semantics[J]. Artificial Intelligence, 2002,138(1-2):181-234.

[10] Gebser M, Kaufmann B, Neumann A, et al. Conflict-driven answer set solving[C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI2007). 2007:386-392.

[11] 李鑫,李凡,边杏宾,等. E-R模型的回答集编程表示[J]. 计算机研究与发展, 2010,47(1):164-173.

[12] 赵岭忠,王雪松,钱俊彦,等. 从经典逻辑知识构建ASP知识库的新方法[J]. 计算机应用, 2010,30(11):2932-2936.

[13] 吕勇全,陈寅,邬家炜,等. 基于回答集程序的排课系统设计与实现[J]. 计算机技术与发展, 2010,20(6):228-232.

[14] 王洁,韩雪平,赵丽丽,等. ￢RDF推理中不一致问题研究[J]. 计算机工程, 2012,38(7):152-154.

[15] 张青伟,赵岭忠. 回答集程序设计在TTP求解中的应用[J]. 桂林电子科技大学学报, 2010,30(4):305-309.

[16] 王雪松,赵岭忠,张超. 基于ASP的CSP模型验证性质反例生成技术研究[J]. 计算机应用研究, 2013,30(1):52-55.

[17] Eiter T, Gottlob G, Mannila H. Disjunctive datalog[J]. ACM Transactions on Database Systems, 1997,22(3):364-418.

[18] Baral C. Knowledge Representation, Reasoning, and Declarative Problem Solving[M]. Cambridge University Press, 2003.

[19] Erdem E, Lifschitz V. Tight logic programs[J]. Theory and Practice of Logic Programming, 2003,3(4-5):499-518.

基于回答集程序的Slater选举求解方法

Slater Election Solving Method Based on Answer Set Programming

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	赵然1,2，郭志川1,2,朱小勇1,2. 一种基于Levy飞行的改进蝗虫优化算法[J]. 计算机与现代化, 2020, 0(01): 104-.
[2]	姜凯华1,2，孙鹏1,2，韩锐1. 一种结合灰狼和FM算法的云端应用解构方法[J]. 计算机与现代化, 2020, 0(01): 53-.
[3]	朱洋洋. 混合花粉算法求解全局优化问题[J]. 计算机与现代化, 2019, 0(10): 48-.
[4]	刘姚，宋振明. 基于变量决策层的启发式变量选择策略[J]. 计算机与现代化, 2019, 0(07): 20-.
[5]	刘姚1,2，宋振明1. 基于学习子句长度和LBD的删除策略[J]. 计算机与现代化, 2019, 0(05): 92-.
[6]	包沙如拉1,2，孙鹏1,2，韩锐1,2，郭志川1,2. 一种海云协同媒体服务系统副本放置算法[J]. 计算机与现代化, 2018, 0(09): 93-.
[7]	李玥，王念新，葛世伦. IaaS云服务定价机制的仿真研究[J]. 计算机与现代化, 2014, 0(11): 20-26.
[8]	徐路路;张丽萍;郭越. 代码分析中的层次式静态检测方法[J]. 计算机与现代化, 2013, 1(9): 58-61,6.