建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
温馨提示

抱歉,您需设置社区昵称后才能参与社区互动!

前往修改
我再想想

2020华为软件精英挑战赛

话题 : 430 成员 : 6437

加入HCSD

线上数据可以不要用完全图凑环数了吗?

288acbf2fe... 2020/5/6 2678

大量答案包含在完全图中会导致的问题:

  1. 算法的运行时间将远低于 IO 所需的时间(算法时间占比在 10% 以下),导致该比赛变成 IOcraft2020。

  2. 无法分辨出算法的优劣,甚至会导致朴素单向 DFS 算法运行速度超过在绝大多数情况下表现更加优秀的双向搜索算法与启发式算法。


关于生成测试数据的一些参考:

  1. 均匀随机图信息熵最大,可以有效分辨出不同算法的优劣。最广受好评的民间数据是 10w 个点,随机连接 200w 条边,边权在取值范围内均匀随机取值,最终答案有 1900w 环。这个图非常有效地提高了算法部分在总运行时间中的占比(典型值为 80%)。

  2. 均匀随机图没有什么特征可言,可以避免选手需要探测数据特征进行过拟合式的优化。

  3. 在随机图的基础上叠加特殊的局部图(例如增加度数较大的点),验证选手开发的程序的正确性。


“道理我都懂,但我们的求解器在均匀随机图上太慢了跑不出标准答案怎么办呢?”:

  1. 联系几个选手,可以用他/她们的代码来跑啊。




from magical girls

回复 (7)

2020/5/8 12:53

回复:goggleman 发表于 2020-5-8 12:24 建议大赛组委会去参考一下具有35亿个顶点和1280亿条边的Hyperlink Web图,甚至可以考虑动态数据集,考察算法对演化图的处理效果

即使这样 IO 仍然会占用绝大部分时间

goggleman
0 0
2020/5/8 12:24

建议大赛组委会去参考一下具有35亿个顶点和1280亿条边的Hyperlink Web图,甚至可以考虑动态数据集,考察算法对演化图的处理效果

2020/5/7 17:53

回复:凌少 发表于 2020-5-7 16:56其实就是完全图占答案的比重太高了

的确。数据包含完全图是没问题的,但不应该让大多数答案在完全图或者非常稠密的图中。否则的话找环的平均难度就太低了。

凌少
0 0
2020/5/7 16:56

其实就是完全图占答案的比重太高了

2020/5/7 16:30


赤耳
0 0
2020/5/7 16:05

++++++

TCOOMIN
0 0
2020/5/7 11:37

捞一捞魔法少女,居然没人回复

上划加载中
标签
您还可以添加5个标签
  • 没有搜索到和“关键字”相关的标签
  • 云产品
  • 解决方案
  • 技术领域
  • 通用技术
  • 平台功能
取消

288acbf2fe6c2f8deb82

角色:成员

话题:3

发消息
发表于2020年05月06日 20:44:46 26787
直达本楼层的链接
楼主
正序浏览 只看该作者
[复赛问题咨询] 线上数据可以不要用完全图凑环数了吗?

大量答案包含在完全图中会导致的问题:

  1. 算法的运行时间将远低于 IO 所需的时间(算法时间占比在 10% 以下),导致该比赛变成 IOcraft2020。

  2. 无法分辨出算法的优劣,甚至会导致朴素单向 DFS 算法运行速度超过在绝大多数情况下表现更加优秀的双向搜索算法与启发式算法。


关于生成测试数据的一些参考:

  1. 均匀随机图信息熵最大,可以有效分辨出不同算法的优劣。最广受好评的民间数据是 10w 个点,随机连接 200w 条边,边权在取值范围内均匀随机取值,最终答案有 1900w 环。这个图非常有效地提高了算法部分在总运行时间中的占比(典型值为 80%)。

  2. 均匀随机图没有什么特征可言,可以避免选手需要探测数据特征进行过拟合式的优化。

  3. 在随机图的基础上叠加特殊的局部图(例如增加度数较大的点),验证选手开发的程序的正确性。


“道理我都懂,但我们的求解器在均匀随机图上太慢了跑不出标准答案怎么办呢?”:

  1. 联系几个选手,可以用他/她们的代码来跑啊。




from magical girls

点赞1 举报
分享

分享文章到朋友圈

分享文章到微博

288acbf2fe6c2f8deb82

角色:成员

话题:3

发消息
发表于2020年05月08日 12:53:35
直达本楼层的链接
8#
只看该作者

回复:goggleman 发表于 2020-5-8 12:24 建议大赛组委会去参考一下具有35亿个顶点和1280亿条边的Hyperlink Web图,甚至可以考虑动态数据集,考察算法对演化图的处理效果

即使这样 IO 仍然会占用绝大部分时间

点赞 评论 引用 举报

goggleman

角色:成员

话题:0

发消息
发表于2020年05月08日 12:24:01
直达本楼层的链接
7#
只看该作者

建议大赛组委会去参考一下具有35亿个顶点和1280亿条边的Hyperlink Web图,甚至可以考虑动态数据集,考察算法对演化图的处理效果

点赞 评论 引用 举报

288acbf2fe6c2f8deb82

角色:成员

话题:3

发消息
发表于2020年05月07日 17:53:06
直达本楼层的链接
6#
只看该作者

回复:凌少 发表于 2020-5-7 16:56其实就是完全图占答案的比重太高了

的确。数据包含完全图是没问题的,但不应该让大多数答案在完全图或者非常稠密的图中。否则的话找环的平均难度就太低了。

点赞 评论 引用 举报

凌少

角色:成员

话题:0

发消息
发表于2020年05月07日 16:56:52
直达本楼层的链接
5#
只看该作者

其实就是完全图占答案的比重太高了

点赞 评论 引用 举报

Codefresher

角色:成员

话题:3

发消息
发表于2020年05月07日 16:30:55
直达本楼层的链接
地板
只看该作者


点赞 评论 引用 举报

赤耳

角色:成员

话题:10

发消息
发表于2020年05月07日 16:05:53
直达本楼层的链接
板凳
只看该作者

++++++

点赞 评论 引用 举报

TCOOMIN

角色:成员

话题:0

发消息
发表于2020年05月07日 11:37:48
直达本楼层的链接
沙发
只看该作者

捞一捞魔法少女,居然没人回复

点赞 评论 引用 举报

游客

您需要登录后才可以回帖 登录 | 立即注册