algorithm - 用于处理由邻居列表函数定义的(可能是无限的)图的库

Question

这是我在各种编程语言中无数次使用的模式:

1. 遇到一个可以很容易地简化为某种图形算法的问题。
2. 定义邻接函数:outEdges::MyNode -> [MyNode]。
3. 编写上述图算法的一些通用形式，将此函数作为其第一个参数。

例如，考虑这种(故意低效)方法来计算两个词之间的编辑距离。我们将计算通过广度优先搜索将一个词转换为另一个词所需的最少插入和删除次数。

import Data.List
import Data.Maybe

alphabet :: String
alphabet = ['a'..'z']

wordNeighbors :: String -> [String]
wordNeighbors word = deletions ++ insertions where
    insertions = [pre++[c]++suf | (pre,suf) <- splits, c <- alphabet]
    deletions =  [pre++suf      | (pre,_:suf) <- take (length word) splits]

    splits = zip (inits word) (tails word)

shortestDistance :: (Eq a,Hashable a)=> (a -> [a]) -> a -> a -> Maybe Int
shortestDistance edgeFunc source target =
    -- 8 lines of code where I do a breadth-first traversal,
    -- using a HashSet to track previously visited nodes;
    -- yawn...

editDistance :: String -> String -> Int
editDistance a b = fromJust $ shortestDistance wordNeighbors a b

main = print $ editDistance "cat" "can"  -- prints 2

问题是，我对第 3 步感到非常厌倦。(请参阅上面的 shortestDistance...)

我觉得我已经编写了数百次相同的算法。如果我能以某种方式利用 FGL 或 Data.Graph 并完成它，我会很高兴，但到目前为止正如我所知，两者最终都需要构建某种 Graph 数据结构，该结构对所有节点的集合都是严格的。这是一个问题，因为在许多问题中，图形是无限的(例如上面的示例)。

我特别询问了 Haskell，因为 Haskell 非常关注组合子，以至于我以某种方式期望这些算法中的许多已经存在于某个地方。

---

附录:除了最短路径之外，还有我经常写的其他函数示例:

-- Useful for organizing the computation of a recursively-defined
-- property of the nodes in an acyclic graph, such as nimbers.
dfsPostOrder :: (v -> [v]) -> v -> [v]
dfsPostOrder adjFunc root = ...

-- Find all nodes connected in some manner to the root node.
-- In case I know the components are finite size, but am not sure
-- of a nice way to express their contents.
-- (Note: The API below is only good for undirected graphs)
getComponent :: (v -> [v]) -> v -> Set v
getComponent adjFunc root = ...

-- Lazily organize the graph into groups by their minimum distance
-- to any of the nodes in @roots@.
-- One could use this to help incrementalize parts of e.g. a Game
-- of Life or Kinetic Monte Carlo simulation by locating regions
-- invalidated by changes in the state.
groupsByProximity :: (v -> [v]) -> Set v -> [Set v]
groupsByProximity adjFunc roots = ...

---

TL;DR:是否有任何通用的方法来编写适用于潜在无限、潜在循环、有向图的算法——例如由邻接函数定义的算法(节点 -> [Node] 或 Node -> [(Node, Weight)])?

Answer 1

我认为大多数“广度优先”搜索算法实际上是某种 "best-first" algorithm .也就是说，搜索边界放在一个优先队列中这决定了访问节点的顺序。

我找到了两个实现通用最佳优先算法的包:

• astar
• monad-dijkstra

这两个模块都有非常通用的接口(interface)——即你提供一个邻居函数，节点间距离函数和(在 A-star 的情况下)启发式功能。

有了适当的启发式和距离功能，您可能可以映射您对其中一种算法的搜索。例如，this patent描述了一种聘用 A-star 的方法解决编辑距离问题。