子图匹配算法研究(2)
时间:2019-07-21 09:56 来源:毕业论文 作者:毕业论文 点击:次
本文研究的是后者，首先分析采用静态消耗测算模式的子图匹配查询的优点和缺点，并根据信息熵的作用，将信息熵引入匹配算法，通过研究实验对两类算法进行比较，看谁的计算效率更高。 2 概念介绍 2.1子图匹配的的有关定义 本文需要的子图匹配相关的三个概念：图数据 ；查询子图；置换映射； 将G作为一个图数据，即G=<V,E,L>。其中V表示点集合；L是标签的集合；E V×L×V表示边集合； 用Q表示查询子图过程中出现的集合对，即（Vq，Eq）； 用θ表示子图查询时的映射，即VARq V； 2.2子图同构问题的定义 子图同构就是给定两个图G与H作为输入，然后判定其存在的映射同构关系，下面就用两个简单的图结构来解释一下映射同构，如下图A和图B所示： 对于给定的两个图，是从节点数目大的那个图中寻找部分节点和边，和节点数目小的那个图是同构。很显然我们要从图A中找到与图B的同构图，首先我们从顶点V1为顶点搜索它的每个邻接点，先搜索左边，搜索到V2节点处时左边路径上的节点都已被访问过，搜索将回溯到顶点V1，重新选择路径，搜索到V3处时，该路径上的节点也都被访问过，然后我们以V4为顶点进行查询，因为顶点V4只有一条搜索路径图B的结构不符合，所以可以排除。最终我们可以从图 2.3信息熵 香农根据热物理学中熵的理论提出了信息熵概念，用来解决信息的量化度量问题[10]。信息熵是个比较能够抽象的概念，在现实中计算很复杂很难计算出来，但是它可以被测定出来。该定义比较抽象，下面我举一个简单的例子来更好地解释一下：在新一轮的NBA联赛中，人们都想在猜想最后的冠军是谁。假如我错过了看比赛，又很想知道冠军是谁。赛后我问了一个知道答案的人，他不想直接告诉我要让我猜，猜一次需要给他10钱，然后告诉我猜得对不对。那么问起来了，我需要给他多少钱才能知道冠绝是谁呢？如果木有目的性的随意猜或者挨个猜，很显然需要猜很多次，但是不排除一次猜对的可能性。其实可以把这30是支球队变成数字，1到30，然后问他冠军实在1到15号中吗？如果才对了，就会继续问他是在1到8中吗，如果错了，冠军很显然就在9到15中，这样最多只需要五次，就能猜出冠军是谁。如果刚开始我们排除一些不可能夺冠的队伍，把剩下可能的一部分球队进行编排猜测的话，可以更快的猜出结果。 从这个例子中我们可以看出，对于一个问题的不确定性我们可以通过添加约束条件来缩小它的搜索查询空间，提高效率。子图同构问题和这个例子基本上相似，在查询数据库时我们可以添加一些搜索条件来减少它的查询空间，提高查询效率。 (责任编辑：qin) |