4 Mar 2017

华为

link

本次赛题基本描述

在给定结构的G省电信网络中，为了视频内容快速低成本的传送到每个住户小区，需要在这个给定网络结构中选择一些网络节点附近放置视频内容存储服务器。需要解决的问题是：在满足所有的住户小区视频播放需求的基本前提下，如何选择视频内容存储服务器放置位置，使得成本最小。

通用性描述：

  • 网络结构模型： 无向图，无孤立点，每条边有两个方向的权重分别代表两个方向的总带宽,但这两个权重值相等。每条链路的单位租用费均不同。

  • 消费节点：需要满足不同节点的消费需求
  • 视频内容服务器：输出能力没有上限，可以服务多个消费节点， 一个消费节点也可以从多个服务器获取视频流，部署费用300k/台。
  • 消费节点与连接的网络节点之间的链路总带宽无限大，并且网络租用费为零。

比赛内容：

寻找视频内容服务器部署方案：
从网络结构模型中选择一部分网络节点，在其上/附近 一对一 地部署服务器，视频内容服务器与对应的这个节点直连，与对应的这个网络节点之间的通信 没有带宽限制、也没有通信成本。 提供的部署方案需要使得视频流从视频内容服务器经过一些网络节点和链路到达消费节点，并 满足所有消费节点的视频带宽消耗需求。
在满足所有消费节点视频带宽消耗需求的前提下，使得 耗费的总成本（视频内容服务器部署成本+带宽租用成本）最低。 部署方案不仅需要包括部署 视频内容服务器的节点位置，而且还要包括每个消费节点与所有视频内容服务器之间的网络路径以及路径上占用的带宽。

思路一：最小费用流

看起来是一个多源(最多n个)多汇点的最小费用流问题， 源点即为部署服务器的结点，汇点为消费者结点，求解过程如下：

  1. 因为可能存在多个源点，所以建立一个超级源点s’，连接到图中的每一个非消费者结点，最大流量和费用为(无穷或sys.maxint,deploy_price);
  2. 建立一个超级汇点t’，由每个汇点连接到它，最大流量和费用为（每个消费者需要的流量，0)；
  3. 对新建立的图，求s’到t’的最小费用流：
    1. 求出发点到收点的最小费用通路u(s’,t’);
    2. 对该通路分配最大的可能流量f，并让通路上的所有边容量减少f,对于饱和边，设置其费用为无穷大。
    3. 重复1, 2直到不存在可增广路径。 因为每个服务器的deploy_price相同，所以每个结点都可能成为源点，而每一次增广流量，都需要重新求一次最小费用通路,循环次数过多。

有人在交流群中提到一种边的松弛技术。？？

实现 定义一个邻接表(由二维数组来实现)来表示无边图：for G(V,E) define ArrayList [n+2] = [s',n0,n1,...,n-1,t'],每个数组元素存储的是一个关于它邻接点信息的数组。 While( flowin(t') <= Needed(t')) { minCostRoad(s',t'); addFlow(s',t'); //deleteEdge,minusEdgeC }

这个方法似乎不能找出服务器的位置。只能求出最小费用，因为它不会记录走过的边。

整数规划

整数规划目前没有一般的多项式时间解法。 (分枝定界法) 解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。现今比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。

  1. Formulate the Generalized Load balancing problem as a linear program with restrictions on the variable values.

其他参考信息：
算法资料：问题属于设施选址问题，
先建立整数规划模型， 然后再采用启发式的寻优算法， 例如退火算法， 粒子群算法， 遗传算法， 考虑算法的复杂性以避免超时。

建立整数规划模型：
min z = p∑Xi+∑∑ZijfijCostij,
s.t.
{ }

使用遗传算法:
上层算法设计：

  1. 标定决策变量的初始种群Zt,Zt为种群中的第t个候选解， 设定群体进化代数;
  2. 给定风险因子segema，惩罚因子N>=0， 以及允许的最大偏差Dmax > 0;
  3. 候选解Zt在收到下城九三结果:
Tags:
Stats: