在搜索时保持先前访问过的状态的记录 [英] Keep record of previously visited states when searching

问题描述

我正在编写几个搜索函数，为此我使用 Node 数据类型：

  data节点a = 
节点{[...] 
，getPath :: [a]  -  ^先前状态此节点已访问
} 
  

该字段 getPath ，用于检查我是否先前在那个节点上访问过那个状态：​​当扩展一个新节点时，我通过下面的方法来检查：

  visited =`elem`路径
  

它可以工作，但是当扩展了很多节点并且路径变为非常昂贵时太长。有没有更好的方式来跟踪我所访问的州？也许一个不同的数据结构（而不​​是一个列表），执行更好的用途？ 解决方案

答案取决于你的约束元素有（或可以给出）。

如果你的元素有一个 Ord 约束，那么你可以使用 Data.Set c> O（log n）成员测试。

一个 Hashable 约束，那么你可以使用 HashSet 从无序容器中获取 O（log n）具有更好的常数因子的会员资格测试*和足够大的基数，以便大多数用例有效地保持恒定的时间。

如果元素只有一个 Eq 约束条件，那么你不可能比列表做得更好。

---

*根据性能 Hashable 实例。如有疑问，请参考基准。

I am programming several search functions, for which I use the Node datatype:

data Node a =
  Node { [...]
       , getPath :: [a]    -- ^ Previous states this node has visited
       }

That field, getPath, is what I use to check if I have previously visited that state in that node: when expanding a new node, I check that by doing:

visited = `elem` path

It works, but it becomes incredibly costly when there are a lot of nodes expanded and the paths become too long. Is there a better way to keep track of the states I have visited? Maybe a different data structure (instead of a list) that performs better for this use?

解决方案

The answer depends on what constraints your elements have (or can be given).

If your elements have an Ord constraint then you can use Data.Set from containers to get O(log n) membership tests.

If your elements have a Hashable constraint then you can use a HashSet from unordered-containers to get O(log n) membership tests with better constant factors* and a large enough base that they are effectively constant time for most use cases.

If your elements only have an Eq constraint then you can't do better than a list.

---

* Depending on the performance of the Hashable instance. When in doubt, benchmark.

这篇关于在搜索时保持先前访问过的状态的记录的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！