先貼上我們名次俄认，我們是上合賽區(qū)的【上江湖南西核笠溃】隊典尾。初賽38名糊探，復活賽8，然后就game over啦：
這次的賽題依舊涉及圖論相關的算法。去年是【未來網(wǎng)絡：尋路】瞪慧，今年是【大視頻時代：布局】弃酌。連續(xù)兩年都是圖論了，建議明年準備參加比賽的同學可以先把圖論給溫習了查蓉。
細分的話榜贴，這是一個CDN問題，或者叫做server placement/ facility location問題鬼佣，總之搜這幾個關鍵詞可以拿到很多有價值的論文及汉。建議明年準備參加比賽的同學，拿到賽題后先把問題模型搞清楚房铭，確定其在學術界的名稱缸匪，然后就可以去搜論文了类溢。看論文是一個非常重要的集思廣益的過程砂心。
簡要地給出我們的timeline:
1.一開始打算借鑒去年的線性規(guī)劃蛇耀。
比賽前期遇到期末考試纺涤，斷斷續(xù)續(xù)用了一周在Lingo把官網(wǎng)case跑出來了，得到最優(yōu)解783外永，但是耗時4s伯顶，時間太長了骆膝。又嘗試自己寫單純形法來解整數(shù)規(guī)劃，逐漸認定手寫至少很難和商業(yè)上成熟的軟件相比汪厨，耗時問題難以解決劫乱，遂放棄。后來網(wǎng)上有人分享衷戈，他用整數(shù)規(guī)劃成功解決大case，用時超過2小時刁笙，而解決QQ群里面非官方的終極case則需要耗時一天以上疲吸，這條路的確行不通前鹅。
2.大事化小，先解決CDN位置確定時的最小費用最大流問題蹂喻。
謝師兄成功寫出了SPFA算法口四，這個是我們比賽過程中的一個關鍵點秦陋。接著我加入超級源點和超級匯點的思想:超級源點連接設定好的CDN（為了方便，接下來服務器都會被簡稱為CDN）粪小，超級匯點連接所有的消費節(jié)點所連接的網(wǎng)絡節(jié)點抡句，并且保證所有消費節(jié)點連接到超級匯點的鏈路帶寬即為其帶寬需求待榔。至此流济，當確定某幾個節(jié)點為CDN時，可以求出最大流為且只能為固定值時的最小費用問題（后期注：另外據(jù)可靠消息雕憔，zkw算法比SPFA更適用于此圖）斤彼。所以接下來我們只需要想方法來確定CDN位置。
3.用遺傳來確定CDN位置琉苇。
當時擺在我們面前的主要有退火并扇、遺傳這兩種啟發(fā)式搜索方案，我們選擇了遺傳算法⊥僚悖現(xiàn)在回想起來旺坠，這個選擇注定是一條更難的路：首先在選擇初始種群時走了彎路扮超，嘗試了很多種方法來篩選出"CDN候選點"，也就是篩選出哪些點可以作為基因出刷，想來減少后期的計算量；其次種群的迭代太慢了崩侠，迭代出來的也不一定是可行解却音；并且遺傳有個關鍵：要保證產(chǎn)生的子代很大幾率上是優(yōu)于父代矢炼，才能保證整個過程是在優(yōu)勝劣汰。這個關鍵點我們沒有處理好句灌，進一步減慢了迭代速度胰锌。
4.改用退火算法
后來寫出了一版退火算法，立馬就上64強了酬土，在50-60名之間格带。退火更加適合于這道題东揣，我認為關鍵原因在于:退火的求領域解的機制加大了產(chǎn)生可行解的幾率嘶卧，使得迭代的有效率大幅提升芥吟。遺傳不是不好，而是比起退火來難很多钟鸵，導致我們一直沒有調(diào)試出滿意結(jié)果棺耍，當然也可能是我們寫殘了种樱。一打聽周圍的參賽同學，才發(fā)現(xiàn)那些早就順利上榜的人用的都是退火算法害幅。
回過頭來岂昭，我反思為什么我們在遺傳上浪費了太多時間: 不舍得丟棄已有成果约啊，覺得不斷努力肯定會有好結(jié)果。實際上记盒，應當具備一定的預見能力枢里，覺得行不通盡早換方向蹂午。鍥而不舍豆胸，及時止損，這兩者的關系要好好把握與權(quán)衡晚胡，這可能就是大佬經(jīng)驗比我豐富的地方吧。當然止損也有一條捷徑瓷患，那就是要在比賽中保持信息暢通擅编，不能閉門造車。如果我們早知道大多數(shù)人用的都是退火谭贪，自然而然就會更早的轉(zhuǎn)換方向锦担，畢竟重新寫一版代碼代價太大，沒有大把握的話很難有動力去做套媚。所以建議比賽的同學們應當多結(jié)識賽友凑阶，沒人愿意白給你指導衷快，你也得拿有份量的信息去交換，這樣得來的信息比在QQ群和博客得來的有用得多师郑。
5.對圖預處理调窍、優(yōu)化與重構(gòu)。
既然已經(jīng)上榜地梨，那么艱難的爬榜之路就開始了宝剖。代碼重構(gòu)主要是師兄在做，每次優(yōu)化一點兒万细，名次都能往上爬幾名赖钞，但是幾小時后又會有人爬到我們前面來。大家都在優(yōu)化弓千，不進則退放這里是再合適不過了献起。我在做預處理的程序，篩選出必定為CDN的點捌显。這個規(guī)律很好找扶歪，大case能篩選出30-50個點摄闸，大大減少了運算量年枕，名詞進入40-50區(qū)間。
6.發(fā)現(xiàn)重大規(guī)律:只需要在消費點直連的網(wǎng)絡節(jié)點中篩選即可品洛。
我們之前一直是在所有點中進行CDN選點桥状。直到有一天硝清，看到了有一個同學分享的用線性規(guī)劃得到的最優(yōu)解運算結(jié)果芦拿。我對他的數(shù)據(jù)統(tǒng)計分析了一下蔗崎，發(fā)現(xiàn)最優(yōu)解的CDN位置基本均為消費點直連的網(wǎng)絡節(jié)點，偶爾有一兩個落單的點為普通的網(wǎng)絡節(jié)點裙盾。為了效率他嫡，我覺得暫時可以直接在消費點直連的網(wǎng)絡節(jié)點中進行CDN選點即可。因為這個規(guī)律的發(fā)現(xiàn)徘熔，再加上對圖預處理的過程酷师，名次進入了30-40區(qū)間染乌。所以無論通過什么方法求解，也許是暴力大法台颠，也許是線性規(guī)劃串前，雖然這些方法不可以用在最終代碼中荡碾，但是可以獲得用于參考的最優(yōu)解局装。這就相當于做習題時拿到了沒有運算過程的最終答案铐尚，從答案往過程推導也是一個獲得思路的好方法塑径。
7.用C++重寫。统舀。誉简。
目前為止TOP64至少是保住了闷串，綠卡問題不大了。接下來都在優(yōu)化與重構(gòu)桨武，發(fā)現(xiàn)Java效率實在底下锈津，迭代次數(shù)比C++慢了五倍不止琼梆。官方說法是Java和C++差異可以忽略茎杂，這個只能參考错览，千萬別采納。C++作為競賽語言是有原因的煌往，道理我們都懂倾哺，依舊走了彎路，萬事都是如此携冤，你不體會一遍就不會長記性悼粮。
復活賽競爭異常激烈，復活賽最終的前四放初賽是可以進前15的(此數(shù)據(jù)僅供參考曾棕，并不嚴謹)扣猫。所以能在初賽完成的目標，千萬不要拖到復活賽翘地。用CPP重寫后申尤，初級和中級接近滿分了，高級case實在沒時間調(diào)試了衙耕，若放初賽這結(jié)果進前32是穩(wěn)的时鸵。不過沒什么可遺憾的，大佬們的確很厲害，希望自己多汲取教訓薯酝，多掌握經(jīng)驗者填。
最終我們的代碼構(gòu)成為：退火算法尋址 + SPFA算法求路徑 by C++語言穴亏。附上github源代碼以及目錄:
數(shù)十個賽區(qū)刺覆，只有西北川渝等賽區(qū)的競爭才算是白熱化，尤其是成電酝枢、西電等高校長期30多個隊伍霸屏TOP64榜，而其他賽區(qū)進TOP64和拿綠卡難度并不大。所以我明年肯定會推薦學弟學妹們來參加這個比賽古胆，性價比還是很高的隧哮。
比賽過程中陨帆，偶遇開發(fā)者論壇愚人節(jié)活動。運氣比較好亥鸠，我們隊三個人拿了兩套華為code craft衛(wèi)衣和小原公仔。感謝我的隊友：謝師兄和任同學家妆，尤其感謝他們給我做隊長的機會姨伤，比賽完帶隊友們?nèi)コ噗嗤こ粤艘活D飯，放張照弱弱地紀念一下：
寫下這篇文章词渤，主要是給自己隊伍的工作做個總結(jié)，也給其他和我一樣的"小白"提供參賽經(jīng)驗慧妄。歡迎關注，歡迎討論运挫。
