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

• 作者: 赖河蒗
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 回答集程序 Slater选举 饱和技术 求解器 启发式算法 最优化问题 NP-hard
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 人工智能
• 页码范围: 6-10,14
• 页数: 6页
• 分类号: TP18
• 字数: 5420字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2014.12.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赖河蒗		6	2	1.0	1.0