0

这是我现在使用 HashMap 实现的方法

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private HashMap<MazeCell, Boolean> visitedCells = new HashMap<MazeCell, Boolean>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (visitedCells.get(cell) == null)
    {
        visitedCells.put(cell, true);
        breadCrumbs.push(cell);
    }       

我正在使用递归算法来查找迷宫结束的步数。在我尝试迈出下一个“步骤”之前,我需要确保我没有去过我要迈出的地方。我觉得除了我去过的地方之外,还有比充满空值的 HashMap 更好的数据结构,但我真的不知道。有谁知道更好的数据结构?

4

4 回答 4

0

HashMap您应该使用HashSet而不是a 。代码会更容易阅读。由于 anHashSet由 an 支持,因此性能是等效的HashMap<E,Object>

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private Set<MazeCell> visitedCells = new HashSet<MazeCell>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (!visitedCells.contains(cell))
    {
        visitedCells.add(cell);
        breadCrumbs.push(cell);
    }   
}

一个HashSet offers constant time performance for the basic operations.

于 2013-03-18T15:13:01.423 回答
0

boolean[][]为整个矩阵设置一个怎么样?

如果您不处理太大的矩阵,我可能会选择这个选项。

1000x1000 不是那么大,整个矩阵将占用大约 1 MB 的存储空间(取决于实现)。

读/写的开销应该小于使用散列。还需要注意的是,如果散列函数不好,散列的性能可能会很糟糕。二维阵列解决方案没有这个缺点。

存储密集度较低的解决方案是BitSet[]1000x1000 矩阵的存储空间约为 125 KB。

请注意,您可以null在任何一种情况下(boolean[]BitSet可以为空)都有值,其中有空行/列(取决于实现)以进一步减少存储空间。

免责声明:以上数字只是估计,我忽略了一些事情。

于 2013-03-18T15:36:53.357 回答
0

目前的设计还可以。如果单元格的数量是固定的,您可以将单元格保存在一个数组中,并使用位向量来表示访问过的单元格。例如,一个 32 位整数可以表示 32 个单元。

于 2013-03-18T15:14:12.933 回答
0

不相交集

这是实现这种数据结构的最有效方式。

简而言之,您所做的是创建一个代表您的迷宫的二维整数数组。数组中的每一行列将是迷宫中的 x,y 坐标。坐标位置上的值将显示它所在的“集合”。

因此,在您的情况下,如果您访问过某个位置,请在该位置放置 1。

因此,如果未访问坐标,它将包含 0。

于 2013-03-18T16:23:42.233 回答