Motivated by efforts to incorporate sheaves into networking, we seek to reinterpret pathfinding algorithms in terms of cellular sheaves, using Dijkstra's algorithm as an example. We construct sheaves on a graph with distinguished source and sink vertices, in which paths are represented by sections. The first sheaf is a very general construction that can be applied to other algorithms, while the second is created specifically to capture the decision making of Dijkstra's algorithm. In both cases, Dijkstra's algorithm can be described as a systematic process of extending local sections to global sections. We discuss the relationship between the two sheaves and summarize how other pathfinding algorithms can be interpreted in a similar way. While the sheaves presented here address paths and pathfinding algorithms, we suggest that future work could explore connections to other concepts from graph theory and other networking algorithms. This work was supported by the NASA Internship Project and SCaN Internship Project during the summer of 2020.


翻译:在努力将牛排纳入网络的过程中,我们试图用Dijkstra的算法作为例子,重新解释细胞包状的路径调查算法。我们用不同的源头和水槽脊组成一个图表,其中路径由各部分代表。第一页是可用于其他算法的非常笼统的构造,而第二页则是专门为捕捉Dijkstra的算法的决策而创建的。在这两起案件中,Dijkstra的算法可以被描述为一个系统的过程,将本地部分扩大到全球部分。我们讨论了两页的分类法之间的关系,并总结了其他路径调查算法如何以类似的方式解释。虽然在此展示的分类法是路径和路径调查算法,但我们建议未来的工作可以探索从图形理论和其他网络算法与其他概念的联系。2020年夏天,这项工作得到了美国航天局实习生项目和SCaN Intern Inship Project的支持。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
120+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
计算机 | USENIX Security 2020等国际会议信息5条
Call4Papers
7+阅读 · 2019年4月25日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Parallel Tempering on Optimized Paths
Arxiv
0+阅读 · 2021年2月15日
Arxiv
0+阅读 · 2021年2月12日
Arxiv
0+阅读 · 2021年2月11日
VIP会员
相关VIP内容
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
计算机 | USENIX Security 2020等国际会议信息5条
Call4Papers
7+阅读 · 2019年4月25日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Top
微信扫码咨询专知VIP会员