526互联

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

发布时间 2023-05-05 19:58:07作者: ZzTzZ

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

1.1 描述

image

1.2 术语解释

image

1.3 数学描述

image

1.3.1 约束

image

1.4 目标

image

2.1 简单总结题目

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

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

题目为组合优化问题

2.1.1 组合优化问题

一、定义

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

二、常见的组合优化问题

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

三、两种求解方法

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

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

线性规划：

将每个边缘节点的流量看作变量，如1号连接abc三个点，则约束为x1a+x2b+x3c ≤ c1

同时，1，2，3三个节点都为a点提供带宽，则约束为 x1a + x2a + x3a ≥ Dit

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

优缺点：

  • 效率较高

  • 只能保证求出可行解！

  • 可操作性低

最大流：

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

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

优缺点：

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

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

2.2 优化之路

引入近似求解，两个思路

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

2.2.1 可行解思路

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

  • 编码解码：

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

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

  • 适应度函数：

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

  • 进化/变异

较为简单，需要调整参数

优缺点：

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

2.2.2 预分配思路

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

  • 预分配

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

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

  • 分配

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

  • 重分配（迁移）

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