解決隨機最大二分匹配問題

Question

我已經面臨以下問題：

• 有兩個不相交的集合，A和B
• 對於每對元件（a，b）（a屬於集合A ，其中b屬於集合B），那麼有可能提前知道pij。它表示a與b匹配的概率（確定性水平），換句話說，a與b匹配得多近（反之亦然，因爲pij == pji）。
• 我必須找到具有最高概率/確定性的匹配，並找出對（a，b），其描述了匹配
• 每一個元素都必須匹配/與另一個配對從另一組一次（像在標準二分匹配問題）
• 如果可能的話，我想計算一個數值近似地表達了對獲得匹配的不確定性水平（比方說，0代表隨機猜測，1表示肯定）

一個簡單實用描述需要這種算法的例子牀下面（這個其實不是我解決這個問題！）：

• 兩個人被要求寫字母 一個 - 在一張紙上
• z對每對字母（a，b）我們運行模式匹配器以確定人寫的aA代表字母b由人寫的B的概率。這給了我們 概率矩陣表達某種相似性相關 的每對字母（a，b）
• 每個字母的那個人A寫道， 我們需要找到相應的 信人B
寫

現行辦法： 我想知道如果我能分配權重成比例的確定性水平/概率元素a從集對數與來自集合B的元素b匹配，然後運行最大加權二分配匹配以找到最大總和。對數是因爲我想最大化多重匹配的總概率，並且由於單個匹配（表示爲匹配元素對a-b）形成事件鏈，其是概率的乘積，通過取對數，我們將其轉換成到概率之和，然後使用匈牙利算法等加權二分匹配算法容易地將其最大化。但我懷疑這種方法會確保統計預期最大值的最佳匹配。

經過搜索，我發現最接近的問題是一個兩階段隨機最大加權匹配問題，它是NP難題，但實際上我需要某種「一階段」隨機最大加權匹配問題。

Answer 1

我不知道是否可以使用MaxFlow/MinCut。無論如何，我目前無法證明這是最佳選擇，但是您的問題可能是NP難度。通過創建連接到A中所有節點的權重爲1並且接收器連接到B中的所有節點的源，您可以使用MF/MC找到完美匹配，如果有雙向圖，V =（A，B）重量1.我提議你讓邊緣從橫到B的權重是你上述概率。你怎麼看？