圖論在計算廣告中的應用

01-27

背景是這樣的，我們是一家初創 DSP 公司，然後在接入騰訊 Ad Exchange 的時候，騰訊拋給我們了這麼一個限制：一次廣告請求中可能含有多個廣告位，但我們不能拿相同廣告主的廣告進行重複競價。舉個例子來說，假如一次請求中含有 A、B、C 三個廣告位，我們手頭有 a、b、c、d 四個廣告主的廣告可供參與競價，假使我們拿廣告主 a 的廣告去參與廣告位 A 的競價，那就不能拿 a 去參與 B 和 C 的競價了。

好了，那作為公司的商業智能，我們要面對的問題就是，在這個約束下，如何使我們投放廣告的利潤最大化？這篇專欄文章即是這個問題的最優解決方案。

如果我們不考慮這個約束，那麼我們可以利用最簡單的公式來求得期望：

$eCPM = pCTR times CPC$

其中 CPC 是由廣告主在後台設定的，pCTR 是由統計模型預測的點擊率，那麼 eCPM 即為本次投放的期望價值，不熟悉計算廣告名詞的可以自行百度一下。如果以傳統策略來說，對於每一個廣告位，我們都是返回 eCPM 最高的那個廣告進行競價，輔以平滑預算模型即可最大化我們和廣告主的利潤。但如果增加了上述約束的話，就沒那麼簡單了，假如a、b、c、d對A、B、C的 eCPM 如下（Slot是廣告位，Ad是廣告，值就表示價值）：

如果我們用暴力的方法來解決的話，那麼我們需要進行 $A_{4}^{3}$ 次選擇，可見計算複雜度是階乘級別的，隨著廣告主或者廣告位數量的增加，要求100ms內響應請求就變得不那麼實際。

那如果我們仍以之前貪心的策略來呢？這樣我們可能會選取到如下結果：

即從廣告位A開始挑最大的，再B，再C，那麼價值和為12。但實際上，我們可以獲取更大價值：

在這種選取方式下，價值和為14。如果運氣好，我們以C->B->A的方式來做貪心，還是可以找到最優解的。那麼我們可以從任一一個廣告位出發，枚舉完所有路徑做一遍貪心策略，複雜度仍然是階乘級別的（Slot全排列個數 * Ad個數）。

如果你有圖論基礎的話，這個表格應該一眼就能看出來，其本質上是一個鄰接矩陣，那我們就可以把它給畫出來，邊上是有權值的，表示的就是廣告位和廣告主之間的價值：

畫得比較粗糙，手工PS繪製，紅色描邊的就是我們要的最優解。搞過 ACM 競賽或者熟悉圖論的同學應該一眼就能看出這是一個「二分圖」了，並且我們的目標是二分圖的最大權值匹配。

--------------------------------

在聊最大權值匹配之前，我們要先認識什麼是「二分圖匹配」，以及如何去做權值相等的最大二分匹配，在這之後我們才能更深入理解這個問題，去解決帶權值的最大匹配問題。

二分圖：簡單來說，如果圖中點可以被分為兩組，並且使得所有邊都跨越組的邊界，則這就是一個二分圖。準確地說：把一個圖的頂點劃分為兩個不相交集 U 和 V ，使得每一條邊都分別連接 U 、 V 中的頂點。如果存在這樣的劃分，則此圖為一個二分圖。二分圖的一個等價定義是：不含有「含奇數條邊的環」的圖。
最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。

完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那麼它就是一個完美匹配。圖 4 是一個完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個點都已經匹配，添加一條新的匹配邊一定會與已有的匹配邊衝突）。但並非每個圖都存在完美匹配。

舉一個更簡單的例子，下圖中的邊表示男生和女生彼此喜歡，問最多能有多少配對？這就是一個經典的求無權二分圖最大匹配問題。

這時候，有一個來自匈牙利的數學家 Edmonds 跳出來了說他可以解決這個問題，所以就有了一個「匈牙利演算法」（為什麼不叫 Edmonds 演算法？），這個演算法的核心是不斷去尋找增廣路徑，在介紹這個演算法前，還有兩個概念需要知道：

交替路：從一個未匹配點出發，依次經過非匹配邊、匹配邊、非匹配邊…… 形成的路徑叫交替路。
增廣路：從一個未匹配點出發，走交替路，如果途徑另一個未匹配點（出發的點不算），則這條交替路稱為增廣路（augmenting path）。

以上圖為例，我們可以找到這麼一條增廣路，其中 1->6 和 4->8 是已匹配的邊：

那麼「匈牙利演算法」其實就很簡單了，就是不斷找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時，達到最大匹配（增廣路定理）。

所以我們可以簡潔地用 DFS 或者 BFS 來實現這個過程，代碼就不貼了，如果有興趣夯實這一基礎，可以移步：程序員必須掌握哪些演算法？ - SimonS 的回答尋找 OJ 上對應的題。

--------------------------------

接下來我們就要面對本次的大BOSS了，即解決帶權值的最大二分圖匹配。這裡要亮相的人物是 Kuhn-Munkres，他在「匈牙利演算法」的基礎上發明了「 KM 演算法」，高效解決了帶權值的問題，但是！為什麼他就能以自己名字命名演算法了……（黑人問號）

接下來的演算法過程描述可能會比較複雜，我會儘可能用簡單的語言來講。想當年搞OI的時候聽高三NOI保送的金牌大牛給我們上這個課，我剛聽完的時候也是一臉懵逼。

「KM 演算法」中引入了一個「頂標」的概念，其實就是給每個頂點加了一個標記位。我們設頂點 $X_{i}$ 的標記為 $A_{i}$ ，設頂點 $Y_{i}$ 的標記為 $B_{i}$ ，頂點 $X_{i}$ 和 $Y_{j}$ 之間的邊權為 $W_{ij}$ ，很顯然，對於任何邊 $(i,j)$ ，總有 $A_{i} + B_{j} geq W_{ij}$ 。這裡還有兩個較為隱晦的概念：

相等子圖：設 $G(V,E)$ 為二部圖， $G(V,E)$ 為二部圖的子圖。如果對於 $G$ 中的任何邊 $(i,j)$ 滿足 $L(x)+L(y)=W_{xy}$ ，我們稱 $G(V,E)$ 為 $G(V,E)$ 的等價子圖或相等子圖（是 G 的生成子圖）。
完備匹配：設 $G(V_{1},V_{2}, E)$ 為二部圖， $|V_{1}|leq |V_{2}|$ ， $M$ 為 $G$ 中一個最大匹配，且 $|M|=|V_{1}|$ ，則稱 $M$ 為 $V_{1}$ 到 $V_{2}$ 的完備匹配。

如果你第一次可以無壓力看懂上述兩個概念，那說明你天賦比我高，我至少來回讀了三四遍。最後，祭出「KM演算法」的核心定理：

若二分圖中的相等子圖有完備匹配，那麼這個完備匹配就是二分圖的最大權匹配。

證明放到後面再講，我們先理解了以上幾個概念之後，「KM演算法」按以下步驟執行，即可找到最大權匹配：

初始化採用貪心策略，設 $A_{i}$ 為與 $X_{i}$ 相連的最大邊權， $B_{i}$ 為 0；
利用「匈牙利演算法」找到一個完備匹配 $M$ ；
如果 $M$ 不存在，則修改頂標值，增加一些邊；
重複第二步和第三步，直到找到完備匹配即為最大權匹配。

第三步展開來是這樣的，從第一個節點開始掃描，如果有合法的增廣路，那麼將其反選，擴充路徑；如果該節點沒有合法的增廣路，那麼則將增廣路上的所有 $A$ 上的點加入點集 $S$ ，將 $B$ 上的所有點加入點集 $T$ ，從 $S$ 和不在 $T$ 集合中的點裡面，通過以下公式得到一個 $delta$ ：