| 摘 要: 基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制量化分支顶点的剪枝效果,环境反馈则用双域个数来表征待搜索子图的大小。前向预测通过单边采样选择顶点模拟分支,并根据反馈确定最佳顶点。实验结果表明,新算法McSplitLA比McSplitDAL多解决7个算例,平均求解时间减少11.2%～17.9%,有效提高了剪枝率并优化了探索方向。 |
| 关键词: NP难问题 强化学习 最大公共诱导子图 分支策略 |
|
中图分类号: TP301.6
文献标识码: A
|
| 基金项目: 国家自然科学基金项目(U22B2017) |
|
| Maximum Common Induced Subgraph Algorithm Based on Feedback Scoring and Forward Prediction |
|
SUN Ke, LIU Yanli, HUANG Zhihao
|
(College of Science, Wuhan University of Science and Technology, Wuhan 430078, China)
jiner628@foxmail.com; yanlil2008@wust.edu.cn; hzh8268527@163.com
|
| Abstract: Reinforcement learning-based Maximum Common Induced Subgraph (MCIS) algorithms face limitations when handling vertices infrequently appearing in historical searches, making it difficult to evaluate their true importance and conduct effective exploration. To address this, a forward prediction method based on action and environmental feedback is proposed. Action feedback quantifies the pruning effect of branching vertices through a reward mechanism, while environmental feedback characterizes the size of the subgraph to be searched using double-domain counts. Forward prediction selects vertices for simulated branching via unilateral sampling and determines the optimal vertex based on feedback. Experimental results demonstrate that the new algorithm, McSplitLA, solves 7 more benchmark instances than McSplitDAL, reduces average solving time by 11.2%～17.9%, and effectively enhances pruning efficiency while optimizing search direction. |
| Keywords: NP-hard problem reinforcement learning maximum common induced subgraph branching strategy |
