95计费版赛题 赛题分析+代码

95计费版赛题 赛题分析+代码

1.1 描述

1.2 术语解释

1.3 数学描述

1.3.1 约束

1.4 目标

2.1 简单总结题目

节点可以分为边缘节点和客户节点，边缘节点的各个时刻的分配流量的从小到大排序的前95%作为成本

显然，每个节点的后5%是可以白嫖的，因此需要增加白嫖的流量

题目为组合优化问题

2.1.1 组合优化问题

一、定义

在离散的状态空间中，求得极值的优化问题

二、常见的组合优化问题

• 旅行商 TSP
• 背包
• 车辆路径问题
• 车间作业调度问题
• 最小顶点覆盖问题

三、两种求解方法

• 精确求解
  • 搜索
  • 分枝定界
  • 动态规划 DP
• 近似求解
  • 近似算法
    • 贪心
    • 局部优化搜索
    • 线性规划
    • 松弛算法
  • 启发式算法
    • 模拟退火
    • 禁忌搜索
    • 遗传算法
    • 粒子群，蚁群

2.1.2 可行解：线性规划/最大流

线性规划：

将每个边缘节点的流量看作变量，如1号连接abc三个点，则约束为x_1a+x_2b+x_3c ≤ c₁

同时，1，2，3三个节点都为a点提供带宽，则约束为 x_1a + x_2a + x_3a ≥ D_i^t

利用线性规划工具求解即可

优缺点：

• 效率较高

• 只能保证求出可行解！

• 可操作性低

最大流：

超级源点连接所有客户节点，流量上限为客户节点需求的流量

所有边缘节点连接超级汇点，流量上限为inf

优缺点：

• 效率较低
• 可操作性强
  • 退流
  • 降权（类似hlpp算法的relabel）

最终选择此方案，进行组合优化

2.2 优化之路

引入近似求解，两个思路

• 可行解 + 流量迁移
• 预分配 + 剩余分配

2.2.1 可行解思路

这里用遗传算法进行举例：

• 编码解码：

先用2.1.2中的手段求出一组可行解，对于可行解进行二进制编码（作为基因）

可以将每个节点分配流量的二进制进行直接拼接（固定位数）作为基因，这种编码方式便于编码+解码

• 适应度函数：

用总共花费的成本（即最终计算的答案）作为适应度函数

• 进化/变异

较为简单，需要调整参数

优缺点：

• 基因过长，数据量较大时需要考虑使用 bitset
• 需要调整参数

2.2.2 预分配思路

模拟现实中流量的分配情况，高带宽需求的数据都集中在某段时间

• 预分配

按照 **边缘节点最大带宽从大到小排序 ** 选择边缘节点

按照 能吸收最大流量的时刻 选择白嫖的 5 % 的时刻，之后遍历客户需求，尽可能达到带宽上限

• 分配

将未分配的流量需求按照 尽量填满，优先使用免费空间最大的，使得成本最小 的贪心思路分配

• 重分配（迁移）

统计边缘y在时刻k下的使用量，从小到大排序找出找出各边缘95%位置处的带宽成本。统计当前时刻k下每个边缘的95%位置处的使用带宽量，寻找用于再分配的边缘。