基于回答集编程的Banks选举求解方法  

Banks Election Solving Method Based on Answer Set Programming

作　　者：赖河蒗[1] 陈红英[1] 赖博先[1] 柯万添[1] 

机构地区：[1]华南师范大学计算机学院,广州510631

出　　处：《计算机工程》2013年第8期266-269,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(61173010)

摘　　要：采用启发式算法的Banks选举在进行求解时执行效率较低。为解决该问题,提出一种基于回答集编程(ASP)的求解方法。通过建立Banks选举问题到ASP问题的映射,编写相对应的ASP,调用回答集求解器进行求解,得到的每一个ASP模型就是Banks选举问题的一个解。实验结果表明,当问题规模为200时,该方法的求解时间为4.196 s,求解效率高于手工启发式方法。Banks election using a heuristic algorithm has the problem that the efficiency is low in the implementation,so this paper proposes a solving method based on Answer Set Programming（ASP）.It establishes the mapping from Banks election problem to the ASP problem,writes the corresponding ASP,calls the answer set solver to solve,and each ASP model obtained is a solution of the Banks election problem.Experimental results show that when the problem size is 200,the solving time of this method is 4.196 s,solving efficiency is better than that of manual heuristic method.

关 键 词：回答集编程 Banks选举 计算复杂度 求解器 启发式算法 最大传递子图 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]