初赛做题指导文档（含伪代码）v1.21
需积分: 0 166 浏览量
2022-08-08
22:30:59
上传
评论
收藏 20KB DOCX 举报
初赛做题指导文档（含伪代码）
前言：为了使得参赛者更好地上手解决赛题，这里给出一个简单的、基本的解题思
路，但注意本文档给出的解题办法只是初级的（得分可能较低），并非最优的算法，只能
算是抛砖引玉，请各位参赛者务必寻找更好的解题办法并自己实现。
首先来看一下初赛赛题，题干要求根据用户对虚拟机的请求数据进行预测，然后再根
据预测结果，考虑应该部署多少台物理服务器，以及怎么把预测出来的虚拟机放置到每台
物理服务器上。抽象来讲，这个过程包含两个阶段：即基于虚拟机请求的预测阶段和虚拟
机的放置阶段。预测阶段属于机器学习的拟合问题，而逻辑回归是解决这类问题最基本也
是做常用的办法。下面先来介绍一种简单的线性回归模型。
（一）预测阶段：通过对历史数据的初步分析，我们可以假设需要预测时间段的虚拟
机数量与前面若干个时刻的虚拟机分布是相关的。形式化表示为：对于某种虚拟机规格
𝑓
，由于任何下一个时刻
𝑡
的虚拟机数量都与前
𝑛
个时刻的虚拟机数量相关，设相关权重
分别为
𝑤
1
,
𝑤
2
,……,
𝑤
𝑛
，通常时间越接近的数据相关权重，时间越远的数据权重越小。使用
S
𝑡
表示每个时刻的虚拟机数量，那么要预测虚拟机规格
𝑓
在
𝑡
时刻的数量模型为：
𝑆
𝑓
𝑡
=
𝑤
1
𝑆
𝑓
𝑡
―
1
+
𝑤
2
𝑆
𝑓
𝑡
―
2
+
…
+
𝑤
𝑛
𝑆
𝑓
𝑡
―
𝑛
公式（1）
伪代码如下（Logistic）：
对每个虚拟机规格
𝑓
根据训练数据集确定相关权重系数大小
𝑤
1
,
𝑤
2
,……,
𝑤
𝑛
代入公式（1），求出虚拟机规格
𝑓
在时刻 t 的数量
𝑆
𝑓
𝑡
综合每种规格的虚拟机在
𝑡
时刻的数量
𝑁
𝑡
=
∑
f
𝑆
𝑓
𝑡
根据题干，设计完预测模型，得到虚拟机预测结果，我们需要把这些都放在物理服务
器上，这是“装箱问题”，也是“背包问题”。直观上来讲，先放“西瓜”，后放“芝
麻”，效果更好，同时放置的时候尽可能“避免浪费”，也就是说我们可以“贪心”地
评论0
最新资源