如何理解scipy.optimize.quadratic_assignment函数的输出及异常结果？

核心原因：最优解不唯一 #

当你输入A=B时，恒等排列[0,1,2,3,4]确实是二次分配问题的一个最优解，但并非唯一的最优解。scipy的quadratic_assignment函数会返回算法找到的任意一个最优解，而非固定返回恒等排列。

为什么会存在多个最优解？ #

二次分配问题的默认目标是最大化trace(A^T P B P^T)，当A=B时等价于最大化trace(A^T P A P^T)。如果存在排列P，使得P A P^T与A的乘积迹值和恒等排列的结果一致，那么P就是最优解。这种情况常见于：

• 矩阵A存在结构对称性（比如两个节点的连接模式完全相同，交换它们不改变目标函数值）；
• 矩阵A中有重复的行/列结构（比如多个全零行，交换它们不影响计算结果）；
• 随机生成的稀疏矩阵恰好存在等价的节点排列。

验证最优性 #

你可以通过对比目标函数值来确认返回的排列是否为最优解：

import numpy as np
from scipy.optimize import quadratic_assignment

n = 5
p = np.log(n)/n
A = np.random.rand(n,n)<p

res = quadratic_assignment(A, A)

# 计算恒等排列的目标函数值
identity_P = np.eye(n)
identity_fun = np.trace(A.T @ identity_P @ A @ identity_P.T)

print("恒等排列目标值:", identity_fun)
print("返回排列的目标值:", res.fun)
print("是否为最优解:", np.isclose(identity_fun, res.fun))

如果输出是否为最优解为True，说明返回的排列确实是最优解。

进一步验证：暴力枚举（仅适用于小n） #

对于n≤8的情况，可以用暴力枚举法查看所有可能的最优解：

res_brute = quadratic_assignment(A, A, method='brute')
print("暴力枚举得到的最优排列:", res_brute.col_ind)

你会发现可能存在多个排列都能达到相同的最优目标值。

内容的提问来源于stack exchange，提问作者LowPolyCorgi