论文标题
路径优化滑轮
Path Optimization Sheaves
论文作者
论文摘要
通过将束带纳入网络的努力的激励，我们试图以细胞或骨的算法来重新解释途径算法，以Dijkstra的算法为例。我们在具有杰出源和水槽顶点的图表上构建滑轮，其中路径由部分表示。第一个捆绑是一种非常通用的结构，可以应用于其他算法，而第二条则是专门为捕获Dijkstra算法的决策而创建的。在这两种情况下，Dijkstra的算法都可以描述为将本地部分扩展到全球部分的系统过程。我们讨论了两条或骨之间的关系，并总结了如何以类似方式解释其他探路算法。虽然此处介绍的滑绳涉及路径和路径算法，但我们建议未来的工作可以探索图理论和其他网络算法与其他概念的联系。这项工作得到了2020年夏季NASA实习项目和扫描实习项目的支持。
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.
