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

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

Algorithm of graph matching based on mental imagery semantic nets

A new method for searching mental imagery in semantic nets is proposed.The problems of semantic nets of mental imagery are generally solved by graph matching.First a semantic net with variable nodes is constructed in accordance with the requirements of the problem to be solved.Then the graph matching algorithm is employed to match the already existed semantic nets of computer vision system.The enquiry part of the sub-semantic network is the solution if it matches the semantic network graph successfully.The problem of map matching can be resolved by the construction of a data structure of associate graph.For two graphs,G=(V,A) and G′=(V′,A′),we can construct an associate graph G″= (V″,A″),in which V″is of all possible matching set nodes,and A″is of all compatible matching set nodes.It is equivalent to find a maximum clique in the associate graphs, clique is defined as a completely connected sub-graph of Equates G″.The largest clique meets the criterion that its node sets are not of approximate subsets of any other clique.