基于表象式语义网络的图匹配算法

摘要

提出了一种在表象式语义网络中的查找方法,表象式语义网络问题的求解一般都是通过图匹配实现的,首先根据待求解的问题的要求构造一个带变量节点的语义网络,然后与计算机视觉系统中己存储的语义网络进行图匹配。当语义网络中的询问部分与系统中的语义网络图匹配后,则与询问部分匹配的事实就是问题的解。图匹配问题可以通过构造一个图的附属数据结构来完成,这个附属数据结构也称为相连图(association graph),对于两个图G=(V,A)以及G′=(V′,A′),构造相联图G″=(V″,A″),也就是说,V″是所有可能节点匹配对的集合,A″是所有相容节点匹配的集合。这相当于在相联图中寻求一个最大的基团(clique),其中基团定义为G″的完全连通的一个子图。最大基团满足其节点集合不是任何其他基团节点集的适当子集。