我该如何优化这种递归方法

Question

我正在尝试制作一个单词拼图游戏,为此我正在使用递归方法来查找给定字母中的所有可能单词.这些字母是4x4板.

像这样:

ABCD
EFGH
HIJK
LMNO

在这个循环中调用递归方法:

for (int y = 0; y < width; y++)
        {
            for (int x = 0; x < height; x++)
            {
                myScabble.Search(letters, y, x, width, height, "", covered, t);
            }
        }

字母是字符的二维数组.

y&x是显示董事会中的位置的整数

width和height也是int,它表示电路板的尺寸

""是我们试图制作的字符串(单词)

覆盖是一系列bools,以检查我们是否已经使用该方块.

t是一个List(包含要检查的所有单词).

需要优化的递归方法:

public void Search(char[,] letters, int y, int x, int width, int height, string build, bool[,] covered, List<aWord> tt)
    {
        // Dont get outside the bounds
        if (y >= width || y < 0 || x >= height || x < 0)
        {
            return;
        }

        // Dont deal with allrady covered squares
        if (covered[x, y])
        {
            return;
        }

        // Get Letter
        char letter = letters[x, y];

        // Append
        string pass = build + letter;

        // check if its a possibel word
        //List<aWord> t = myWords.aWord.Where(w => w.word.StartsWith(pass)).ToList();
        List<aWord> t = tt.Where(w => w.word.StartsWith(pass)).ToList();
        // check if the list is emphty
        if (t.Count < 10 && t.Count != 0)
        {
            //stop point
        }
        if (t.Count == 0)
        {
            return;
        }
        // Check if its a complete word.
        if (t[0].word == pass)
        {
            //check if its allrdy present in the _found dictinary

            if (!_found.ContainsKey(pass))
            {
                //if not add the word to the dictionary
                _found.Add(pass, true);
            }

        }
        // Check to see if there is more than 1 more that matches string pass 
        // ie. are there more words to find.
        if (t.Count > 1)
        {
            // make a copy of the covered array
            bool[,] cov = new bool[height, width];
            for (int i = 0; i < width; i++)
            {
                for (int a = 0; a < height; a++)
                {
                    cov[a, i] = covered[a, i];
                }
            }
            // Set the current square as covered.
            cov[x, y] = true;

            // Continue in all 8 directions.
            Search(letters, y + 1, x, width, height, pass, cov, t);
            Search(letters, y, x + 1, width, height, pass, cov, t);
            Search(letters, y + 1, x + 1, width, height, pass, cov, t);
            Search(letters, y - 1, x, width, height, pass, cov, t);
            Search(letters, y, x - 1, width, height, pass, cov, t);
            Search(letters, y - 1, x - 1, width, height, pass, cov, t);
            Search(letters, y - 1, x + 1, width, height, pass, cov, t);
            Search(letters, y + 1, x - 1, width, height, pass, cov, t);

        }


    }

代码的工作方式与我预期的相同,但速度非常慢..查找单词大约需要2分钟.

编辑:我澄清了字母数组是2D

我想告诉我如何让算法快速工作.我使用@Enigmativity实现的Trie,使用@EricLippert描述的搜索模式

public void SearchWord(char[,] letters, Trie parentTrie, char[] build, int x, int y, bool[,] covered )
    {
        char[] pass = new char[build.Length + 1];
        build.CopyTo(pass, 0);

        // iterate through all squares in the board.
        for (var r = 0; r < letters.GetLength(0); r++ )
        {
            for (var c = 0; c < letters.GetLength(1); c++)
            {
                //check if this square is naighbor to the last square
                if ((IsNeighbor(x, y, r, c)|| x == -1) && !(covered[r, c]))
                {
                    // check if the current Trie contains the letter
                    if (parentTrie.ContainsKey(letters[r,c]))
                    {
                        pass[build.Length] = letters[r, c];
                        covered[r, c] = true;
                        SearchWord(letters, parentTrie[letters[r, c]], pass, r, c, covered);
                        covered[r, c] = false;
                    }
                    if (parentTrie.ContainsKey('$') && (!myStrings.Contains(new string(build).ToLower())))
                        myStrings.Add(new string(build).ToLower());
                }
            }
        }
    }

它最初被称为:

SearchWord(letters, trie, new char[0], -1, -1, new bool[letters.GetLength(0), letters.GetLength(1)]);

我意识到我可以添加字母作为属性,但由于它是一个引用类型,它不是非常昂贵的时间

Answer 1

其他答案是正确的:你应该完全放弃这个算法并重新开始.

在文字游戏中处理这些问题的方法是将字典转换为适合您想要进行的搜索的形式.在你的情况,你想建立的数据结构被称为线索,这是一个双关语,因为它是一个"树",做快"重新特里-VAL",哈哈哈,这些计算机科学家伙都非常诙谐!

trie的工作方式是你有一棵树,每个节点最多有27个孩子.假设你有字典{AB,ACE,ACT,CAT}.trie看起来像这样:

         root
      /        \
     A          C
    / \         |
   B   C        A
   |  / \       |
   $ E   T      T
     |   |      |
     $   $      $

其中$表示"单词已结束".从根到$的每条路径都是合法的.

现在找到所有单词,首先从字典中构建trie.然后对于网格中的每个起始点,尝试trie中的每个可能的单词.如果你从一个包含A的网格方块开始,那么你当然不会遍历trie的C分支.然后对于特里的A中的每个孩子,看看网格是否有一个相邻的方格,可以让你更深入到特里.

这是一个有趣的递归算法,你会发现它非常快,因为你可以非常聪明地放弃从给定方块开始不可能存在的大量单词.

这一切都有意义吗？