基于动态规划的优先语义扩充求解算法

Preferred semantics extension algorithm based on dynamic programming

抽象辩论框架中的优先语义是判断争议可接受程度的最重要语义。现有优先扩充求解方法多用标记映射求解,依赖于标记的定义、转换规则、相邻争议的标记。算法每次迭代会产生一个新的抽象辩论框架导致时间、空间复杂度较高。提出一种基于动态规划的优先扩充算法,在动态规划中加入争议可接受性判断,求出辩论框架中极大可容许集得到优先扩充。在基于随机抽象辩论框架与ICCMA提供的数据集进行实验,同Heureka、ArgSemSAT等算法进行对比。结果表明,求解相同数量的优先扩充,算法耗时较少,时间、空间复杂度有所降低。

The preferred semantics in the abstract argumentation framework is the most important semantics for judging the acceptability of arguments.The existing preferred expansion solving methods mostly use marker mapping to solve,which depends on the definition of markers,conversion rules,and the markers of adjacent arguments.Each iteration of the algorithm will gene-rate a new abstract argumentation framework,resulting in high time and space complexity.This paper proposed preferred expansion algorithm based on dynamic programming,and added the judgment of the acceptability of arguments to the dynamic pro-gramming,and obtained the maximum admissible set in the argumentation framework by preferred expansion.This paper conducted experiments based on the random abstract argumentation framework and the data set provided by ICCMA,and compared the proposed algorithm with algorithms such as Heureka and ArgSemSAT.The results show that,to solve the same number of preferred expansions,the algorithm consumes less time and reduces the time and space complexity.