2017華為軟件精英挑戰(zhàn)賽

1、I背景大視頻解決方案中，視頻業(yè)務體驗非常關鍵，視頻內(nèi)容如何有效傳送到最終消費 者是決定視頻體驗好壞的核心環(huán)節(jié)。I本次賽題基本描述在給定結構的網(wǎng)絡中（如：xx城市的電信網(wǎng)絡），為了視頻內(nèi)容快速低成本的 傳送到每個住戶小區(qū)，需要在這個給定網(wǎng)絡結構中選擇一些網(wǎng)絡節(jié)點附近放置視 頻內(nèi)容存儲服務器。需要解決的問題是：在滿足所有的住戶小區(qū)視頻播放需求的 基本前提下，如何選擇視頻內(nèi)容存儲服務器放置位置，使得成本最小。I本次賽題通用性描述網(wǎng)絡結構模型：給定一個由若干網(wǎng)絡節(jié)點（例如路由器、交換機）構成的網(wǎng)絡結 構無向圖，每個節(jié)點至少與另外一個節(jié)點通過網(wǎng)絡鏈路相連 （網(wǎng)絡鏈路特指兩個 網(wǎng)絡節(jié)點之間直接相連的網(wǎng)絡通

2、路，中間沒有其他網(wǎng)絡節(jié)點，相當于無向圖中的 一條邊），一個節(jié)點可以將收到的數(shù)據(jù)通過網(wǎng)絡鏈路傳輸給相連的另一個節(jié)點， 節(jié)點本身的轉發(fā)能力無上限。每條鏈路的網(wǎng)絡總帶寬不同（例如某條鏈路的總帶 寬為10Gbp§。而每條鏈路承載的視頻傳輸需要按照占用帶寬的多少收取對應 網(wǎng)絡租用費，每條鏈路的單位租用費均不同（例如某條鏈路的租用費為1,000元/Gbps,即1K/Gbps）。某條鏈路上被占用的帶寬總和不得超過該鏈路的總帶 寬。消費節(jié)點：給定的網(wǎng)絡結構中有部分網(wǎng)絡節(jié)點直接連接到小區(qū)住戶的網(wǎng)絡、每個 小區(qū)住戶網(wǎng)絡在這個給定的網(wǎng)絡結構圖中呈現(xiàn)為一個消費節(jié)點， 不同消費節(jié)點的 視頻帶寬消耗需求不同。視

3、頻內(nèi)容服務器：視頻內(nèi)容服務器存放視頻內(nèi)容（如：電影影片、電視劇等）， 視頻內(nèi)容服務器的視頻數(shù)據(jù)流可以經(jīng) 由網(wǎng)絡節(jié)點 與鏈路構成的網(wǎng)絡路徑流向消 費節(jié)點,視頻內(nèi)容服務器的輸出能力沒有上限,可以服務多個消費節(jié)點,一個消 費節(jié)點也可以同時從多臺視頻內(nèi)容服務器獲取視頻流。 部署一臺視頻內(nèi)容服務器 需要費用成本（例如300,000元/臺，即300K/臺），所有服務器的成本均相同。比賽程序內(nèi)容：請你設計一個程序尋找最優(yōu)的視頻內(nèi)容服務器部署方案：從網(wǎng)絡結構模型中選擇一部分網(wǎng)絡節(jié)點，在其上 /附近一對一的部署視頻內(nèi)容服務器， 視頻內(nèi)容服務器與對應的這個節(jié)點直連，與對應的這個網(wǎng)絡節(jié)點之間的通信沒有帶寬限制，也沒

4、有通信成本。提供的部署方案需要使得視頻流從視頻內(nèi)容服務 器經(jīng)過一些網(wǎng)絡節(jié)點和鏈路到達消費節(jié)點，滿足所有消費節(jié)點的視頻帶寬消耗需 求，并使得耗費的總成本（視頻內(nèi)容服務器部署成本+帶寬租用成本）最低。部 署方案不僅需要包括部署視頻內(nèi)容服務器的節(jié)點位置，而且還要包括每個消費 節(jié)點與所有視頻內(nèi)容服務器之間的網(wǎng)絡路徑以及路徑上占用的帶寬。I比賽勝負規(guī)則若給定的網(wǎng)絡拓撲模型不存在滿足條件的方案，則輸出無解，程序運行時間越短者勝出。若存在滿足條件的方案，則成本越低者勝出。若兩個方案的成本相同， 則程序運行時間越短者勝出。I補充說明1 .兩個網(wǎng)絡節(jié)點之間最多僅存在一條鏈路,鏈路上下行方向的網(wǎng)絡總帶寬相互 獨立

