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 困难问题。此处提供的结果是近似值，无法保证是最佳值。

参数:

A2-D 数组，方阵

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

B2-D 数组，方阵

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

method字符串，取值为 {‘faq’, ‘2opt’}（默认值：‘faq’）

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

返回:

resOptimizeResult

OptimizeResult，包含以下字段。

col_ind1-D 数组

与发现的 B 节点的最佳排列对应的列索引。

fun浮点数

解决方案的目标值。

nit整数

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

另请参阅

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

选项:

——-

maximize布尔值（默认值：False）

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

rng{None、整数、numpy.random.Generator,

numpy.random.RandomState 为可选参数}

如果 seed 为 None（或 np.random），则使用 numpy.random.RandomState 单例。如果 seed 为整数，则使用 RandomState 实例，用 seed 填充。如果 seed 已是 Generator 或 RandomState 实例，则使用该实例。

partial_match整数的二维数组，为可选参数（默认值：None）

修复部分匹配项。也称为“种子” [2]。

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

注意

partial_match 必须按第一列排序。

partial_guess2-D 整数数组，可选（默认值：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”，维基百科。 https://en.wikipedia.org/wiki/2-opt

[2]

D. Fishkind、S. Adali、H. Patsolic、L. Meng、D. Singh、V. Lyzinski、C. Priebe，“种子图匹配”，Pattern Recognit。 87 (2019): 203-215，https://doi.org/10.1016/j.patcog.2018.09.014