quadratic_assignment(method='2opt')

scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)

（近似地）解决二次分配问题。

此函数使用 2-opt 算法 [1] 解决二次分配问题 (QAP) 和图匹配问题 (GMP)。

二次分配解决以下形式的问题

\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]

其中 \(\mathcal{P}\) 是所有置换矩阵的集合，\(A\) 和 \(B\) 是方阵。

图匹配尝试最大化相同的目标函数。此算法可以被认为是寻找两个图的节点对齐方式，该对齐方式最小化了诱导边不一致的数量，或者在加权图的情况下，最小化了平方边权重差异的总和。

请注意，二次分配问题是 NP-hard 问题。此处给出的结果是近似值，不能保证是最优的。

参数:

A二维数组，方阵

目标函数中的方阵 \(A\)。

B二维数组，方阵

目标函数中的方阵 \(B\)。

methodstr，取值范围为 {‘faq’, ‘2opt’} (默认: ‘faq’)

用于解决问题的算法。这是 ‘2opt’ 的特定于方法的文档。 ‘faq’ 也可用。

返回:

resOptimizeResult

OptimizeResult，其中包含以下字段。

col_ind一维数组

与找到的 B 的节点最佳置换相对应的列索引。

fun浮点数

解的目标值。

nit整数

优化期间执行的迭代次数。

另请参阅

有关其余参数的文档，请参阅 scipy.optimize.quadratic_assignment

选项:

——-

maximize布尔值 (默认: False)

如果为 True，则最大化目标函数。

rng{None, int, numpy.random.Generator}, 可选

伪随机数生成器状态。 有关详细信息，请参阅 quadratic_assignment。

partial_match二维整数数组，可选 (默认: None)

固定部分匹配。 也称为“种子” [2]。

partial_match 的每一行指定一对匹配的节点：A 的节点 partial_match[i, 0] 与 B 的节点 partial_match[i, 1] 匹配。 该数组的形状为 (m, 2)，其中 m 不大于节点数 \(n\)。

注意

partial_match 必须按第一列排序。

partial_guess二维整数数组，可选 (默认: None)

关于两个矩阵之间匹配的猜测。与 partial_match 不同，partial_guess 不固定索引；它们仍然可以自由优化。

partial_guess 的每一行指定一对匹配的节点：A 的节点 partial_guess[i, 0] 与 B 的节点 partial_guess[i, 1] 匹配。该数组的形状为 (m, 2)，其中 m 不大于节点数 \(n\)。

注意

partial_guess 必须按第一列排序。

备注

这是一种贪婪算法，其工作方式类似于冒泡排序：从初始置换开始，它迭代地交换索引对以改进目标函数，直到不可能进行此类改进为止。

参考文献

[1]

“2-opt,” Wikipedia. https://en.wikipedia.org/wiki/2-opt

[2]

D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, https://doi.org/10.1016/j.patcog.2018.09.014