研究工作也許是我們訓練中最有趣的部分。 我們的想法是在大學期間嘗試自己選擇的方向。 例如，軟體工程和機器學習領域的學生經常去公司（主要是 JetBrains 或 Yandex，但不僅限於）進行研究。
在這篇文章中，我將討論我的電腦科學專案。 作為我工作的一部分，我研究並付諸實踐了解決最著名的 NP 難題之一的方法： 頂點覆蓋問題.
如今，一種解決 NP 難題的有趣方法正在快速發展——參數化演算法。 我將盡力讓您加快速度，告訴您一些簡單的參數化演算法，並描述一種對我幫助很大的強大方法。 我在PACE挑戰賽上展示了我的結果：根據公開測試的結果，我的解決方案獲得了第三名，最終結果將於1月XNUMX日揭曉。
關於我
我叫瓦西里‧阿爾費羅夫，現在即將在聖彼得堡國立研究大學高等經濟學院讀完三年級。 我從學生時代起就對演算法感興趣，當時我在莫斯科第 179 學校學習並成功參加了電腦科學奧林匹克競賽。
有限數量的參數化演算法專家進入酒吧...
例取自書本
想像一下，您是個小鎮的酒吧保全。 每週五，半個城市的人都會來到你的酒吧放鬆，這給你帶來了很多麻煩：你需要把吵鬧的顧客趕出酒吧，以防止打架。 最終，您厭倦了並決定採取預防措施。
由於您的城市很小，您可以準確地知道哪對顧客在酒吧在一起時可能會打架。 你有一份清單嗎 n 今晚會來酒吧的人。 您決定將一些鎮民拒之門外，以免引起任何人打架。 同時，你的老闆不想損失利潤，如果你不讓超過 k 人。
不幸的是，你面前的問題是一個經典的 NP 難題。 你可能知道她是 ，或作為頂點覆蓋問題。 對於此類問題，一般情況下，沒有演算法可以在可接受的時間內工作。 準確地說，未經證實且相當強的假設ETH（指數時間假說）說這個問題無法及時解決 ，也就是說，你想不出還有什麼比完整搜尋更好的了。 例如，假設有人要來你的酒吧 N = 1000時 人類。 那麼完整的搜尋將是 大約有選項 - 瘋狂的數量。 幸運的是，你的管理階層給了你一個限制 k = 10，因此需要迭代的組合數量要少得多：十個元素的子集數量為 。 這樣雖然好一些，但即使在強大的集群上，也不是一日之數。
為了消除酒吧訪客之間關係緊張的情況下打架的可能性，您需要將鮑勃、丹尼爾和費多拒之門外。 不存在只留下兩個人的解決方案。
這是否意味著是時候讓步並讓所有人參與了？ 讓我們考慮其他選擇。 嗯，例如，你不能只讓那些可能與很多人打架的人進來。 如果有人至少可以與 k+1 另一個人，那你絕對不能讓他進來──否則你就得把所有人都拒之門外 k+1 鎮民，他可以跟他們打架，這肯定會讓領導者不高興。
讓你按照這個原則，把能丟的人都丟掉。 然後其他人都可以戰鬥 k 人們。 把他們扔出去 k 夥計，你能阻止的無非就是 衝突。 這意味著如果有超過 如果一個人至少捲入了一場衝突，那麼你當然無法阻止所有衝突。 當然，因為您肯定會讓完全不衝突的人進來，所以您需要檢查 XNUMX 人中 XNUMX 人的所有子集。 大約有 ，而這個數量的操作已經可以在集群上整理出來了。
如果你可以安全地帶走根本沒有衝突的人，那麼那些只參與一次衝突的人呢？ 事實上，他們也可以透過關上對手的大門來讓他們進來。 事實上，如果愛麗絲只與鮑伯發生衝突，那麼如果我們把愛麗絲排除在他們兩人之外，我們就不會輸：鮑伯可能有其他衝突，但愛麗絲肯定沒有這些衝突。 而且，不讓我們兩個進去也沒有意義。 進行此類操作後，不再有任何剩餘 命運未卜的客人：我們只有 衝突，每個衝突都有兩個參與者，每個衝突至少涉及兩個人。 所以剩下的就是整理 選項，這可以很容易地在筆記型電腦上考慮半天。
事實上，透過簡單的推理，您可以實現更有吸引力的條件。 請注意，我們肯定需要解決所有爭議，即從每一對衝突的人中，選擇至少一個我們不會讓其進入的人。 讓我們考慮以下演算法：採取任何衝突，我們從中刪除一個參與者並從其餘參與者遞歸地開始，然後刪除另一個參與者並同樣遞歸地開始。 由於我們每一步都將某人扔出去，因此這種演算法的遞歸樹是深度二叉樹 k，所以總的來說，演算法的工作原理是 哪裡 n 是頂點的數量，並且 m - 肋骨數量。 在我們的例子中，大約是一千萬，不僅在筆記型電腦上，甚至在手機上也可以瞬間計算出來。
上面的例子就是一個例子 參數化演算法。 參數化演算法是及時運行的演算法 f(k) 聚(n)哪裡 p - 多項式， f 是任意可計算函數，且 k - 一些參數，很可能比問題的規模小得多。
這個演算法之前的所有推理都給了例子 內核化 是創建參數化演算法的通用技術之一。 核化是將問題規模減小到受參數函數限制的值。 由此產生的問題通常稱為核心。 因此，透過對頂點度數的簡單推理，我們獲得了頂點覆蓋問題的二次核，並透過答案的大小進行參數化。 您也可以為此任務選擇其他設定（例如 LP 上方的頂點覆蓋），但這是我們將討論的設定。
步伐挑戰
競爭 （參數化演算法和計算實驗挑戰賽）誕生於 2015 年，旨在在參數化演算法和實際用於解決計算問題的方法之間建立聯繫。 前三場比賽致力於尋找圖的樹寬度（），尋找史坦納樹（）並蒐索一組割環的頂點（）。 今年，您可以嘗試解決的問題之一是上述頂點覆蓋問題。
這項比賽每年都越來越受歡迎。 如果你相信初步數據的話，今年就有 24 支隊伍參加了僅解決頂點覆蓋問題的比賽。 值得注意的是，比賽持續的時間不是幾個小時甚至一周，而是幾個月。 團隊有機會研究文獻，提出自己的原創想法並嘗試實施。 從本質上講，本次競賽是一個研究項目。 最有效的解決方案的想法和獲獎者的頒獎將與會議同時舉行 （參數化和精確計算國際研討會）作為歐洲最大的年度演算法會議的一部分 。 有關比賽本身的更多詳細信息，請訪問 ，往年的結果是 .
解決方案圖
為了解決頂點覆蓋問題，我嘗試使用參數化演算法。 它們通常由兩部分組成：簡化規則（理想情況下會導致內核化）和分割規則。 簡化規則是在多項式時間內對輸入進行預處理。 應用此類規則的目的是將問題簡化為等效的較小的問題。 簡化規則是演算法中最昂貴的部分，應用這部分會導致總運行時間 而不是簡單的多項式時間。 在我們的例子中，分割規則是基於以下事實：對於每個頂點，您需要將其或其鄰居作為答案。
一般方案是這樣的：我們應用簡化規則，然後選擇一些頂點，並進行兩次遞歸呼叫：在第一個中，我們將其作為回應，在另一個中，我們將其所有鄰居作為回應。 這就是我們所說的沿著該頂點的分裂（分支）。
下一段將對該方案添加一個補充。
拆分（早午餐）規則的想法
讓我們討論如何選擇發生分裂的頂點。
從演算法的角度來看，其主要思想是非常貪婪的：讓我們取一個最大度數的頂點並沿著它進行分割。 為什麼看起來更好？ 因為在遞歸呼叫的第二個分支中我們會透過這種方式刪除很多頂點。 您可以指望剩下一個小圖表，我們可以快速處理它。
這種方法結合已經討論過的簡單內核化技術，很好地展示了自己，並解決了數千個頂點大小的一些測試。 但是，例如，它不適用於三次圖（即每個頂點的度數為三的圖）。
還有另一個基於相當簡單的想法的想法：如果圖是斷開的，則其連接組件上的問題可以獨立解決，並在最後結合答案。 順便說一句，這是該方案中承諾的一個小修改，這將顯著加快解決速度：以前，在這種情況下，我們致力於計算組件響應的時間乘積，但現在我們致力於總和。 為了加速分支，您需要將連通圖變成斷開圖。
怎麼做？ 如果圖表中有一個連結點，你就需要努力去爭取它。 鉸接點是一個頂點，當刪除時，圖形將失去其連接性。 可以使用經典演算法在線性時間內找到圖中的所有連接點。 這種方法顯著加快了分支速度。
當刪除任何選取的頂點時，圖形將分成連接的組件。
我們會這樣做，但我們想要更多。 例如，在圖中尋找小的頂點切割並沿其頂點進行分割。 據我所知，找到最小全域頂點切割的最有效方法是使用 Gomori-Hu 樹，它是在立方時間內建造的。 在 PACE 挑戰賽中，典型的圖大小為數千個頂點。 在這種情況下，需要在遞歸樹的每個頂點執行數十億次操作。 事實證明，在規定的時間內解決問題根本不可能。
讓我們嘗試優化解決方案。 任何構造最大流的演算法都可以找到一對頂點之間的最小頂點割。 你可以讓它進入這樣的網絡 ，實際上它的工作速度非常快。 我懷疑理論上可以證明對運行時間的估計 ，這已經是可以接受的了。
我多次嘗試尋找隨機頂點對之間的切割，並採取最平衡的一個。 不幸的是，這在開放 PACE 挑戰測試中產生了糟糕的結果。 我將其與最大程度分割頂點的演算法進行了比較，並在下降深度限制的情況下運行它們。 試圖以這種方式找到切點的演算法留下了更大的圖。 這是因為切割結果非常不平衡：刪除了 5-10 個頂點後，只能分割 15-20 個頂點。
值得注意的是，有關理論上最快演算法的文章使用更先進的技術來選擇分裂頂點。 此類技術的實現非常複雜，在時間和記憶體方面的表現通常很差。 我無法確定哪些是可以接受的實踐。
如何應用簡化規則
我們已經有了內核化的想法。 讓我提醒您：
- 如果存在孤立頂點，請將其刪除。
- 如果存在度數為 1 的頂點，則將其刪除並取其鄰居作為回應。
- 如果至少有一個度數的頂點 k+1， 把它收回。
對於前兩個，一切都很清楚，對於第三個，有一個技巧。 如果在關於酒吧的漫畫問題中，我們給出的上限為 k，那麼在 PACE Challenge 中你只需要找到最小尺寸的頂點覆蓋。 這是搜尋問題到決策問題的典型轉變；通常兩類問題之間沒有區別。 在實踐中，如果我們為頂點覆蓋問題編寫求解器，可能會有所不同。 例如第三點。
從實施的角度來看，有兩種方法可以進行。 第一種方法稱為迭代深化。 如下：我們可以從下面對答案的一些合理約束開始，然後使用這個約束作為對上面答案的約束來運行我們的演算法，而遞歸不會低於這個約束。 如果我們找到了某個答案，那麼它肯定是最優的，否則我們可以將此限制增加一併重新開始。
另一種方法是儲存一些當前的最佳答案並尋找較小的答案，找到時更改此參數 k 以更好地切斷搜索中不必要的分支。
經過幾次夜間實驗後，我決定將這兩種方法結合起來：首先，我在搜尋深度上進行某種限制（選擇它，以便與主要解決方案相比花費的時間可以忽略不計）運行我的演算法，並使用最佳的找到的解決方案作為答案的上限 - 即同一件事 k.
2 次頂點
我們已經處理了 0 度和 1 度的頂點。 事實證明，這可以透過 2 度的頂點來完成，但這需要對圖中進行更複雜的操作。
為了解釋這一點，我們需要以某種方式指定頂點。 我們將度數為 2 的頂點稱為頂點 v，及其鄰居 - 頂點 x и y。 接下來我們會講兩個案例。
- 何時 x и y - 鄰居。 然後你就可以回答 x и y和 v 刪除。 確實，從這個三角形中至少需要取兩個頂點作為回報，如果我們取絕對不會輸 x и y：他們可能還有其他鄰居，並且 v 他們不在這裡。
- 何時 x и y - 不是鄰居。 然後指出所有三個頂點都可以黏合成一個。 這個想法是，在這種情況下，存在一個最佳答案，其中我們採取 v，或兩個頂點 x и y。 此外，在第一種情況下，我們將不得不採取所有鄰居的回應 x и y，但在第二個則沒有必要。 這恰好對應於我們不採用黏合頂點作為響應以及採用黏合頂點作為響應時的情況。 只需要注意，在這兩種情況下，此類操作的響應都會減少 XNUMX。
值得注意的是，這種方法很難在公平的線性時間內準確實現。 黏合頂點是一項複雜的操作；您需要複製鄰居清單。 如果您不小心這樣做，您可能會得到漸近次優的運行時間（例如，如果您在每次粘合後複製大量邊）。 我決定從 2 度頂點找到整個路徑，並分析一堆特殊情況，例如來自此類頂點或除一個頂點之外的所有此類頂點的循環。
此外，該操作必須是可逆的，以便當從遞歸返回時我們將圖表恢復到其原始形式。 為了確保這一點，我沒有清除合併頂點的邊列表，所以我只知道哪些邊去哪裡。 這種圖的實現也需要準確性，但它提供了公平的線性時間。 而對於數萬條邊的圖，它可以放入處理器快取中，這在速度上有很大的優勢。
線性核
最後是核心中最有趣的部分。
首先，回想一下，在二部圖中，可以使用以下方法找到最小頂點覆蓋 。 為此，您需要使用演算法 為了找到那裡的最大匹配，然後使用定理 .
線性核的思想是這樣的：首先我們將圖分叉，即不是每個頂點 v 讓我們加入兩個峰值 и ，而不是每條邊 紫外線 讓我們加入兩根肋骨 и 。 產生的圖將是二分圖。 讓我們找到其中的最小頂點覆蓋。 原始圖的某些頂點會到達那裡兩次，有些只會到達一次，有些則永遠不會。 Nemhauser-Trotter 定理指出，在這種情況下，我們可以刪除未命中一次的頂點，並收回命中兩次的頂點。 此外，她說，對於剩餘的頂點（那些擊中一次的頂點），您需要至少取一半作為答案。
我們剛學會離開不超過 2k 尖峰事實上，如果餘數答案至少是所有頂點的一半，那麼頂點總數就不會多於 2k.
在這裡我能夠向前邁出一小步。 很明顯，以這種方式建構的核心取決於我們在二部圖中採用的最小頂點覆蓋類型。 我想取一個，以便剩餘頂點的數量最少。 以前，他們只能及時做到這一點 。 我當時想出了這個演算法的實現 ，因此，可以在每個分支階段的數十萬個頂點的圖中搜尋該核。
導致
實踐表明，我的解決方案在數百個頂點和數千個邊的測試中效果良好。 在這樣的測試中，很可能會在半小時內找到解決方案。 原則上，如果圖具有足夠多的高階頂點（例如，階數 10 及更高），則在可接受的時間內找到答案的機率會增加。
要參加比賽，必須將解決方案發送至 。 根據那裡提供的資訊判斷 ，我的解決方案在公開測試中在二十個中排名第三，與第二有很大差距。 說實話，目前還不完全清楚比賽本身如何評估解決方案：例如，我的解決方案通過的測試比第四名的解決方案要少，但在通過的測試中，它的運行速度更快。
封閉測試的結果將於 XNUMX 月 XNUMX 日公佈。
來源： www.habr.com