本文提出了一种基于约束的部分枚举空间关系图匹配策略.该策略通过使用在匹配过程中动态生成的2类匹配约束条件智能预测当前匹配状态的后继有效的枚举状态以跳过无效的中间匹配状态,达到状态空间剪枝的目的,可以有效降低空间关系图匹配过程中状态搜索空间.根据理论分析,该策略在最好情况下的时间复杂度为O(n2),在几乎很少发生的最坏情况下时间复杂度为O(n!);其空间复杂度都是O(n).所提出的方法已在笔者研发的手绘草图识别系统Smart Sketchpad中取得了很好的识别效果.%A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.
展开▼
机译：本文提出了一种基于约束的部分枚举空间关系图匹配策略.该策略通过使用在匹配过程中动态生成的2类匹配约束条件智能预测当前匹配状态的后继有效的枚举状态以跳过无效的中间匹配状态,达到状态空间剪枝的目的,可以有效降低空间关系图匹配过程中状态搜索空间.根据理论分析,该策略在最好情况下的时间复杂度为O(n2),在几乎很少发生的最坏情况下时间复杂度为O(n!);其空间复杂度都是O(n).所提出的方法已在笔者研发的手绘草图识别系统Smart Sketchpad中取得了很好的识别效果.%A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.
展开▼
