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 節點的最佳排列的行索引。

funfloat

解決方案的目標值。

nitint

最佳化期間執行的迭代次數。

另請參閱

有關其餘參數的文件，請參閱 scipy.optimize.quadratic_assignment

選項:

——-

maximizebool (預設值: 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，”維基百科。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