2017华为软件精英挑战赛总结

article/2025/4/3 12:13:19

1.题目

本次赛题是一个视频服务器的CDN规划问题
赛题包_百度网盘

2.解题思

2.1 思路一 整数规划

主要是要把模型建出来

包含了
0-1变量->是否布置服务器
边变量-> 表示该边所跑的流量

用glpk试过,变量个数太庞大,内存都开不下,解的效果也不好,只能解很小点数的,连28个点的都解不出来;清华大佬,手写了一份高性能整数规划求解器,解的非常好,膜拜了。

建模思路可以参考清华博士大佬的建模思路:
复赛整数规划模型.docx

2.2 思路二 启发式算法 + 最小费用流

2.2.1 启发式算法

可以用遗传,模拟退火等
如果是遗传的话,染色体编码可以按照0,1编码,布置服务器节点的置为1,没有布置服务器节点的置为0;

2.2.1.1 基于遗传算法的改进

修改策略
加快收敛
1)一轮寻找完以后,先排序,对一轮中最优的 20% 选取进行保留,然后再用这20%的与其他的进行交叉,变异
4)在每轮开始的时候,加入几条历史最优的染色体

跳出局部解
1)搜寻多次
一次搜索完以后,选择最好的1-2条,然后再随机生成种群,再次搜索,思路就是改变初始种群
2)退化,陷入局部最优以后,保留几条比较好的,其余的都重新初始化,再搜索 和 改变初始种群 同理

2.2.1.2 非均衡变异

减搜索,从高位开始,把1的变成0,如果费用降低,则保留0;如果费用增大则保留原来的1;
加搜索,从高位开始,把0的变成1,如果费用降低,则保留1;如果蜂拥增大则保留原来的0;

2.2.2 最小费用流

2.2.2.1 最小费用流建模

最小费用流一般用于求解单源点单汇点的问题,和赛题要求还略有不同,需要增加一个超级源点和一个超级汇点,将多源多汇的费用流问题转化为单源单汇费用流问题,最终建出来的模型如上面整数规划图形所示。
约束1:
连接超级源点到每个服务器节点,将无向边转为两条有向边,cost设置为0,带宽上限设为无穷,可以用最大的可能值代替
约束2:
连接每个消费节点到超级汇点,将无向边转为两条有向边,cost设置为0,带宽上限设为消费节点的需求
约束3:
网络节点内部都是互相连接的,将无向边转为两条有向边,cost和带宽上限根据读取的图信息来设置
约束4:
网络节点到消费节点设为双向边,cost按读取的图信息来设置,带宽上限设为消费节点的需求

2.2.2.2 最小费用流入门

概念
原理解析

2.2.2.3 最小费用流 之 增广路

一种是在可行流基础上进行增广,每次按照最小费用增广,直到没有办法再增广则算法结束,求得的就是最小费用最大流;

2.2.2.4 最小费用流 之 费用最小的最大流

在可行流基础上先寻找最大流,找到最大流以后想办法将费用降到最低

2.2.2.5 最小费用流代码实现

2.2.2.5.1 SPFA

SPFA方式源代码


/***************************************************
算法引入:
任何容量网络的最大流流量是唯一且确定的,但是它的最大流f并不是唯一的;
既然最大流f不唯一,因此,如果每条弧上不仅有容量限制,还有费用r;
即每条弧上有一个单位费用的参数,那么在保证最大流的前提下;
还存在一个选择费用最小的最大流问题,即为最小费用最大流问题;算法思想:
寻找最大流的方法是从某个可行流出发,找到关于这个流的一条增广路P;
沿着P调整f,对新的可行流又试图寻找关于它的增广路,循环直至不存在增广路为止;
要求最小费用最大流:
如果f是流量为f1的可行流中费用最小者,而p是关于f的所有增广路中费用最小的增广路;
那么沿着p去调整f,得到可行流_f,就是流量为f1的所有可行流中的费用最小者;
这样当f是最大流时,它也就是所要求的最小费用最大流了;算法内容:
在寻找关于f的最小费用增广路的过程中;
需要构造一个关于f的伴随网络W(f);
把在原网络中寻找关于f的最小费用增广路转换为在伴随网络W(f)中寻找从Vs到Vt的最短路问题;其中伴随网络W(f)构造为:
顶点为原网络中的顶点;
原网络中的每条弧<u,v>变成两个方向相反的弧<u,v>和<v,u>;
在W(f)中每条弧<u,v>的权值为:
if(f(u,v)<c(u,v))W(u,v)=r(u,v);
else if(f(u,v)==c(u,v))W(u,v)=无穷大(可省略);
if(f(u,v)>0)W(v,u)=-r(u,v);
else if(f(u,v)==0)W(v,u)=无穷大(可省略);算法流程:
①开始取f(0)={0};
②一般若在第k-1步得到的最小费用流为f(k-1),则构造伴随网络W(f(k-1));
③在W(f(k-1))中寻找从Vs到Vt的最短路,若不存在则转⑤,存在转④;
④在原网络G中得到相应的增广路P,在P上对f(k-1)进行调整;调整后新的可行流为f(k),转②;
⑤f(k-1)为最小费用最大流,算法完毕;算法测试:
HDU1533,ZOJ2404,POJ2195(Going Home);
题意:
在一个网络地图上,有n个小人和n栋房子;
在每个单位时间内,每个人可以往水平方向或垂直方向移动一步,走到相邻的方格中;
对于每个小人,走一步需支付一美元,直到他走入房子里,且每栋房子只能容纳一个人;
求让n个小人移动到n个不同的房子,求需要支付的最小费用;
****************************************************/#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<queue>
using namespace std;int n,m;
const int N=250;
const int M=10000;
const int MAX=0xffffff;
char

http://chatgpt.dhexx.cn/article/APcIrMUj.shtml

相关文章

2017华为软件精英挑战赛解分析

后经在复赛赛题上测试&#xff0c;效果并不好&#xff0c;只适合部分数据集&#xff0c;并且没有理论支持&#xff0c;放出来只为启发—— 以下方法初中级样例1s以内&#xff0c;高级样例10s内出最优解—— 不随机&#xff0c;无启发式&#xff0c;走优化的方法。采用反馈-迭代…

2021华为软件精英挑战赛(粤港澳赛区复赛第八)

一、序言 总结一下四月份参加的华为软挑赛&#xff0c;距离现在已经结束了四个多月&#xff0c;终于有时间抽空写写总结了&#xff08;小作文&#xff09;&#xff0c;我们是粤港澳赛区的620&619-F3队&#xff0c;第一次参加这次比赛&#xff0c;本想尝试一下&#xff0c;但…

css 给文字加下划线

