Algebras for weighted search
Algebras for weighted search
复制标题
加权搜索的代数
DOI：
10.1145/3473577
复制
发表时间：
2021
影响因子：
--
通讯作者：
Kidney D
中科院分区：
文献类型：
--
作者：
Kidney D
加权搜索是许多基本和有用算法的重要组成部分。尽管如此，作为一种计算效应，它的研究相对较少，没有受到深度优先或广度优先搜索那么多的关注。本文探讨了加权搜索的代数基础，并演示了如何将其实现为一元变换。发展首先探索了广度优先搜索，它可以表示为半环上的多项式。这些多项式被推广到自由半模一元，以捕捉广泛的应用，包括概率一元，多项式一元，以及加权搜索的一元。最后介绍了一种基于自由半模单模的单模变压器。对此类型应用优化将产生配对堆的实现，然后使用该实现来实现Dijkstra算法和高效的概率抽样。该建筑在立方AGDA中正式确定，并在哈斯克尔实施。
Weighted search is an essential component of many fundamental and useful algorithms. Despite this, it is relatively under explored as a computational effect, receiving not nearly as much attention as either depth- or breadth-first search. This paper explores the algebraic underpinning of weighted search, and demonstrates how to implement it as a monad transformer.The development first explores breadth-first search, which can be expressed as a polynomial over semirings. These polynomials are generalised to the free semimodule monad to capture a wide range of applications, including probability monads, polynomial monads, and monads for weighted search. Finally, a monad transformer based on the free semimodule monad is introduced. Applying optimisations to this type yields an implementation of pairing heaps, which is then used to implement Dijkstra's algorithm and efficient probabilistic sampling. The construction is formalised in Cubical Agda and implemented in Haskell.
登录
查看更多内容
影响因子：
1.8
作者：
Vezzosi, Andrea;Mortberg, Anders;Abel, Andreas
通讯作者：
Abel, Andreas
用于逻辑编程的组合器
DOI：
10.1007/978-1-349-91518-7_9
发表时间：
2003
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
Michael Z. Spivey;Silvija Seres
通讯作者：
Silvija Seres
用于广度优先搜索的组合器
影响因子：
1.1
作者：
Michael Spivey
通讯作者：
Michael Spivey
如何用成功列表替换失败：惰性函数语言中的异常处理、回溯和模式匹配方法
DOI：
10.1007/3-540-15975-4_33
发表时间：
1985
期刊：
J. Funct. Program.
影响因子：
--
作者：
Philip Wadler
通讯作者：
Philip Wadler
单射正序幺半群 I
影响因子：
0.8
作者：
F. Wehrung
通讯作者：
F. Wehrung