Abstract: 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.

Key words: Answer Set Programming(ASP), Banks election, computation complexity, solver, heuristic algorithm, maximum transmission subgraph

摘要： 采用启发式算法的Banks选举在进行求解时执行效率较低。为解决该问题，提出一种基于回答集编程(ASP)的求解方法。通过建立Banks选举问题到ASP问题的映射，编写相对应的ASP，调用回答集求解器进行求解，得到的每一个ASP模型就是Banks选举问题的一个解。实验结果表明，当问题规模为200时，该方法的求解时间为4.196 s，求解效率高于手工启发式方法。

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

CLC Number: 

• TP18