计算机应用

作者：王宇, 刘燕丽, 陈劭武

单位：1. 武汉科技大学 理学院, 武汉 430081;2. 冶金工业过程系统科学湖北省重点实验室(武汉科技大学), 武汉 430081

关键词：组合优化问题,NP-Hard问题,强化学习,算法设计,最大公共子图

基金：湖北省大学生创新训练项目（S201910488044）；冶金工业过程系统科学湖北重点实验室开放基金资助项目（Y201716）。

针对最大公共子图（MCS）的传统分支策略依赖于图的静态属性，缺少学习历史搜索信息的问题，提出了基于顶点冲突学习的分支策略。首先，把上界的减少值作为分支点完成匹配动作的奖励；其次，由于当最优解被更新时，得到的最优解是分支点不断推理产生的结果，因此给予在完整的搜索路径上的分支点适当的奖励，从而强化这些顶点对搜索的积极作用；最后，设计了匹配动作的价值函数，并选择具有最大累计奖励的顶点作为新的分支点。在McSplit算法基础上，提出了糅合新分支策略的McSplitRLR算法。实验结果表明，除去均可以被所有对比算法在10 s之内解决的简单算例，在相同机器和求解限制时间条件下，相较当前先进的算法McSplit、McSplitSBS，McSplitRLR分别多解决了109、33个困难算例，求解率分别提高了5.6%、1.6%。

来源：2021年第6期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第6期