面向模型局部搜索的最短路径集最优匹配方法

Model local search oriented optimal matching method for shortest paths set

为实现边界表示模型的局部搜索,提出一种将模型属性图局部结构比较问题转化为属性图最短路径集最优匹配问题的方法。为获得属性图的最短路径集,给出一种可以生成两两节点间所有最短路径的算法;为实现查询模型与备选模型对应的最短路径集之间的最优匹配,将离散粒子群优化算法引入模型搜索领域,提出面向最短路径集最优匹配的算法,定义了相应的基本运算规则、适应度函数、终止条件和算法步骤。模型搜索实验结果表明,所提算法可以解决如何获取模型局部结构对应关系和计算局部结构间距离的问题,从而有效地支持模型的局部搜索。

To realize local search of Boundary Representation（B-Rep） model, a method converted attribute graph local structure comparison into attribute graph shortest paths set optimal matching was proposed. To obtain shortest paths set of the attribute graph, an algorithm named All Shortest Paths generation based on Floyd--Warshall （ASP Floyd-Warshall） was presented. For realize optimal matching of shortest paths set between query models and candidate models, an Discrete Particle Swarm Optimization for Shortest Paths Optimal Matching （DPSO-SPOM） was given, which included definition of corresponding basic operation rules, fitness function, termination conditions and algorithm steps. The experimental results demonstrate that ASP Floyd-Warshall algorithm and DPSO-SPOM algorithm could solve problems that how to obtain the local structure correspondence between models and how to calcu late distance between local structures, thus supported the local search of models effectively.