本次比赛时间精力有限,采用的算法简单,成绩不是很理想。
先来简单分析一下题目,本次比赛在一张拓扑图中,需要满足带宽的限制,为每一个请求安排一条路径连接起点到终点,计算出该路径成本,寻找总成本最优的结果。
首先,刚开始被比赛方带偏了,比赛方给出的请求的参考路径其实没什么用,仅仅使用这些路径数据分配,测试用例的总成本较优解也就500多w。
要想有效的降低成本结果,需要摒弃输入中提供的路径,所有路径都由自己去分配。
首先我想到的可能是用迪杰斯特拉算法等,逐一的找寻最优路径,再交换顺序重新分配。
又或者是每次随机的选择路径,分配完成后,再随机的对一条路径进行优化,最后一点一点的逼近最优解。
但是经过测试之后,发现效果都不好。因为比赛要求1分钟完成计算解题,而搜索路径是极为耗时的操作,因而收敛慢,效果差。
采用的策略
经过测试,我采用的策略是,一次Floyd计算最短路径,再修改分配的先后顺序,将路径按成本从小到大,先后的放入网络中,如果请求路径带宽超出限制,则不放。将所有能放下的放入后,对于剩余的请求,按照第一次的floyd路径的初始拟放置成本从小到大的顺序,依次计算迪杰斯特拉最短路径,并放入网络中,更新网络(主要是带宽信息),继续布置下一个,直到最终所有请求都完成布置,该方法测试用例能达到412w。
1