Maximum Common induced Subgraph (MCS) is an important NP-hard problem with wide real-world applications. Branch-and-Bound (BnB) is the basis of a class of efficient algorithms for MCS, consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.

本研究提出了一种新的基于深度强化学习的顶点选择方法与价值函数，应用于求解最大诱导公共子图问题的分支定界算法，并实验验证了新算法的效果明显优于目前最先进的算法McSplit+LL和McSplit+RL，同时分析证明了新的选择方法和价值函数的有效性。

用新的价值函数进行混合学习解决最大公共子图问题