基於匹配分數對來自不同列表的值進行1-1匹配的算法

Question

我有兩個列表，listA和listB，可能具有不同的長度。我想匹配listA中的對象與listB中的對象，以獲得最佳匹配。

我有一個算法，可以給任何一對對象的匹配分數。我需要的是一個有效的（並且相當容易閱讀）算法，以獲得最高得分匹配1-1。在listA中每個對象只有一個精確的匹配，但是可能有與具有相同分數的同一對象匹配，並且在那種情況下匹配哪個並不重要。由於匹配得分不夠高，是否在最後一個或兩個列表中留下了一些對象也沒關係。

我提出的算法可能有一些缺陷，我沒有發現，並且可能有一個標準的方法來做到這一點，我一直沒有找到，所以我正在尋找建議/校正。

這裏是我的嘗試：

for (a in listA) 
    for (b in listB) 
     if (!b.hasPerfectMatch) 
      var score = calculateMatchScore(a,b) 
      if (score > b.score) //better match than any previous 
       remove any previous match to b 
       add previous match a to end of listA 
       b.score = score 
       if (b.hasPerfectMatch) 
        break //found exact match for this a 

（我將使用Java的方式）

Answer 1

你描述一個稱爲最大權重二分匹配經典的問題，已經有各地的許多優秀算法解決它。我建議讀一讀匈牙利語算法作爲出發點，因爲它簡單，快速，並且保證已知它能產生最佳答案。

希望這會有所幫助！