css给文字加下划线 直接贴代码 span {cursor: pointer;&:hover {color: #40A9FF;text-decoration: underline;}}

Excel批量设置下划线

Excel批量设置下划线 目录 Excel批量设置下划线 1、框选需要设置的单元格内容&#xff0c;鼠标右键选择“设置单元格格式” 2、点击“自定义”在类型框中输入“ *_ ” 点击“确定”自动生成&#xff08;注意这个 *_符号需要将输入法切换为英文输入法&#xff09; 3、完成…

h5下划线怎么设置_怎么给文加下划线?

怎么给文本加下划线&#xff1f;下面本篇文章就给大家介绍一下HTML页面和word文档中给文本加下划线的方法。有一定的参考价值&#xff0c;有需要的朋友可以参考一下&#xff0c;希望对大家有所帮助。 HTML页面中给文本添加下划线 在HTML页面中怎么给文本添加下划线&#xff1f;…

latex输出下划线

第一种&#xff1a; 如果只是在作者的邮箱...输出下划线的话直接使用 \_ 就可以了 ma\_pengsen 输出结果&#xff1a; 第二种&#xff1a; 如果要在下划线上输出东西&#xff0c;那需要 \underline{XXXXXXX} ma\underline{ABCDEFG} 结果&#xff1a;

speedoffice(Word)文字怎么添加下划线

Word里面编辑文字&#xff0c;有时需要添加下划线&#xff0c;那么怎么添加下划线了&#xff1f;以最常用的speedoffice为列。 1、首先&#xff0c;我们用speedoffice打开Word文件&#xff0c;选中需要添加下划线的文字内容&#xff1b; 2、然后&#xff0c;鼠标点击选择“主页…

css里给文字加下划线代码,css给文字加下划线

语法&#xff1a;linear-gradient(direction, color-stop 1, color-stop 2,……) 简单用法&#xff1a;background-image: linear-gradient(red, transparent); 增加角度&#xff0c;linear-gradient(45deg, red, transparent) 加个position&#xff1a;linear-gradient(45deg,…

Word调整文字和下划线的间隔

工作环境(蓝色粗体字为特别注意内容) 1&#xff0c;开发环境&#xff1a;Microsoft word 2007 2&#xff0c;参考文献&#xff1a;https://blog.csdn.net/yiluyangguang1234/article/details/50158381 我们在使用Word编辑文档的时候&#xff0c;遇到有的标题带下划线的&#…

CSS设置下划线与文字间距距离

css的写下划线 text-decoration: underline; 但是这样的样式下划线太靠近文字了 如图 修改方式 border-bottom: 1px solid red;padding-bottom: 8px; 如图

word下划线,间距调大方式

都是下划线&#xff0c;是不是第一个看着更舒服&#xff0c;行间距更大。 下面的就是&#xff1a;我们常用的方式&#xff0c;ctrlu&#xff0c;下划线。 上面的是&#xff1a;连续打一行-&#xff0c;就是------&#xff0c;然后换到下一行&#xff0c;enter时候就出现了一条…

css里给文字加下划线代码,css添加文字下划线样式的方法

css添加文字下划线样式的方法 发布时间&#xff1a;2020-08-31 13:54:27 来源&#xff1a;亿速云 阅读&#xff1a;65 作者&#xff1a;小新 这篇文章将为大家详细讲解有关css添加文字下划线样式的方法&#xff0c;小编觉得挺实用的&#xff0c;因此分享给大家做个参考&#xf…

关于HTML,CSS中某一文字的下划线长度的改变

本人 刚刚入坑前端几个月。对于很多问题看的不是恨透测。前几日&#xff0c;写一个学长交代的小小网页时&#xff0c;遇到了一个问题。前前后后变化了好多次。最后解决了。我想有一些其他的学习者也有可能会遇到这类问题&#xff0c;特分享出来。希望可以帮到大家。 当时中需要…

word下滑线设置

方法一&#xff1a; 选择“文本”——>“选项”——>"高级"——>"为尾部空格添加下划线" step1: step 2: step3: step 4&#xff1a; 方法二&#xff1a; 选中需要添加下划线的部分——>"右键段落“——>"中文版式”——>“…

【CSS】下划线与文字间距,下划线粗细以及下划线颜色的设置

最开始的时候了解下划线的属性是&#xff1a; text-decoration:underline;但是&#xff0c;很遗憾的是&#xff0c;对于设计做的下划线用浏览器默认属性样式很难调整&#xff0c;使用这个属性并不能调整下划线与文字的间距&#xff0c;而且对于下划线的颜色也不好调整&#xf…

Python中函数的返回值

在之前的博客中分别介绍了Python中函数的定义、调用、以及函数的参数等&#xff0c;但是大家有没有发现&#xff1a;我们创建的函数都只是为我们做一些事&#xff0c;做完了就结束。但实际上&#xff0c;有时还需要对事情的结果进行获取。这类似于主管向下级职员下达命令&#…

python return_python 如何获得返回值 return

展开全部 前面两位的方法2113其实和先初始化AA&#xff0c;在调用AA的test()效果是一样5261的&#xff0c;在初4102始化AA()的时候&#xff0c;调用的那次test()的返回1653值已经丢了&#xff0c;比如这样定义&#xff1a;class AA(): def __init__(self): self.count0 sel…

python 自定义函数的返回值

python中自定义的函数&#xff0c;有的有返回值&#xff0c;有的没有返回值&#xff0c;且返回值的类型也需注意。 1、无返回值 例如 list 的 append 操作就是无返回值的&#xff0c;换句话说就是不能进行如下的连续操作&#xff1a; list [] list.append(1).append(2) 2、返…

python中函数的返回值,你了解吗?

函数返回值 1. “返回值”介绍 现实生活中的场景: 我给儿子10块钱&#xff0c;让他给我买包烟。这个例子中&#xff0c;10块钱是我给儿子的&#xff0c;就相当于调用函数时传递到参数&#xff0c;让儿子买烟这个事情最终的目标是&#xff0c;让他把烟给你带回来然后给你对么…

python报错怎么返回_python函数怎么返回值

python函数使用return语句返回“返回值”&#xff0c;可以将其赋给其它变量作其它的用处。所有函数都有返回值&#xff0c;如果没有return语句&#xff0c;会隐式地调用return None作为返回值。 python 函数使用 return 语句返回 "返回值"&#xff0c;可以将其赋给其…