2017华为精英挑战赛(2)

历时几天,上交了完整的代码并在测试集更新前挤进了排行榜前32.

具体做法沿用上次提到的遗传算法+最小费用最大流。但是对遗传算法只实现了变异而没有交叉。以服务器的有无决定01序列生成个体,使个体不断变异,并将好的变异结果保存下来覆盖个体。

这从本质上来说是一个非常有局限性的贪心算法。变异相当于试探性的添加加一个服务器或取消一个服务器,如果计算结果较好则变异,否则不变异。几乎100%会进入一个比较差的局部最优解。

然而在测试集更新后居然还能上升到前10,推测很多人的代码在迭代时没有超时判断导致零分。名次现在无关紧要,重要的是如何继续完善遗传算法以及减少寻路时间。

最小费用最大流

在如下一张简单有向图中,红色结点为服务器,绿色节点为用户,边权值为单位带宽的单价,每条边上的总带宽暂不显示。服务器必须传递流量到达用户使用户需求得到满足。

之前走了弯路,寻找到这么一张表格,记录所有服务器到所有用户的流量路径,并每次输出最小路径作为选择(现在假设表中路径满足流量条件。且从上至下,同一服务器的不同路径总花费不断增大,同时后一条路径的选择建立在前一条路径上所有边流量被使用的前提下)

服务器->用户 完整路径
0->2 0->1->2
0->2 0->1->4->5->2
0->2 0->3->4->5->2
0->8 0->1->4->7->8
0->8 0->1->4->5->8
0->8 0->3->4->7->8
6->2 6->3->4->1->2
6->2 6->3->4->5->2
6->2 6->7->4->1->2
6->8 6->7->8

之后不断地在所有路径中找到一条边权最小的边,作为输出路径,满足用户需求,之后减去边上所有已用流量,更新上述表格再次寻找最小权边…直到所有用户得到满足。

n为网络节点数,m为用户节点数,一次DJS+ek为O(n^2),需要在每一轮获得最短边的同时更新表,计算为m*m次,每次要从平均含有m*m条边的表中寻找一条边。这样做的时间复杂度为m^2*(m^2*O(n^2)+m^2),几乎是O(n^6)。在800点的情况下,每进行一次寻路,会花费1s时间。在90s超时的条件下,使用这种做法最多迭代大小为100的种群不到1次(考虑遗传算法种群的生成、变异、交叉、适应度计算)。

之后受到人启发,发现完完全全走了弯路,寻路问题完全可以通过建立超级源点与超级汇点来解决。同样是这张图,将所有服务器连接到一个超级源点,所有用户连到超级汇点,这样问题就变成了单源点->单汇点的最小费用最大流问题。如图

如此一来,只需要更改DJS的起始条件和终止条件,就能在一次寻路算法后找到所有路径,从小权值开始选择,直到满足所有用户需求。复杂度降到了O(n^4)。提交结果参考:

 

接下来的工作,即继续完成遗传算法,考虑交叉方式和参数设定,尝试使用DJS+Heap提高寻路时间。

To be continue…

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

《2017华为精英挑战赛(2)》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.