2022华为软件精英挑战赛复盘_华为软件挑战赛题目

2022华为软件精英挑战赛复盘

1 赛题预览

题目背景对标的是华为公司华为云的一个真实业务背景，可以大致理解为视频直播服务中的流量调度问题。大概有全球3千多支队伍参赛，赛事规模10万人左右。
emmm将赛事规则浅显的举个例子，比如针对一个微视频客户端，用户在不同的时间线会批量的产生视频请求需求；视频请求可以通过不同地区的服务器进行反馈（受空间和硬件限制存在qos约束，通俗点说就是部分服务器可用且服务器负载有限），如何合理分配流量使得带宽成本最小是赛制的核心任务。赛题中一个比较重要的设定就是服务器成本的计算方式，区别于传统的用多少付多少，赛制的服务器采用跨时间线的95%分位数作为基础成本，使整个赛题有了更多的优化空间，后面会详细解释。

初赛任务书中的赛题描述如下：

优化目标 赛制核心是合理分配方案，是优化带宽成本，那么带宽成本怎么计算呢？每一个边缘节点的带宽成本是边缘节点（服务器）所有时间负载的流量组成的数组，按从小到大排序，取排序95%位置的流量值。总成本就是所有边缘节点的带宽成本之和。举个例子，假如一个边缘节点在1~20时刻，接收的流量分别是2，4，…，40，1，3，…，19，对他们排序，就是1，…，40。然后95%的位置是38，所以该边缘节点的成本就是38。使所有的边缘节点的95分位和最小，就是赛制的优化核心。
难点评估和应对方案概览：
**难点 1：**问题为多约束条件下，求成本最低的流量分配方案，由于数据量大、约束多，一般难以求得最优解。
解决方案：利用贪心算法，在成本尽可能小的情况下，找到通用的流量分配方案，随后进行流量迁移，调整分配方案减小成本，并进行多次迭代，使其逼近最优解
**难点 2：**通过节点之间的连接关系实现流量迁移，在迁移结束后都需要重新排序以确定下一个需要迁移节点,由于数据量大，时间复杂度较大，在有限时间内，寻优效果不佳。
解决方案：使用优先队列数据结构，在完成节点的流量迁移后，无需排序，同时采用节点时刻滚动更新的方法，减少了无效迭代，极大降低了时间复杂度

下面大致复盘下我们从初赛到决赛的方案分配思路。

2 初赛实现整体思路：全局贪心初始化、遍历装填、组合优化、子问题分解

总体概括而言有三轮迭代优化。每次解决赛制的一个核心任务。
第一轮 预装填边缘节点，找到每个时刻最有可能满载的边缘节点，对这个时刻的边缘节点预先进行装填（全局贪心）
第二轮 按客户节点需求大小，在满足可行解的情况下，按排序规则依次装填，按容量大小和比例装填。（保证有可行解的前提下进行迭代）
第三轮 搬运95节点百分位。（赛制性暴力优化，这也是最后几乎将时间全部用完的核心原因）
下面是详细的执行方案。

first step（针对边缘节点 对最有可能超过95%分位的时刻节点进行预装填）

第一阶段优化思路：对于单个服务器 我们期望它95分位之前尽量平缓，95分位之后尽量塞满，达到最大负荷，换句话说 ，对于单个服务器，95分位后的时刻，服务器用的越多越好，用多少赚多少。什么时候服务器能达到这个状态呢，答案很容易想到，时间跨度上需求最大的时候最容易达到，这种情况下服务器最容易满载。于是我们针对单个边缘节点，挨个统计他所有时刻中，所链接用户的需求总和最大的5% 预先保证这些时刻，服务器装的越多越好，越多越赚。
换句话说,第一阶段想达成的主要目的是，如果能事先找到每个边缘节点装的最满的时刻，把这些时刻尽量装满，成本优化最多

1. 获取边缘节点分别在100个时刻的（针对与其相连的所有客户节点)需求总和序列
2. 对上方的序列进行排序，截取最大的5% (根据题意中的95%分位,边缘节点所有时刻中，装的最多的5%时刻可理解为白嫖阶段，我们此刻选取的5%最有可能能达到上述条件）
3. 针对每个边缘节点，挨个按时刻进行装填(装填后需按时刻更新需求表），此时需决定，先装哪个边缘节点，因为分配方案不可逆，顺序影响后续的装填方案。针对哪个节点先装也构成整体方案的调参点
   • 对所有边缘节点进行排序，遵守下述规则
     1. 按边缘节点链接的用户数量排序，链接数小的优先（保证不炸）
     2. 当链接数一致时，按边缘节点所连接的用户节点的需求总和排序，大的优先（其实也是保证不炸）
4. 每个边缘节点装填时，该如何装填也需遵守一定的规则
   1. 根据与边缘节点相连的用户节点，依次装载用户节点剩余带宽的10%（如果边缘节点此刻的带宽少于客户节点剩余的10%，将剩余的数据按比例平均分配给剩余的节点） 设定规则，装满了就换下一个
   2. 装填后需要更新最后的分配表以及需求表
5. 第一轮结束后，我们会得到一个新的需求表和分配表（只有部分的时刻有数值）

second step（遍历每个时刻的客户节点，对其需求依次进行装填）

第二轮迭代的主要任务，就是在保证有可行解的前提下，均匀分配客户节点的需求到与其相连的边缘节点，规避爆栈的极端情况。

1. 先进行排序，客户节点需求大的先装
2. 装客户节点时遵循两个规则
   1. 与其关联的边缘节点，带宽大的边缘节点先装
   2. 每次装边缘节点时，依次按节点剩余的比例装载（目前最好的效果是按边缘节点剩余带宽的0.5%进行装填）

third step（找寻此刻每个边缘节点的95%分位，将上面的负载依次搬运到同时刻的其余节点上）

第三轮的核心任务就是暴力搬运优化，在尽可能时间复杂度低的条件下降低整体的95%分位成本

1. 对边缘节点内部的所有进行排序 找出当前的95%百分位（此处使用了优先队列）
2. 搬运而言，先搬方差比较大的节点（数据波动比较明显 亟需将其修改为平缓的直线）
3. 具体搬运的过程中，主要搬运当前边缘节点所连接的所有用户节点所能连接的所有边缘节点，找空位进行装填

3 复赛：离散优化

复赛训练赛引入了流的概念，客户节点需求的是多个流，每个流只能分配给一个边缘节点，因此问题就从连续优化变成了离散优化。

流的概念

也就是说此时的客户节点对于流X有这么多的需求 需要分配到与其相连的边缘节点上 分配到谁的头上都行（只要有的选且不炸）

同时带宽成本也有了变化，不再是95%分位点的流量值，而是95%分位点的函数关系。此外，如果边缘节点如果没有被使用，那么边缘节点成本就为0。

核心总结： 增加流的概念（影响用户节点装填方式）

现在的需求文件当中，每个时刻目前都有一系列流，每个流能满足用户节点不同的需求
在复赛当中，做出了以下规定，

1. 在每个时刻，每个用户节点对于每种流会有带宽需求（0 表示该时刻该客户节点对
   这种流无带宽需求）。 为了实现流的流向端到端可追溯，在每个时刻， 一个用户
   节点对一种流的带宽需求需要不可拆分地分配到一个边缘节点。

2. 换句话说，目前所有用户节点的需求在指定了有限边缘节点的基础上，在装载需求阶段，
   还只能一块一块的进行装填，一个时间段有多少个流，就需要完整的将多少块碎片将其
   装载到和其相邻的边缘节点上。

3. 再简化来说，就是当前客户节点在装填边缘节点时，装的块数量和大小固定

4. 成本改动

   1. 目前边缘节点的成本依旧是选取95%分位，只是目前在计算出百分位后的数值后，会和V比较，如果成本大于V，则成本会显著增加，赛方意图是将95%的数值尽量控制在v以下
   2. 

first step（针对边缘节点 对最有可能超过95%分位的时刻节点进行预装填 针对新的流 需要将需求按快装填）

1. 获取边缘节点分别在所有（例：100个）时刻的（针对与其相连的所有客户节点)需求总和序列
2. 对上方的序列进行排序，截取最大的5% (根据题意中的95%分位,边缘节点所有时刻中，装的最多的5%时刻可理解为白嫖阶段，我们此刻选取的5%最有可能能达到上述条件，填的越满，越能趋近最优解）
3. 选中了需要预先装填的时刻后，挨个按选中的时刻针对每个边缘节点进行装填(装填后需按时刻更新需求表），此时需决定，先装哪个边缘节点，因为分配方案不可逆，顺序影响后续的装填方案。针对哪个节点先装也构成整体方案的调参点
   • 对所有边缘节点进行排序，遵守下述规则
     1. 按边缘节点链接的用户数量排序，链接数小的优先（保证不炸）
     2. 当链接数一致时，按边缘节点所连接的用户节点的需求总和排序，大的优先（其实也是保证不炸）
     3. 针对边缘节点可用的stream，也需要考核如何排序（目前暂时还没考虑这一层，暂时使用的前两项决定使用先装填哪个边缘节点）
     4. 5.19优化 根据边缘节点的带宽大小进行排序 下午 根据边缘节点*与它相连的边缘
4. 每个边缘节点装填时，该如何装填也需遵守一定的规则
   1. 这里装填时不能像之前一样按剩余比例装填，这里的装填需要 针对边缘节点可用的stream，也需要考核如何排序， 目前的思路是优先装载最大的流
   2. 装填后需要更新最后的分配表以及需求表
5. 第一轮结束后，我们会得到一个新的需求表和分配表（只有部分的时刻有数值）

预装填环节

1. 将所有边缘节点的负载都预先装载到v
2. 在装载完毕后，需要将所有的需求表全部更新
3. 注意:预装填位置需要放在5%的边缘节点以及完全装置完毕之后，（问题是 此刻的预装填还有意义么） 那之前的5%分位事先装填是不是就不存在意义了（额 这个预装填是在更新需求表之后进行装填的 所以严格来讲还是有作用的）

second step（遍历每个时刻的客户节点，对其需求依次进行装填）

1. 目前此阶段就是将剩余的需求均匀的分给其他节点

third step（找寻此刻每个边缘节点的95%分位，将上面的负载依次搬运到同时刻的其余节点上，对于新阶段，就是将大于V的95%值的往V上搬）

1. 对边缘节点内部的所有进行排序 找出当前的95%百分位（此处使用了优先队列）
2. 搬运而言，先搬方差比较大的节点（数据波动比较明显 亟需将其修改为平缓的直线）
3. 具体搬运的过程中，主要搬运当前边缘节点所连接的所有用户节点所能连接的所有边缘节点，找空位进行装填

4 复活赛优化策略

1、5%时刻数和10%时刻数留余量

现目前可以减10-35的数，也可以是乘以4.9这些

// 5%时刻数
int time_5 = time_num*5/100-15;
// 10%时刻数
int time_10 = time_num*10/100-15;
1
2
3
4

2、预装填

预装填是指将所有的边缘节点都装到V值，可以选择在第一轮之前进行，也可以在第一轮结束后运行。

/**
* 预装填到V
* 将所有节点的所有时刻都装到V
*/
for (int i = 0; i < time_num; i++) {
    // 遍历每个边缘节点
    for (Map.Entry<String, EdgeNode> entry : each_time_edgeList.get(i).entrySet()) {
        if (entry.getValue().usedBandwidth >= V_value) {
            continue;
        }
        for (UserNode userNode : entry.getValue().linkUser) {
            if (entry.getValue().usedBandwidth >= V_value) {
                break;
            }
            for (Map.Entry<String,Stream> streamEntry : each_time_userList.get(i).get(userNode.getName()).linkStream.entrySet()) {
                int demand = streamEntry.getValue().getDemand();
                if (demand <=0) {
                    continue;
                }
                if (entry.getValue().usedBandwidth >= V_value) {
                    break;
                }
                if (demand + entry.getValue().usedBandwidth <= V_value) {
                    // 更新当前时间段，当前边缘节点带宽
                    each_time_edgeList.get(i).get(entry.getValue().getName()).setBandwidth(each_time_edgeList.get(i).get(entry.getValue().getName()).getBandwidth() - demand);
                    // 更新边缘节点的使用单款
                    each_time_edgeList.get(i).get(entry.getValue().getName()).usedBandwidth+=demand;
                    // 将该Stream 存入该边缘节点
                    each_time_edgeList.get(i).get(entry.getValue().getName()).linkStream.add(new Stream(streamEntry.getValue().getName(),streamEntry.getValue().getUsername(),streamEntry.getValue().getDemand()));
                    // 更新用户节点的需求
                    each_time_userList.get(i).get(streamEntry.getValue().getUsername()).setDemand(each_time_userList.get(i).get(streamEntry.getValue().getUsername()).getDemand()-demand);
                    // 更新用户节点的流的需求
                    each_time_userList.get(i).get(streamEntry.getValue().getUsername()).linkStream.get(streamEntry.getValue().getName()).setDemand(0);
                    // 将信息存入output中
                    List<String> list = output.get(i).get(streamEntry.getValue().getUsername()).getOrDefault(entry.getValue().getName(), new ArrayList<String>());
                    list.add(streamEntry.getValue().getName());
                    output.get(i).get(streamEntry.getValue().getUsername()).put(entry.getValue().getName(),list);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

3、第一轮排序（有待实现） 已实现 有提升

现目前是根据边缘节点的带宽除以边缘节点所连接的客户节点的数量来排序。

// 对边缘节点进行排序
edgeList.sort(new Comparator<EdgeNode>() {
@Override
public int compare(EdgeNode o1, EdgeNode o2) {
return o2.getBandwidth()/o2.linkUser.size() - o1.getBandwidth()/o1.linkUser.size();
}
});
1
2
3
4
5
6
7

可以让被选择的那十个节点在前面待实现

4、第二轮对边缘节点进行排序（有需要实现的点）

现在直接根据边缘节点的带宽从大到小排序

// 对用户节点所连的边缘节点进行排序
int time_now = i;
entry.getValue().linkEdge.sort(new Comparator<EdgeNode>() {
@Override
public int compare(EdgeNode o1, EdgeNode o2) {
return each_time_edgeList.get(time_now).get(o2.getName()).getBandwidth() - each_time_edgeList.get(time_now).get(o1.getName()).getBandwidth();
}
});
1
2
3
4
5
6
7
8

后续可以将那5%或10%的边缘节点放在前面先进行装填，这里就需要记录这些时刻，然后判断，在进行排序 （明天实现一下）

entry.getValue().linkEdge.sort(new Comparator<EdgeNode>() {
              @Override
              public int compare(EdgeNode o1, EdgeNode o2) {
                  if (o1.times_5_10.contains(time_now) && o2.times_5_10.contains(time_now)) {
                      return each_time_edgeList.get(time_now).get(o2.getName()).getBandwidth() - each_time_edgeList.get(time_now).get(o1.getName()).getBandwidth();
                  } else if (!o1.times_5_10.contains(time_now) && o2.times_5_10.contains(time_now)) {
                      return 1;
                  } else if (o1.times_5_10.contains(time_now) && !o2.times_5_10.contains(time_now)) {
                      return -1;
                  } else {
                      return each_time_edgeList.get(time_now).get(o2.getName()).getBandwidth() - each_time_edgeList.get(time_now).get(o1.getName()).getBandwidth();
                  }
              }
          });
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、第三轮的排序（已实现在比赛中需要进行验证） （目前测试 作用不大 目前修改为）

在正式赛中根据边缘节点剩余带宽进行的排序

// 对该用户节点所连接的边缘节点进行排序 TODO

              int tt = time_now;
              each_time_userList.get(time_now).get(userName).linkEdge.sort(new Comparator<EdgeNode>() {
                  @Override
                  public int compare(EdgeNode o1, EdgeNode o2) {

                      return each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth - each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth;

                  }
              });
1
2
3
4
5
6
7
8
9
10
11

可以尝试将5%和10%时刻的边缘节点放在前面，优先进行装填

// 对该用户节点所连接的边缘节点进行排序 TODO
              int tt = time_now;
              each_time_userList.get(time_now).get(userName).linkEdge.sort(new Comparator<EdgeNode>() {
                  @Override
                  public int compare(EdgeNode o1, EdgeNode o2) {
                      if (each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth > edgeNodeMap.get(o2.getName()).eachTimeAllUserDemondQueue.peek()[1]
                              && each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth > edgeNodeMap.get(o1.getName()).eachTimeAllUserDemondQueue.peek()[1]) {
                          return each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth - each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth;
                      } else if (each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth > edgeNodeMap.get(o2.getName()).eachTimeAllUserDemondQueue.peek()[1]
                              && each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth < edgeNodeMap.get(o1.getName()).eachTimeAllUserDemondQueue.peek()[1]) {
                          return 1;
                      } else if (each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth < edgeNodeMap.get(o2.getName()).eachTimeAllUserDemondQueue.peek()[1]
                              && each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth > edgeNodeMap.get(o1.getName()).eachTimeAllUserDemondQueue.peek()[1]) {
                          return -1;
                      } else {
                          return each_time_edgeList.get(tt).get(o1.getName()).usedBandwidth - each_time_edgeList.get(tt).get(o2.getName()).usedBandwidth;
                      }
                  }
              });
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

目前是根据边缘节点的usedBandwidth的大小从小到大排序，后续可以考虑根据边缘节点的剩余带宽从大到小排序

6、后续选取10%的边缘节点（有待实现的想法）

现在选取的是95%处最大的那十个节点

// 首先对每个边缘节点每个时刻的使用的带宽进行排序，最终目的是使得95%处的节点在有限队列的顶部
  for (EdgeNode edgeNode : edgeList) {
      edgeNode.eachTimeAllUserDemondQueue.clear();
      for (int i = 0; i < time_num; i++) {
          edgeNode.eachTimeAllUserDemondQueue.add(new int[]{i,each_time_edgeList.get(i).get(edgeNode.getName()).usedBandwidth});
          if (i>time_95) {
              edgeNode.eachTimeAllUserDemondQueue.poll();
          }
      }
  }
  edgeList.sort(new Comparator<EdgeNode>() {
      @Override
      public int compare(EdgeNode o1, EdgeNode o2) {
          return o2.eachTimeAllUserDemondQueue.peek()[1] - o1.eachTimeAllUserDemondQueue.peek()[1];
      }
  });

  preEdge10.clear();;
  for (int i=0;i<10;i++) {
      preEdge10.add(edgeList.get(i).getName());
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

后续可以考虑，找出95%和90%处差值最大的那几个边缘节点这样能保证选取的是最好的那十个节点待实现

7、第三轮中可以尝试以前耗时比较长的方法

即每轮都对被搬入地边缘节点各个时刻地所用带宽进行更新，这样非常耗时，但是能确保每次都能有优化

8、在第三轮搬入搬出操作后，只需要对时刻数在95%或90%内的边缘节点进行更新数据，对于可全部使用的那5%或10%不用进行更新数据，否则会有BUG

如下面的代码所示

// 只有在搬入小于95%地那些节点地时候才对数据进行更新
                      if (each_time_edgeList.get(time_now).get(edgeNode1.getName()).usedBandwidth < edgeNodeMap.get(edgeNode1.getName()).eachTimeAllUserDemondQueue.peek()[1]) {
                          edgeNodeMap.get(edgeNode1.getName()).eachTimeAllUserDemondQueue.add(new int[]{time_now,each_time_edgeList.get(time_now).get(edgeNode1.getName()).usedBandwidth});
                      }
1
2
3
4

5决赛

改动

增加中心节点的概念

也就是根据当前边缘节点流的申请和使用情况，生成一个新的成本，如果想保证这个成本尽量少，

• 单体而言：保证边缘节点对流的申请尽量集中且统一，理想情况下是优先装载之前使用过的同名流（这样很多需求会重叠，中心节点的成本不会叠加上升）
  也就是，针对单个边缘节点而言 如果客户节点在分配流时，如果都能分配的前提下，此时的流优先分配给边缘节点内有相同流的节点 且流的值越大 越分配给哪一个节点

• 整体而言：也存在5%的白嫖空间 当整体中心节点的成本呈更高的斜率和平滑曲线时 中心节点 成本最低（这个要体现在搬运的过程 依次将95%分位往下搬）

  

• 问题：针对客户节点需求的流而言，边缘节点是否可以不装满

  • 搞清楚边缘节点和客户节点的装载关系
    
  • 所以对于每个流，都会完完全全的装载入边缘节点

中心节点计算方式（每个边缘节点都会连接至中心节点）

若边缘节点对于不同的客户节点都装载了同种id的流，哪个装的多 边缘节点对于这个流的请求值就是多少（也就是边缘节点对于流有唯一最大配对），转换为程序逻辑，边缘节点对使用到的同名的流进行排序，都取最大值

（注意 上个时刻的缓存不影响当前时刻的中心节点成本计算）

细节描述：

对于缓存的处理

设计思路：

第一步第二步不变，还是优先白嫖策略

第三步对中心节点进行搬运 目的是搬运后正优化 保证搬运后 不增加另外一个边缘节点中心节点的成本的前提下 进行中心节点最大值降低（注意 此处搬运需要判断是否搬运后会增加边缘节点成本的 或者搬运后整体成本能够得到增加也能够接受）

新的搬运思路 说如果判断出此时的边缘节点流

第四步对边缘节点进行搬运 时间控制在和上面一步保持差不多的节奏 （注意搬运的同时也要增加上述的限制条件）

6.决赛变更点及应对思路

每个时刻可以选取20个节点 修改缓存计算方式 增加可搬运的空间

思路

• 第三轮后 选出每个时刻边缘节点使用的最多20个节点 增加可用负载后，重新进行搬运 降低95百分位和中心节点成本

• 第一轮的时候就选出20个节点（选择边缘节点期望负载最多的）

• 综合比较两种方案的最优值