《表1 占优子图挑选的算法》

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

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

《一种基于图塌缩的药物分子检索方法》

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

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

在以塌缩方式处理非环子图结构之前，还有一个重要的障碍需要克服，即非环子图之间的重叠问题。由于可用于塌缩的候选非环子图有多种选择，它们之间存在着相交（两个子图某些部分重叠）或包含（一个子图完全位于另一个子图内部）等交叠现象，甚至同一类型的子图在同一分子结构图中也会出现多次且会互相重叠（λiGjf>1）。不同的选择将会导致不同的塌缩结果，进而生成不同的超图。本研究希望能够构建最小的超图，使得后续的检索匹配代价最低，为此需要在分析各种交叠可能性的基础上寻找最佳的非环子图组合方案。在算法设计中，本文将寻找非环子图组合方案的问题转换为“最优子图覆盖”问题，即给定一个图和一组子图，当挑选其中一些子图满足以下两个条件时，这些子图构成对该图的一个最优覆盖:（1）两两之间不存在交叠；（2）在所有挑选方案中对该图的覆盖面积最大。然而，“枚举所有覆盖情况，选择覆盖范围最大的集合”是一个已知的NP-hard问题。于是，本研究提出了一种基于占优子图的启发式算法（表1），基于每个频繁子图Gfj的规模︱Vfj︱和支持度H（Gfj）定义其占优度ω: