文章目录

• 前言
• 一、软挑的基本形式与内容
• 二、初赛阶段的赛题与方案介绍
• • 1. 赛题介绍
  • • (1) 题目介绍
    • (2) 约束条件
    • (3) 优化目标
  • 2. 方案介绍
  • • (1) 思路分析
    • (2) 初步方案设计
    • • 1. 分配策略-排水法
      • 2. 络流
    • (3) 方案验证与分析
    • • 1. 训练赛阶段
      • 2. 正式赛阶段
• 三、复赛阶段的赛题与方案介绍
• • 1.赛题介绍
  • 2.方案介绍
  • • (1) 思路分析
    • (2) 初步设计方案
    • (3) 方案验证与分析
  • 3.主要困难点与细节问题
• 四、决赛阶段的赛题与方案介绍
• • 1.赛题介绍
  • 2.方案介绍
  • • (1) 思路分析
    • (2) 初步设计方案
    • (3) 方案验证与分析
  • 3.主要困难点与细节问题
• 总结

前言

一、软挑的基本形式与内容

• 赛制：软挑的整个比赛形式分为初赛、复赛、决赛三个阶段；每个阶段先是进行10天左右的训练赛，选手可以线上提交代码，然后根据官方的判题器进行评分并排名（训练赛阶段的排名仅仅作为参考，可以方便选手知道自己代码方案的优劣从而合理选择代码迭代方向）；正式赛阶段时间较短（初赛阶段的正式赛为3天，复赛与决赛均为3小时），相较于训练赛，会进行小的题目变更，选手需要在短时间内调整代码方案并进行有效的版本迭代。
• 奖励：2022年的软挑共分了8大赛区，共3291支队伍。初赛阶段，每个赛区的前32名可以获得进入复赛的机会，并拿到华为的机试绿卡（免除机试），前64名可以获得参赛证书；复赛阶段，每个赛区的前4名（因为意外情况，今年临时增加了复活赛，每个赛区额外增加了2个决赛名额）可以进入决赛，并可获得华为的面试绿卡（免除华为两轮技术面试）与一部华为手机；决赛阶段，前8名可以获得奖金。
• 赛题：此次赛题以华为云视频直播服务流量调度问题为基础，并进行一定的抽象调整和简化，关注如何实现云上资源的最优规划和调度问题。赛题的核心类似于边缘计算的任务卸载问题，需要尽量降低任务计算成本。赛题要素主要包含：N个边缘计算节点，以及M个用户节点；时间离散化为T个时刻；每个时刻中，不同用户有多个不同的任务需求；成本计算主要围绕“95分位”这一概念进行梯度计算，因为计算规则比较复杂，所以后续再对这一点具体展开介绍。

二、初赛阶段的赛题与方案介绍

1. 赛题介绍

(1) 题目介绍

假设共有M个客户节点与N个边缘节点，现按照时间线进行流量调度。每个时刻，客户都会有不同大小的流量需求。现需要给出一种流量调度策略，在每个时刻给出一种流量分配方案，在满足给定限制条件下，总的边缘节点代价最小。在任意一个时刻，每个客户节点的需求可以分配到任意多个边缘节点上。同时，每个边缘节点也可以满足多个客户节点的需求。
下图为题目示意图。

2. 正式赛阶段

正式赛沿用训练赛的分配策略版本，即排水算法（白嫖边缘节点+动态调整）

2.方案介绍

该方案获得了粤港澳赛区训练赛第4，正式赛第4的成绩。复赛的方案整体上基于初赛的算法框架，先是采用贪心的策略，利用“95分位”这一点，尽量分配更多的任务到边缘计算节点的免费时刻；在第二步，修改策略为，每次分配的时候，将任务卸载到产生cost最小的边缘计算节点之上；第三步的优化调整，进行了符合条件的代码更新，使得在调整任务分配情况时，是整个任务块进行调整位置。

(1) 思路分析

1. 不可拆分的问题：由于数据流不可拆分，因此初赛时所考虑的 络流解法不再适用。因为 络流算法涉及到反向边这一概念，从最终结果上来看，会导致数据流的拆分。
2. 由于依然使用“95分位”这一概念，所以贪心策略的方法依然可以尝试。
3. 由于成本计算不再是所有边缘计算节点的“95分位”对应数值的累加和，所以贪心的目标需要进行较大的改动。一方面，一旦某个边缘节点被卸载了数据流，那么只要其“95分位”对应数值在V以下的增长都不会带来成本的提升；另一方面，数值超出V的成本计算，与边缘节点容量以及当前已分配数据量有关，边缘节点容量越大，已分配数据量越少，再分配数据产生的新成本就会越低。
4. 初赛中调整优化的部分也需要较大的变动，因为每次调整需要调整一个完整的数据流，而不再是可以按照数值比较随意的调整，这带来了很大的限制。

(2) 初步设计方案

1. 与初赛第一阶段思路相同，先尽可能的利用零成本的5%时刻点进行分配更多的数据流。这一部分主要是包含选择边缘节点，以及对边缘节点所连接的数据流进行分配这两个子部分。尝试了多种贪心的策略，主要包括：
   a. 计算不同时刻，不同边缘节点分别所连接的数据流大小总和，然后进行排序，按照排序后的结果，选出连接数据流总量最大的，且有剩余零成本时刻的边缘节点。然后对于该边缘节点，按照其所连接数据流的大小，由大到小向该边缘节点进行分配。之后，不考虑已经分配的数据流，重复上述步骤，直至所有的边缘节点不再剩余零成本时刻。
   b. 分别计算不同时刻总的数据流总量，排序，然后将前5%对应的时刻作为所有边缘节点的零成本时刻，并将对应时刻的所有数据流随意分配即可。
   c. 跳过这一步。
2. 第二阶段的思路为，分别将所有时刻的所有边缘节点分配内容填充到V这一总值。
3. 第三阶段的思路为，将所有剩余的未分配的流进行排序，然后由大到小进行分配，分配的具体过程为，分别计算该数据流分配至所连接的边缘节点的成本，选择成本最低的进行分配。这一阶段进行排序后分配的考虑，主要是认为小的数据流，可以更方便的对不同边缘阶段的分配效果进行微调，类似于用瓶子装石头与沙子的问题，先装石头后装沙子可以装下更多。
4. 优化调整部分：该部分依然沿用初赛的整体设计思路，包括两个核心部分：降低95分位节点的数值、压低已分配的零成本时刻数值实现零成本时刻的置换优化。但是在设计的时候，需要单个完整的数据流进行调整。但是，对于复赛的成本计算方式，我们对该阶段进行了一点的优化。成本越高的边缘节点，其一定程度上弹出一个数据流能带来更大的成本的降低，因此，在调整的时候，我们优先去降低成本更高的边缘节点。

(3) 方案验证与分析

1. 第一阶段，采用a方案可以取得较b方案更高的效果；采用c方案的想法，主要是考虑将更多的数据流按照第三阶段的成本计算的方式进行分配，或许能达到更好的分配效果，但是存在的问题是，如果没有第一阶段将大量的流进行分配，那么第三阶段，每个流都需要进行多次计算cost，会导致代码运行超时。
2. 对于阶段b，其效果主要是可以在第三阶段之前分配更多的流，大量减少第三阶段的时间，但是该阶段的负面效果是，其将大量的小数值的流进行了分配，不利于不同边缘节点成本利用小流进行微调。所以是否跳过这一阶段，均需要正式赛的尝试。
3. 对于第三阶段和第四阶段，则没有过多的思路上不同的方案。

训练赛阶段的最终成绩为第四名


3.主要困难点与细节问题

1. 时间优化问题：复赛阶段，我们花费了很多的时间在时间优化上，主要是为了能使得优化调整部分进行更多次的调整，从而对所求得的初始解进行更优的改进。主要是包含了几个部分：a. 在第一阶段选择边缘节点的时候，由于每次选择一个之后就需要更新排序，所以这个部分采用了大顶堆的策略，降低寻找最大值的时间复杂度；b. 优化调整部分，每次降低了95分位对应数值之后，需要重新排序，为了降低复杂度，我们采取了局部排序与整体排序交替的策略，每次排序仅仅对95分位前后长度为m的序列值进行重新排序，并在进行了n次排序之后进行整个序列的排序，只要保证m与n满足一定的关系，则可以保证这种策略排序后的95分位数值是正确的。
2. 优化调整部分的死循环：复赛阶段每次调整一整个数据流，会在逻辑上导致一种死循环——对于两个边缘节点A，B，如果其存在某一时刻t1均为两个边缘节点的零cost时刻，并存在某一时刻t2均为两个边缘节点的非零cost时刻。那么，就会存在导致动态调整在 t1的A节点->t1的B节点->t2的B节点->t2的A节点->t1的A节点 的循环中不断地优化调整。为了解决这一问题，在每个边缘节点的实例中，增加了一个bool类型的数组为属性ifCanDown，一旦某边缘节点的某一时刻，是在“压低已分配的零成本时刻数值实现零成本时刻的置换优化”过程中被判定为零cost时刻，则将对应时刻的值置为true，后续降低零成本时刻的节点的数据流分配量时，先判断ifCanDown属性的对应时刻是否为false，如果是则直接跳过。通过这种方式，能打破死循环，并加快了优化调整的单次过程。

四、决赛阶段的赛题与方案介绍

1.赛题介绍

决赛赛题基于复赛赛题进行改动，主要是变动如下：

• 额外增加了中心节点这一要素，是边缘节点的上一层 络节点。边缘节点从中心节点获取流满足客户节点的带宽需求。在分配的时候需要同时考虑中心节点产生了cost。
• 额外增加了cache这一要素，当前时刻的分配结果，会连续对后续多个时刻产生影响。

具体差异如下所述：

2.方案介绍

该方案获得了全球总决赛训练赛第13，正式赛第27的成绩。决赛的方案整体上基于复赛的算法框架，先是采用贪心的策略，利用“95分位”这一点，尽量分配更多的数据流到边缘计算节点的免费时刻，不过为了处理cache这一条件，分配连续的零成本时刻窗口，而不是离散的零成本时刻点；在第二步，考虑到中心节点的成本问题，修改策略为，每次分配的时候，将任务卸载到产生cost最小的边缘计算节点之上，但是数据流的分配顺序考虑到类型差异；第三步的优化调整，在复赛的基础上，优化调整时增加限制——“不抬高中心节点的成本”。

(1) 思路分析

决赛的变动点，导致题目非常的复杂，主要的问题如下：

1. 对于缓存机制这一限制：初赛与复赛阶段，选手的策略大多是不同时间的分配方案上相互解耦的，而缓存机制的引入，则使得之前的方案需要发生较大的变动，甚至需要放弃之前的思路。这一限制有两个思考方向，一是按照时刻的先后顺序进行分配，这样就可以在对某一时刻t进行分配的时候，直接计算出前一时刻对该时刻的缓存，从而避免超出边缘节点的上限；另一个思考方向就是，每次分配某一时刻的边缘节点，就将该时刻的分配方案对后续多个时刻产生的影响进行分析，并将利用数组记录对后续时刻带来的缓存影响。
2. 中心节点成本：针对这一问题，我们的考虑是，尽量在同一个边缘节点中放置同种类型的数据流。但是这个部分会考虑起来会比较复杂，因为同一类型的流往往会存在很多个较大的流，放在同一个边缘节点中就会导致边缘节点的成本比较高。因此，降低边缘节点的成本和中心节点的成本似乎是一个矛盾点。针对这个问题，我们只能是采用做一些测试的方法，验证如何才能更好的降低

(2) 初步设计方案

1. 第一阶段：由于第一阶段主要是充分利用零成本时刻进行分配，之前的方案会将该边缘节点的容量充满，所以在这个地方需要进行缓存的计算。以下是几个思考方向
   a. 最直接的思路变更为：每分配一个时刻，就计算该时刻对后续时刻造成的影响，降低后续时刻的可容纳带宽。主要是利用递归的方案进行缓存的计算，直到当前时候的分配对后续第n个时候的影响为0，则停止递归。
   b. 按照时间顺序从前往后进行设计分配方案
   c. 利用窗口的形式，设计连续的零成本时刻窗口，窗口内部按时序进行分配。、
   另外，在选定了边缘节点之后，针对其进行分配时，考虑中心节点的成本，按同类型优先分配的策略。
2. 第二阶段：原本的思路是，在分配时，在复赛的版本上，计算分配某一数据流所增加的边缘节点与中心节点成本之和。但是计算中心节点的成本，需要记录每个边缘节点在每个时刻对每种类型的流的分配情况，这一数据结构占用空间过大，不可行。因此，该部分，我们简化为只考虑边缘节点的成本。
3. 第三阶段：优化调整时，测试了一下如果按照原本的思路，只考虑边缘节点的话，虽然通过调整会降低边缘节点的成本，但是会导致中心节点成本上升，所以必须增加对中心节点的限制

(3) 方案验证与分析

1. 对于第一部分：我们首先排除了b，因为如果从0时刻开始遍历的话，相当于放弃了初赛复赛的思路，难以充分利用5%的零成本时刻。首先考虑的是a方案：a方案可以成功的应对题目的变更，可以依然没有比较不错的结果，整体成绩在训练赛的阶段始终是中等靠后，经过对线下数据集以及自己造的数据集的分配结果进行分析，我们发现缓存带来的影响很大，如果我们充分利用5%时刻的零成本时刻，那么这些时刻的带宽则会被抬得很高，就会对我们预计的非零成本时刻产生较大的初始分配量（缓存量），导致结果中边缘节点成本难以通过后续分配算法降低下去。如果进行简单的零成本时刻预留，最直接的方案那就是仅仅利用一半的零成本时刻，另一半为这些高分配量的下一时刻。通过这种方式，就可以使得，在下一阶段开始时，95分位的分配量为0.不过这种分配方案的问题在于，没有充分利用零成本时刻，仅仅使用了一半的零成本时刻。因此，我们考虑采用窗口的形式。窗口形式的好处是，我们可以控制，使用几个窗口，就可以预留几个零成本时刻。窗口内部采用按时间顺序处理的方式，即分配完某一时刻，直接计算造成的下一时刻的缓存值。而且通过这种方式，可以避免计算前面n个时刻对当前所分配时刻的缓存影响的问题，大大提高算法效率，为后面的优化调整预留更多的时间。具体而言，是引入超参数N，表示使用的窗口数量， 则窗口数量为W=（总的离散时间数量*5%-N）/ N。计算不同边缘节点的连续W时刻所连接的数据流的总值，然后排序，选数据流总量最大的进行窗口进行分配，分配时候，按照类型进行分配，从而实现对中心节点的控制。
2. 对于第二部分，则采用复赛版本的计算方式进行处理
3. 对于第三部分的优化调整，则是通过限制中心节点和边缘节点成本升高的基础上进行调整的。为了降低计算中心节点成本所需记录的信息，我们在这一步进行了宽限制。我们使用一个三维数据，记录了每个时刻，有哪些边缘节点对每类流产生了中心节点的成本，这种记录仅仅需要记录每个边缘节点每个时刻分配的每种流的最大值。然优化调整的时候，如果每个边缘节点内某个流被转移走，并不降低对应其分配的该类流的最大值，仅仅对转移进来数据流，超出对应记录的最大值时，将该值抬高。

训练赛阶段，我们是在倒数第二天才将第一阶段采用窗口式分配的策略写出来，并将排名从第35名提升到了第13名。但是，由于最终版本直到倒数第二天才写出来，后续补充了一些优化，以及更新了第三阶段的优化调整部分，却没来得及提交验证，最终在训练赛结束的时候是第三名。


3.主要困难点与细节问题

1. 缓存计算时的进位问题：在递归计算缓存时，因为题目中要求缓存进位的问题，而我们又不能预知递归时某一层的后续分配流量总值，所以需要在递归的时候预留1的空间。
2. 第一阶段得时间优化问题：计算连续窗口内所连接数据流总量的时候，采用双指针的方法进行处理，是leecode中计算数组连续位置最大和的经典题目；然后在分配完一个窗口之后，在进行重新计算不同窗口覆盖数据流总值的时候，依然采用双指针的方法进行处理，不过是利用双指针的方法进行一定的减法处理，同时利用大顶堆的方案，调整计算新的窗口覆盖最大值。
3. 缓存的多时刻影响问题:我们处理某一边缘节点的某一时刻，不能仅仅只看前一时刻的分配值，因为不仅仅前一时刻的分配值会导致该时刻有一定的缓存，前n个时刻进行分配数据流，都会间接的给当前时刻带来缓存，这是一个很复杂的过程，需要利用递归的方法计算，也就是说，所分析节点的某一时刻的可分配数据流上限，需要先计算前n个时刻造成的缓存，而且n还不是定值，这种分析会大大降低算法效率。

总结

这篇博客是在比完赛之后写的，所以有些细节问题可能记录的不是特别详细，如果有问题可以私聊。

这次比赛有两个印象比较深刻的教训。
一个是linux系统下的开发一定要熟练，我们因为linux和windows下开发的差异在初赛刚开始的阶段被卡了三天，就是因为不清楚linux与windows换行符的差异，导致输入输出一直出错。以后在工作中一定熟练掌握linux和windows下开发的区别，这样才能减少开发周期，让自己在两个环境下都能得心应手。
二是在设计一个算法时，一定要考虑好他的时间复杂度与空间复杂度，有个大概的心理预期，这样能够在出现问题时，及时反应过来问题出在了哪里，比如我们从初赛开始一直沿用的最大白嫖策略，我们需要在整个分配过程中一直维护所有边缘节点的最大需求时刻，这里就选用了堆结构来进行维护，里面还有一些小的细节，比如查找某个时刻在堆数组中的位置，采用了哈希表的数据结构进行存储等。一个好的算法，他在性能上有提升，那么在时间复杂度或者空间复杂度上一定会有所牺牲，所有就要想清楚要用什么样的数据结构去做这件事，如果数据结构用的不好，再好的算法思路，实现不了也是没用的。

写博客的过程也是在回忆整个比赛的过程。3月1日，我在我们三个人去年的比赛群里发了一句，今年软挑，再冲一次得到了两位队友肯定的回答，那真的是我们今年梦开始的地方。

本来我们最初的目标是进入复赛，因为去年只拿到了粤港澳赛区80名的成绩，今年至少要比去年有所进步吧~能一路打怪升级，杀进决赛是我们一开始没有想到的。比赛期间一个月的时间，基本每天都在高压下度过，不断的去想优化的思路，不断的迭代我们的代码。在瓶颈时，我们看着其他队伍的名次不断提高，而我们队伍的名次不断下降，真的是非常沮丧，但是在成绩有重大突破时，那种喜悦的心情也是令人无比难忘，这将会成为我们一辈子的回忆。虽然决赛的成绩差强人意，但是我们早就突破了自我，远超最初的预期。最重要的是，这次比赛，不仅极大程度地锻炼了我的代码能力和算法能力，还增进了我们三人之间的友谊。我们三人去年软挑第一次组队，粤港澳赛区80名；然后7月份的嵌入式软件算法大赛，粤港澳赛区第十名；今年已经成长到软挑粤港澳赛区第四名，总决赛的27名了。这一路走来，我们三人这两年的比赛经历可以说是我上研究生以来最大的收获了，真的非常感谢我的队友，能陪我走完全程，在每次比赛最困难的时候也都没有放弃，感谢你们！

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！