大量答案包含在完全图中会导致的问题:
算法的运行时间将远低于 IO 所需的时间(算法时间占比在 10% 以下),导致该比赛变成 IOcraft2020。
无法分辨出算法的优劣,甚至会导致朴素单向 DFS 算法运行速度超过在绝大多数情况下表现更加优秀的双向搜索算法与启发式算法。
关于生成测试数据的一些参考:
均匀随机图信息熵最大,可以有效分辨出不同算法的优劣。最广受好评的民间数据是 10w 个点,随机连接 200w 条边,边权在取值范围内均匀随机取值,最终答案有 1900w 环。这个图非常有效地提高了算法部分在总运行时间中的占比(典型值为 80%)。
均匀随机图没有什么特征可言,可以避免选手需要探测数据特征进行过拟合式的优化。
在随机图的基础上叠加特殊的局部图(例如增加度数较大的点),验证选手开发的程序的正确性。
“道理我都懂,但我们的求解器在均匀随机图上太慢了跑不出标准答案怎么办呢?”:
联系几个选手,可以用他/她们的代码来跑啊。
from magical girls



即使这样 IO 仍然会占用绝大部分时间
建议大赛组委会去参考一下具有35亿个顶点和1280亿条边的Hyperlink Web图,甚至可以考虑动态数据集,考察算法对演化图的处理效果
的确。数据包含完全图是没问题的,但不应该让大多数答案在完全图或者非常稠密的图中。否则的话找环的平均难度就太低了。
其实就是完全图占答案的比重太高了
顶
++++++
捞一捞魔法少女,居然没人回复