2018 年中兴迪杰斯特拉算法挑战赛受到美国制裁的影响被迫终止,官网也已关闭。该比赛的任务是在给定网格中填充 1000 条链路,每条链路有三种选择,目标是在一分钟内尽可能降低网格的最大链路利用率。
一种优化方案是从第一条链路开始,每次选择使得当前网格最大链路带宽利用率最小的链路,直到填充完所有链路。该方案得到的利用率约为 40。在此基础上,可以采用模拟退火算法进行优化,每次退火改变一条链路的选择,替换为另外两种选择之一。由于每次只改变一条链路,因此只需计算一次网格利用率,大幅减少了计算量,在相同时间内可以进行更多次的退火操作。通过调整模拟退火参数,最终可以将网格最大链路带宽利用率降低到 37.19 左右,在一分钟内逼近了工具测试得到的 37.08 左右的最优解。