5、，并且上下行方向的總帶寬與網(wǎng)絡租用費相同。例如對于網(wǎng)絡節(jié)點A與B之間的鏈路，該條鏈路上的總帶寬為 10Gbp6單位租用費為1K/Gbps,則表示 A->B、B->A兩個方向上的網(wǎng)絡總帶寬分別為10Gbp6并且租用費均為1K/Gbp& 如果某條數(shù)據(jù)流在該鏈路 A->B方向的占用帶寬為3Gbps,那么該數(shù)據(jù)流在該鏈 路的租用費為3K,并且該鏈路 A->B方向的剩余可用帶寬為 7Gbps而B->A方向 的剩余可用帶寬不受該數(shù)據(jù)流的影響，仍為10Gbps2 .每個網(wǎng)絡節(jié)點最多僅能連接一個消費節(jié)點，每個消費節(jié)點僅能連接一個網(wǎng) 絡節(jié)點。消費節(jié)點與連接的網(wǎng)絡節(jié)點之間的鏈

6、路總帶寬無限大，并且網(wǎng)絡租用費為零。3 .網(wǎng)絡節(jié)點數(shù)量不超過1000個，每個節(jié)點的鏈路數(shù)量不超過 20條，消費節(jié)點 的數(shù)量不超過500個。4 .鏈路總帶寬與單位網(wǎng)絡租用費為0, 100的整數(shù)，視頻內(nèi)容服務器部署成本 與消費節(jié)點的視頻帶寬消耗需求為0,5000的整數(shù)。5 . 部署方案中，網(wǎng)絡路徑上的占用帶寬必須為大于等于0的整數(shù)=6 .“滿足消費節(jié)點的帶寬消耗需求”是指輸出給消費節(jié)點的帶寬總和不得小于該消費節(jié)點的視頻帶寬消耗需求。7 .每個網(wǎng)絡節(jié)點上最多僅可部署一臺視頻內(nèi)容服務器I比賽用例示例上圖為A市網(wǎng)絡拓撲圖，黑色圓圈為網(wǎng)絡節(jié)點，紅色圓圈為消費節(jié)點，圓圈內(nèi)的 數(shù)字為節(jié)點編號。節(jié)點之間的連線為

7、網(wǎng)絡鏈路。鏈路上的標記（x, y）中，x表示鏈路總帶寬（單位為Gbps） , y表示每Gbps的網(wǎng)絡租用費。消費節(jié)點相連鏈路 上的數(shù)字為消費節(jié)點的帶寬消耗需求（單位為Gbp§ ?，F(xiàn)在假設需要在該網(wǎng)絡上部署視頻內(nèi)容服務器， 滿足所有消費節(jié)點的需求（注意: 對于任意用例至少存在一個可行解，即在每個消費節(jié)點直接相連的網(wǎng)絡節(jié)點上部 署一臺服務器）。那么一個成本較低的方案可以如下圖所示，其中綠色圓圈表示 已部署的視頻內(nèi)容服務器，通往不同消費節(jié)點的網(wǎng)絡路徑用不同顏色標識，并附帶了占用帶寬的大?。旱摲桨傅某杀静灰欢ㄊ亲畹偷?。因此現(xiàn)在需要參賽者提供的程序能夠針對不同 的比賽用例，給出成本最低的部署

8、方案。?程序輸入與輸出？I輸入文件格式程序輸入為一個以空格分隔的文本文件，文件每行以換行符（ASCII' n '即0x0a） 為結尾。文件格式為：網(wǎng)絡節(jié)點數(shù)量網(wǎng)絡鏈路數(shù)量消費節(jié)點數(shù)量（空行）視頻內(nèi)容服務器部署成本（空行）鏈路起始節(jié)點ID鏈路終止節(jié)點ID總帶寬大小單位網(wǎng)絡租用費,.（如上鏈路信息若干行）（空行）消費節(jié)點ID相連網(wǎng)絡節(jié)點ID視頻帶寬消耗需求,.（如上終端用戶信息若干行）（文件結束）說明：1 .網(wǎng)絡節(jié)點ID與消費節(jié)點ID均為以0為起始的整數(shù)。2 .文本中出現(xiàn)的所有數(shù)值均為大于等于 0的整數(shù)，數(shù)值上限為100000。I輸入文件示例（參照第一節(jié)中的用例）28 45 12

9、/ 注：28個網(wǎng)絡節(jié)點，45條鏈路，12個消費節(jié)點100 /注：服務器部署成本為1000 16 8 2 / 注：鏈路起始節(jié)點為0,鏈路終止節(jié)點為16,總帶寬為8,單位網(wǎng) 絡租用費為20 26 13 20 9 14 20 8 36 2（以下省略若干行網(wǎng)絡節(jié)點信息）0 8 40 / 注：消費節(jié)點為0,相連網(wǎng)絡節(jié)點ID為8,視頻帶寬消耗需求為401 11 132 22 283 3 454 17 115 19 266 16 157 13 138 5 1810 7 10 11 24 23I輸出文件格式程序輸出為一個以空格分隔的文本文件，文件每行以換行符（ASCII'n '即0x0a） 為

10、結尾。程序結果按如下格式輸出：網(wǎng)絡路徑數(shù)量（空行）網(wǎng)絡節(jié)點ID-01網(wǎng)絡節(jié)點ID-02 , 網(wǎng)絡節(jié)點ID-n消費節(jié)點ID占用帶寬大 小,.（如上網(wǎng)絡路徑信息若干行，每條網(wǎng)絡路徑由若干網(wǎng)絡節(jié)點構成，路徑的起始節(jié)點ID-01表示該節(jié)點部署了視頻內(nèi)容服務器，終止節(jié)點為某個消費 節(jié)點）（文件結束）說明：1 .網(wǎng)絡路徑數(shù)量不得超過50000條。2 .單條路徑的節(jié)點數(shù)量不得超過1000個。3 .不同網(wǎng)絡路徑可按任意先后順序輸出。4 .網(wǎng)絡節(jié)點ID與消費節(jié)點ID的數(shù)值必須與輸入文件相符合，如果ID數(shù)值不 存在于輸入文件中，則將被視為無效結果。5 .文本文件中出現(xiàn)的所有數(shù)值必須為大于等于0的整數(shù)，數(shù)值大小不得

11、超過1000000I輸出文件示例（參照第一節(jié)中的用例部署方案）19 / 注：共輸出19條網(wǎng)絡路徑0 9 11 1 13 / 注：起始網(wǎng)絡節(jié)點ID為0,經(jīng)由ID為9、11等網(wǎng)絡節(jié)點到達 消費節(jié)點為1,占用帶寬為130 7 10 100 6 5 8 13（以下省略網(wǎng)絡路徑若干行）?單個用例的評分機制？I用例的排名機制按下面流程對參賽者結果進行排名：Stepl :對于提交的結果，進行合法性檢驗（詳見題目描述）；Step2 :單個用例的程序運行時間不得超過 90s;若不滿足上述的結果則本用例得分為 0;Step3:計算部署方案的成本，成本越小，排名越優(yōu)；Step4：在成本相同的結果里，用程序運行時間進行排名，時間越短，排名越優(yōu)。I單個用例的評分標準如下根據(jù)上面排名流程得到的排名，使用標準分計分 （排名第一的提交者為100分）。 若所有人均未得到正確結果，則所有人均得分為00?最終得分機制？比賽平臺會使用N個測試用例判題，該N個測試用例分為初級、中級、高級三個 等級，參賽者對于每個測試用例都會得到一個百分制分數(shù)，使用加權平均分 （初 級權重為0.2 ,中級權重為0.3 ,高級權重為0.5）作為該