论文标题
带有新价值功能的混合学习最大值子图问题
Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem
论文作者
论文摘要
最大常见的诱导子图（MC）是广泛的现实应用程序的重要NP硬性问题。分支结合（BNB）是MC的一类有效算法的基础，当发现不存在的解决方案比到目前为止发现的最佳解决方案更好时，包括连续选择以匹配和修剪的顶点。选择要匹配的顶点的方法对于BNB的性能至关重要。在本文中，我们提出了一种新的价值函数和一种用于加强学习定义新的顶点选择方法的混合选择策略，并针对MCS提出了一种称为MCSplitdal的新的BNB算法。广泛的实验表明，MCSPLITDAL显着改善了当前最佳BNB算法，MCSPLIT+LL和MCSPLIT+RL。还进行了经验分析，以说明为什么新的价值函数和混合选择策略有效。
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.
