利用分支学习优化子图同构的搜索  

Using Branch Learning to Optimize the Search for Subgraph Isomorphism

作　　者：张梓涵 刘燕丽[1] 李春丽[1] 迟思义 ZHANG Zihan;LIU Yanli;LI Chunli;CHI Siyi(College of Science,Wuhan University of Science and Technology,Wuhan 430081,China)

机构地区：[1]武汉科技大学理学院,湖北武汉430081

出　　处：《软件导刊》2024年第3期88-93,共6页Software Guide

基　　金：国家自然科学基金项目(U22B2017);湖北省教育厅科学研究计划青年项目(Q20211111)。

摘　　要：子图同构问题是经典的、具有广泛实际应用的NP完全问题。针对精确算法的分支策略依赖顶点度,计算代价高的问题,提出结合无解记录和顶点度约束规则,通过混合分支学习策略减少求解时间的方法(SIBL)。无解记录是指算法每次重启前无目标解的分支路径,为了去除无效搜索,首先移除目标图中顶点度小于当前模式图顶点的候选顶点,然后移除出现在无解记录中的顶点,最后依据顶点分值进行降序排序,优先选择分值大的顶点。新策略提供了利用上界下降量计算单个顶点和顶点匹配对的两种分值计算方式,并交替使用两种分值选择分支顶点以快速寻找目标解,避免贪心选择的局部最优问题。通过测试14220个来自生物、图像等领域的算例发现,SIBL相较于当前领先的Glasgow、McSplit+RL_SI分别多解决了10.08%、19.88%的中等难度算例,验证了分支学习能有效改进子图同构算法的求解效率。Subgraph isomorphism problem is a classic and widely applicable NP complete problem.A hybrid branch learning strategy(SIBL)is proposed to reduce the solution time by combining solveless records and vertex degree constraint rules,in order to address the issue of high computational cost and dependence on vertex degree in precise algorithms.No solution record refers to the branch path without a target solution before each restart of the algorithm.In order to remove invalid searches,candidate vertices in the target graph with a vertex degree smaller than the current pattern graph vertex are first removed,and then vertices that appear in the no solution record are removed.Finally,descend⁃ing sorting is performed based on the vertex score,with priority given to selecting vertices with higher scores.The new strategy provides two score calculation methods that utilize the upper bound descent to calculate a single vertex and vertex matching pairs,and alternately use the two scores to select branch vertices to quickly find the target solution,avoiding the local optimal problem of greedy selection.Through testing 14220 examples from fields such as biology and imaging,it was found that SIBL is superior to the current leading Glasgow,McSplit+RL_SI solved 10.08%and 19.88%of moderately difficult cases respectively,verifying that branch learning can effectively improve the solving effi⁃ciency of subgraph isomorphism algorithms.

关 键 词：NP完全问题 子图同构问题 分支定界 约束规则 分支策略 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]