二次赋值(method=‘2opt’)¶
- scipy.optimize.quadratic_assignment(A, B, method='2opt', options={'maximize': False, 'rng': None, 'partial_match': None, 'partial_guess': None})
(近似)解二次指派问题。
此函数使用2-opt算法解决二次分配问题(QAP)和图匹配问题(GMP [1].
二次赋值解决以下形式的问题：
\[\begin{split}\min_P&\{\\text{trace}(A^T P B P^T)}\\ \mbox{s.t.}&{P\\ε\\Mathcal{P}}\\\end{split}\]哪里 \(\mathcal{{P}}\) 是所有置换矩阵的集合，并且 \(A\) 和 \(B\) 是方阵。
图形匹配尝试 最大化 同样的目标函数。该算法可以被认为是寻找两个图的节点的排列，以最小化诱导边不一致的数量，或者在加权图的情况下，最小化边权重差的平方和。
请注意，二次指派问题是NP难的。这里给出的结果是近似值，不能保证是最优的。
- 参数
- A二维阵列，正方形
方阵 \(A\) 在上面的目标函数中。
- B二维阵列，正方形
方阵 \(B\) 在上面的目标函数中。
- method字符串输入{‘FAQ’，‘2opt’}(默认值：‘FAQ’)
用于解决问题的算法。这是“2opt”的方法特定文档。 'faq' 也是可用的。
- 退货
- resOptimizeResult
OptimizeResult 包含以下字段。
- col_ind一维阵列
的节点中找到的最佳排列对应的列索引 B 。
- 有趣的浮动
解决方案的客观价值。
- NIT集成
优化期间执行的迭代次数。
参见
有关参数睡觉的文档，请参阅
scipy.optimize.quadratic_assignment- 选项
- maximize布尔值(默认值：FALSE)
如果满足以下条件，则最大化目标函数
True。- rng ：{无，整型，
numpy.random.Generator，{无，整型， 如果 seed 为无(或 np.random )、
numpy.random.RandomState使用的是Singleton。如果 seed 是一个整型、一个新的RandomState实例，其种子设定为 seed 。如果 seed 已经是一个Generator或RandomState实例，则使用该实例。- partial_match整数的二维数组，可选(默认值：无)
修复了部分匹配。也被称为“种子” [2].
每行 partial_match 指定一对匹配的节点：节点
partial_match[i, 0]的 A 与节点匹配partial_match[i, 1]的 B 。阵列具有形状(m, 2)，在哪里m不大于节点数， \(n\) 。- partial_guess整数的二维数组，可选(默认值：无)
关于两个矩阵之间匹配的一个猜想。不像 partial_match ， partial_guess 不修复索引；它们仍然可以自由优化。
每行 partial_guess 指定一对匹配的节点：节点
partial_guess[i, 0]的 A 与节点匹配partial_guess[i, 1]的 B 。阵列具有形状(m, 2)，在哪里m不大于节点数， \(n\) 。
注意事项
这是一种贪婪的算法，其工作原理类似于泡沫排序：从初始排列开始，迭代地交换索引对以改进目标函数，直到无法进行此类改进。
参考文献
- 1
“2-OPT，”维基百科。https://en.wikipedia.org/wiki/2-opt
- 2
D.菲什金德，S.Adali，H.Patsolic，L.Meng，D.Singh，V.Lyzinski，C.Priebe，“种子图匹配”，模式识别.87(2019年)：203215，https://doi.org/10.1016/j.patcog.2018.09.014