gpt4 book ai didi

haskell - 首先遍历图的宽度,在Haskell中标记访问的节点

转载 作者:行者123 更新时间:2023-12-02 05:42:29 25 4
gpt4 key购买 nike

所以问题很简单。给定一个图(我希望图的结构在这个问题上没有多大关系),我该如何对其进行BFS?

我最近问了一个有关生成列表的问题,其中每个元素在其末尾附加了许多元素。希望该答案可以让我排队进行BFS所需的队列。但是搜索还有另一个关键组成部分,它会将节点标记为已访问,因此我们不再赘述。这也不需要算法执行的开销。既不标记也不阅读。

由于Haskell不允许我更改状态,我该怎么做?

(我不是在寻找一种将命令性代码转换为Haskell的方法。惯用的Haskell解决方案会很棒。)

最佳答案

如评论中所述,一种正确的方法是将图形与标记其节点分开。您需要使用某种设置的容器。基本上可以采用两种方法:

  • 使用功能集。尽管每次修改都会创建一个新版本,但功能数据结构的设计方式是,实际上只有很小一部分会发生更改,并且原始版本中的大多数会被共享。对于此类结构,插入/查找操作采用O(log n)。但是来自无序容器的HashSet已针对速度进行了优化,对数的底数很大,因此对于大多数目的,该因子就像常数。
  • 使用ST monad(另请参见this question)。在monad内部,您可以使用可变数据结构,而结果仍然是参照透明的。然后,您可以使用例如hashtables包中的ST-based hash tables。这使您可以摆脱log n因子,并在恒定时间内对哈希表进行操作。但是还有其他缺点,例如您的遍历必须是纯遍历的。如果可以在其他monad中使用,则无法将其与ST操作交错。
  • 关于haskell - 首先遍历图的宽度,在Haskell中标记访问的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21074766/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com