赋权图匹配的双向松弛障碍规划模型

"郑开杰、高玉涛和彭济根在《自动化学报》2010年第36卷第8期上发表的文章‘赋权图匹配问题的一种新的松弛模型’探讨了图匹配问题的新解决方案。他们提出了一种基于置换矩阵的双向松弛障碍规划模型，用于解决赋权图匹配问题，即Weighted Graph Matching (WGM)问题。" 文章指出，图匹配问题属于NP难问题，即在计算复杂性理论中，这类问题没有已知的多项式时间解法。传统的图匹配方法通常通过松弛方法来寻找近似解，但作者在此基础上提出了一个创新的模型。这个新模型利用置换矩阵是非负正交矩阵的特性，构建了一个双向松弛障碍规划，它的解与原始图匹配问题的解是等价的。 新模型被定义为一个二元连续规划，同时具备两个重要性质：一是它是一个在正交矩阵上的线性优化问题，二是它是一个在非负矩阵上的凸二次优化问题。这样的双重特性使得该模型在理论和实际应用中都有其独特优势。为了求解这个新模型，作者设计了一个交替迭代算法，并且证明了该算法具有局部收敛性，即在一定条件下，算法会逐步接近最优解。 实证分析部分，通过数值实验展示了新方法在匹配精度上优于传统的线性规划方法和特征值分解方法。这表明，新提出的松弛模型不仅在理论上具有严谨性，而且在实践中也具有较高的匹配效果，为图匹配问题提供了一个更有效的求解途径。 关键词：图匹配，松弛方法，置换矩阵，NP难问题。文章的DOI为10.3724/SP.J.1004.2010.01200，为后续研究者提供了参考文献标识。 这篇文章为解决图匹配这一复杂问题提供了新的理论基础和实用算法，对图论、计算机科学以及相关领域的研究有着重要的贡献。