0

完全公开这是针对算法课的作业，但我不是在找人为我编写任何代码或握住我的手。无论如何，我们必须做 Boggle 游戏。对于那些不知道的人，基本上你会得到一个 Boggle 板并且必须找到尽可能多的单词，考虑到递归的字符串可能性，这可能需要大量时间。

为了减少 OP 时间，我们被鼓励使用我们想尝试的任何算法，并在我们进行过程中“清除”字符串。目前我有一个系统，可以通过将它们存储在字典中来找到所有可能的 3 个字母后缀，如果字符串有 3 个字母但不匹配任何有效的后缀，则停止递归。

进入问题的症结所在，我正在尝试实现 Radix 后缀树，目前它看起来像这样

public static class BoggleRadix
{
    private Node root;

    public BoggleRadix()
    {

    }

    public class Node
    {
        public Node()
        {
           List<Edge> nodeEdges = new List<Edge>() 
           {

           }
        }

    }

    public class Edge
    {
        public String edgeString;
        public Node edgeNode;

        public Edge()
        {

        }
        public Edge(String s, Edge e)
        {
            this.edgeString = s;
            this.edgeNode = e;
        }

    }

}

所以我将指针存储在一个无序列表中，这意味着如果我正在检查后缀，我可以预期，更糟糕的情况是，26 次操作甚至可以找到我需要继续沿着树向下的后缀指针。

有什么方法可以加快插入速度，简化流程吗？是否值得为每个节点在内存中建立一个小字典来检查后缀的第一个字母是否存在？这么小就无所谓了吗？

4

1 回答 1

1

我同意 jimktrains 的建议，即使用数组而不是链表作为后缀。您可以使用 将大写 ASCII 字母转换c为数组索引(int)c - (int)'A'。对我的系统字典的测试表明只有几千个三字母前缀，所以空间使用不应该成为问题。

另一方面，您可以将整个字典存储为确定性非循环有限状态自动机。那么尝试节省空间可能是明智之举。我建议使用位图，而不是无法预测分支的二进制搜索。在每个节点中，有一个字段int bitmap;等于未压缩数组中每个占用索引的按位或（|运算符，具有标识元素0） 。然后，为了测试未压缩索引的存在，检查是否为非零。如果是这样，那么压缩数组的索引是.(1 << i)iibitmap & (1 << i)Integer.bitCount(bitmap & ((1 << i) - 1))

于 2014-09-09T16:10:25.453 回答