如何理解scipy的quadratic_assignment函数的输出？

Question

我正在尝试使用 scipy 的quadratic_assignment函数，但我无法理解输出如何描述最佳解决方案。这是一个最小的例子，我将一个小矩阵与其自身进行比较：

import numpy as np
from scipy.optimize import quadratic_assignment

# Parameters
n = 5
p = np.log(n)/n   # Approx. 32%

# Definitions
A = np.random.rand(n,n)<p

# Quadratic assignment
res = quadratic_assignment(A, A)

print(res.col_ind)

结果似乎是随机分配的：

[3 0 1 4 2]
[3 2 4 1 0]
[3 2 1 0 4]
[4 3 1 0 2]
[2 3 0 1 4]
...

但是，根据文档，col_ind应该是与 B 的节点找到的最佳排列相对应的列索引。由于输入矩阵相等（B==A），因此我希望身份分配[0 1 2 3 4]能够弹出。更改n为更大的值并没有帮助。

我有什么地方做错了吗？

Answer 1

该quadratic_assignment函数（大约）解决了两类问题：二次分配和图形匹配。它们在数学上非常相似：区别在于二次分配涉及最小化目标函数，而图形匹配涉及最大化同一函数。（参考：scipy 文档）。

\n

为了区分这两个问题，该函数接受一个选项（作为函数参数maximize中的键：值对传递）。options如果未提供，则默认为False（即解对应于函数的最小值，即二次分配问题而不是图匹配问题）。

\n

quadratic_assignment(A, B)  # solves quadratic assignment\nquadratic_assignment(A, B, options={\'maximize\': False})  # solves quadratic assignment\nquadratic_assignment(A, B, options={\'maximize\': True})  # solves graph matching\n

\n

现在，当你说“由于输入矩阵相等（B==A），因此我期望恒等分配 [0 1 2 3 4] 弹出” \xe2\x80\x93 这就是图匹配所期望的，即恒等分配确实是 B 的排列，它比任何其他匹配 A 都更好（或者严格地说：至少与任何其他匹配）。

\n

因此，您可以通过指定获得预期结果，options={\'maximize\': True}以便获得图形匹配问题的解决方案，而不是默认的二次分配：

\n

import numpy as np\nfrom scipy.optimize import quadratic_assignment\n\n# Parameters\nn = 5\np = np.log(n)/n   # Approx. 32%\n\n# Definitions\nA = np.random.rand(n,n)<p\n\n# Graph matching\nres = quadratic_assignment(A, A, options={\'maximize\': True})\n\nprint(res.col_ind)\n

\n

当我运行这个程序时，[0 1 2 3 4]大约 97% 的时间我都能得到预期的结果。这不是 100%，因为 (a) 该算法是近似的，并且“不能保证是最优的”（根据文档），以及 (b) 您构造的方式A可能会创建退化情况，其中存在多个同样好的解决方案。

\n