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

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

前往修改
我再想想

2020华为软件精英挑战赛

话题 : 430 成员 : 6437

加入HCSD

可以基于图特征快速估计算法与 IO 时间比例的数学模型

288acbf2fe... 2020/5/8 2692

定义:搜索效率 = 总答案数 / 搜索算法遍历节点的总次数。(0 < 搜索效率 < 1)


搜索效率可以直接反映出 IO 部分 / 算法部分 的时间比例。由于 IO 部分常数较大,需要将搜索效率乘上一个大常数才能得到实际时间比例。


当搜索效率为 x 时, IO 部分 / 算法部分 的时间比例为 20x 。(魔法少女第一定理)


在均匀随机图上面随机走几步,回到原点的概率是 1/n (n 为图的点数)。也就是说,朴素 DFS 算法在均匀随机图上的搜索效率为 1/n。

利用双向搜索(类似密码学上的 meet in the middle 技巧)可以把搜索效率提升到 1/sqrt(n)。


对应到题目场景,如果在图上随机走 7 步回到原点的概率是 x,那么算法的搜索效率往往可以达到 sqrt(x)。(魔法少女第二定理)


在具有特殊特征的图上,搜索效率将非常高。搜索效率越高,高级算法相对于朴素算法的优势就越小(第二定理),算法部分时间在总运行时间内的占比就会越小(第一定理)。


在完全图上,搜索效率可以直接达到 1;在具有局域性的图上(例如社交图),图的维度为 d 且这个值较小时,搜索效率趋近于 (1/d)^(7/2) 。(魔法少女第三定理)


(注:第三定理中图的维度的定义参考了 Wolfram 的理论物理模型:https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ )(章节:The Dimensionality of Space)

回复 (1)

djdj
0 0
2020/5/10 09:56

搜索过的点都被剪枝了,即使一个完全图搜索到后面也变得稀疏了。所以可以搜索前期先用高级算法,后期用朴素算法?或者说,搜索的图因为剪枝,所以是图动态的,每次搜索前先统计一下要搜索的局部看看是否稀疏。

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

288acbf2fe6c2f8deb82

角色:成员

话题:3

发消息
发表于2020年05月08日 13:39:58 26921
直达本楼层的链接
楼主
正序浏览 只看该作者
[复赛问题咨询] 可以基于图特征快速估计算法与 IO 时间比例的数学模型

定义:搜索效率 = 总答案数 / 搜索算法遍历节点的总次数。(0 < 搜索效率 < 1)


搜索效率可以直接反映出 IO 部分 / 算法部分 的时间比例。由于 IO 部分常数较大,需要将搜索效率乘上一个大常数才能得到实际时间比例。


当搜索效率为 x 时, IO 部分 / 算法部分 的时间比例为 20x 。(魔法少女第一定理)


在均匀随机图上面随机走几步,回到原点的概率是 1/n (n 为图的点数)。也就是说,朴素 DFS 算法在均匀随机图上的搜索效率为 1/n。

利用双向搜索(类似密码学上的 meet in the middle 技巧)可以把搜索效率提升到 1/sqrt(n)。


对应到题目场景,如果在图上随机走 7 步回到原点的概率是 x,那么算法的搜索效率往往可以达到 sqrt(x)。(魔法少女第二定理)


在具有特殊特征的图上,搜索效率将非常高。搜索效率越高,高级算法相对于朴素算法的优势就越小(第二定理),算法部分时间在总运行时间内的占比就会越小(第一定理)。


在完全图上,搜索效率可以直接达到 1;在具有局域性的图上(例如社交图),图的维度为 d 且这个值较小时,搜索效率趋近于 (1/d)^(7/2) 。(魔法少女第三定理)


(注:第三定理中图的维度的定义参考了 Wolfram 的理论物理模型:https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ )(章节:The Dimensionality of Space)

点赞3 举报
分享

分享文章到朋友圈

分享文章到微博

djdj

角色:成员

话题:0

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

搜索过的点都被剪枝了,即使一个完全图搜索到后面也变得稀疏了。所以可以搜索前期先用高级算法,后期用朴素算法?或者说,搜索的图因为剪枝,所以是图动态的,每次搜索前先统计一下要搜索的局部看看是否稀疏。

点赞 评论 引用 举报

游客

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