大賽官網：http://codecraft.huawei.com/
賽題解讀：http://mp.weixin.qq.com/s/on_l5Rc3Be-DjgUOXftaNw
賽題案例以及編譯官方軟體包：HUAWEI_Code_Craft_2017_初賽軟體包(readme.txt中有詳細介紹)
從2017.3.15到2017.4.6，花費三個星期的時間投入到2017華為精英挑戰賽。我是第一次參加這種類似于ACM的算法競賽，雖然成績從最初前32強最後跌出64強無緣複賽，但是真的學到了很多東西。大神好多，高手如雲，繼續努力！
在此分享一下比賽心得，總結在這次挑戰賽中所做的努力和工作：
上圖為G省網絡拓撲圖，黑色圓圈為網絡節點，紅色圓圈為消費節點，圓圈内的數字為節點編号。節點之間的連線為網絡鍊路。鍊路上的标記(x, y)中，x表示鍊路總帶寬（機關為Gbps），y表示每Gbps的網絡租用費。消費節點相連鍊路上的數字為消費節點的帶寬消耗需求（機關為Gbps）。
現在假設需要在該網絡上部署視訊内容伺服器，滿足所有消費節點的需求。一個成本較低的方案如下圖所示（選擇0,1,24作為伺服器），其中綠色圓圈表示已部署的視訊内容伺服器，通往不同消費節點的網絡路徑用不同顔色辨別，并附帶了占用帶寬的大小：
通過分析賽題我們小組發現可以總結為以下幾個問題：
1.當選定伺服器位置時，如何制定給消費節點提供帶寬的政策？
舉例：如圖中，選擇0,1,24作為伺服器，如何制定政策在滿足所有消費節點帶寬需求的前提下，使所花費用最小。
2.如何選擇伺服器的位置？
l 初始伺服器位置選擇問題
l 更新伺服器位置政策問題
解答：
針對問題1：
采用最小費用最大流的方法(該算法用來解決從一個點到另一個點，提供帶寬最大時，所需的最小費用)，将所有伺服器連向一個超級伺服器(源點)，将所有消費節點連向一個超級消費節點(彙點)。例如：選擇伺服器0,1,24時，連接配接方案如下圖所示。注意：源點到伺服器帶寬無限，費用為0，單向傳輸；消費節點到彙點帶寬為自身所需帶寬，費用為0，單向傳輸。此時隻需計算源點到彙點的最小費用最大流就可以了。如果費用流最大帶寬<所有節點所需帶寬和(即彙點所需帶寬)，那麼所選伺服器無法滿足要求，否則一定滿足要求，并計算出了源點到彙點的最小費用。最後加上單個伺服器費用*伺服器個數即可求得此次的總最小花費。
如果不這樣連接配接和考慮問題，在計算時會遇到計算邏輯複雜和計算速度慢的問題。通過不斷地優化，我們最終在資料規模達到網絡節點800點、消費節點360點時，計算一次費用流隻需10ms左右。
針對問題2：
方法1：這個賽題明顯是一個NP-Hard問題，最開始我們想用暴力的方法解決，首先與每個消費節點直接相連接配接的網絡節點放置局伺服器(即初始伺服器位置選擇，因為這樣一定可以保證有解)，然後全局網絡節點考慮，對伺服器集合要麼随機采用減一個、換一個或者加一個伺服器，然後利用每次標明的伺服器集合去計算費用流，存儲花費最小的一次費用流。疊代運作直到最後收斂或者達到題目運作時間限制。其中，什麼時候減和加都是随機數随機選擇的，而且減哪個加哪個網絡節點也是由随機數随機選擇的，這樣就保證了一定随機性，防止陷入局部最優（實際上，我們還是沒有很好解決這個問題）。
方法2：由于當資料規模增大到一定程度時，方法1的算法無法在題目要求的90s内收斂，是以要求一個更快的收斂方案。第二個方法還是利用直連的方法布局初始伺服器集合，而我們隻在目前與消費節點直連伺服器中随機減一個或者換一個，直到收斂，取最少費用的一次伺服器布局。這樣我們相當于将原來在800個點的網絡節點中搜尋解，轉化為了在360個消費節點直連的網絡節點中搜尋點，顯然我們的算法無法找到全局最優解，但是這樣可以在有限的時間内更快的收斂，達到一個更小的費用。 由于一直在直連網絡節點中搜尋，是以對伺服器單價不高的情況還是有不錯的解的。并且因為一直在直連中計算費用流，在規定時間内計算費用流時間縮減了很多，是以在大案例中有不錯的解。大案例(800網絡節點)中我們測試得出疊代次數可以多達3萬多次，而第一種方法僅有3000多次，快了10倍。在大案例中追求有限時間内搜尋最優解還是很不錯的idea，得益于此在大規模的比賽樣例中我們取得了不錯的成績。
方法3：其實很明顯，上面兩種方法都會遇到跳不出局部最優解的問題，一旦我們陷入一個局部最優解根本跳不出去，顯然還是需要一個啟發式的方法，經典的算法像蟻群，爬山，模拟退火，遺傳算法，粒子群等，大家可以查閱相關論文，這些都是經典TSP問題很好的解決方法，用在這裡肯定也是可行的。 我們最後在伺服器選址使用的是模拟退火，算法簡單又快速，這也是我們第三種算法。第三種方法初始化還是使用的直連的方法，每次随機加一個伺服器、減一個或者換一個，但是我們并不是将這個機率設死，不是對目前花費沒有減小的效果就舍棄這次抉擇，而是以一定機率去接受它，并且這個機率随着疊代深入慢慢減小，這就是經典的模拟退火的算法，一定程度上可以避免陷入局部最優。
待實作的方法：
但是很遺憾，想法是挺好的，由于沒有經驗，經過兩天調參我們的效果還是不理想，沒有解決陷入局部最優的困局。直到比賽結束這個問題也沒有解決，最後很遺憾沒有進入複賽。
其實解決局部最好方法就是增加随機性，一個是選擇伺服器的時候加大随機性，這裡rand()是以使用時間作為srand參數自然是最好的。
另外初始伺服器的随機性，是以一旦結果收斂我們應該重新開機再繼續搜尋，但是很遺憾這個方法我們沒有時間實踐了，就是伺服器布局不要選擇直連，而是全局随機選擇跟消費節點數量相同的伺服器，然後多次抉擇直到收斂。
最後還有一個思想是經過模拟退火後，接受機率會越來越小，陷入局部最優解。之後我們應該将溫度重新升溫，即接受機率恢複到某一值，重新降溫，如此反複。
我覺得我們失敗就是敗在了這裡，有些遺憾，在最後才想明白。其它人的方法我就不知道，可能還有一些比較啟發的選擇方法，我們另外還根據每個網絡節點的出度設計每個網絡節點選擇為伺服器的權重，自然出度大情況我們更希望它被選擇為伺服器，但最終效果也不盡如人意。等比賽結束看看大神們的代碼，膜拜一下，再重新思考一下該問題。
我們所做過的優化案例：
整個過程，我們對算法做了很多優化，雖然我們沒有逃出局部最優解的困局，但是我敢說我們最小費用和整個算法優化是頂尖的。看讨論群裡他們分享的速度都沒有我們的快。
主要有以下的優化：
1、費用流計算中不管中間路線布局，我們将多源多彙問題優化為單元對單元，也就是模拟設計兩個超級節點，一個連接配接所有伺服器，一個連接配接所有消費節點，整個過程簡化為單源單彙費用流問題；
2、每疊代一次不必重新加載所有圖資料，我們采用個别資料還原再重新進行下一輪的最小費用流計算即可；
3、伺服器集合存儲的時候，我們采用标準模闆庫中set資料結構其實是最好的，第一伺服器不會重複set很符合這個性質，第二set是基于紅黑樹實作的，插入删除很快速，是以使用set比其他任何資料結構都要好，這個設計又讓我們的算法效率提高了不少；
4、在各種循環中，應考慮其提前終止的情況，避免沒有意義的計算。
以上就是我的總結，雖然很遺憾沒有進入複賽，但是過程還是學習了不少，繼續加油！
最後提供我們的代碼：https://github.com/DUTFangXiang/2017HuaWei_CraftCode