《表2 自同构检测时间：基于对称破坏的子图同构约束求解算法》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《基于对称破坏的子图同构约束求解算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

在PDBSV2数据集中，算法求解平均时间见表1，其对应自同构检测时间见表2。表中参数“解的数量”用于比较在同一问题实例下，本文算法与其它算法求得解的数量。如在Q4规模下，VFSBC求得10 848个解，VF2求得13 696个解，说明其中有2848个解是重复解，在求解时，是不需要被计算的。实验结果显示，VFSBC算法的表现同样优于VF2及ILF算法。在规模为Q16时，本文算法的求解速度是VF2的1.55倍，统计Q4-Q128这6组实验组，其平均求解速度是VF2算法的1.18倍，平均减少1015个重复解。当模式图的规模处于Q32以下时，自同构检测时间依然占比甚微，但是随着模式图的规模增加，自同构检测的时间所占比例逐渐增大。因为自同构检测是一个连续发散的过程，一方面其检测时间受划分内单元数量影响；另一方面，其复杂度随搜索树深度的增加呈指数级增长。如何解决图规模增大带来的自同构检测负担，是需要进一步解决的问题。