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

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);
            }
        }

letters 是一个 2D 字符数组。

y & x 是整数，显示板

宽度和宽度的位置。 height 也是 int，它告诉板的尺寸

“”是我们试图使（单词）

覆盖的字符串是一个布尔数组，以检查我们是否已经使用了该正方形。

t 是一个列表（其中包含要检查的所有单词）。

需要优化的递归方法：

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 possible 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 分钟才能找到单词。

编辑：我澄清了这些字母 数组是二维的

我想展示我如何让算法运行得非常快。 我使用 @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

其他答案是正确的：您应该完全放弃这个算法并重新开始。

在文字游戏中处理这些问题的方法是将字典转换成适合您想要执行的搜索类型的形式。在你的例子中，你想要构建的数据结构称为trie，这是一个双关语，因为它是一个快速“re-trie-val”的“树”，哈哈哈，那些计算机科学的家伙非常机智！

trie 的工作方式是有一棵树，其中每个节点最多有 27 个子节点。假设您有字典 { AB, ACE, ACT, CAT }。 trie 看起来像这样：

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

其中 $ 表示“单词结束”。从根到 $ 的每条路径都是一个合法的单词。

现在要找到所有单词，首先从字典中构建特里树。然后，对于网格中的每个起点，尝试特里树中的每个可能的单词。如果您从包含 A 的网格方块开始，那么您当然不会向下遍历 trie 的 C 分支。然后，对于特里树中 A 的每个子节点，查看网格是否有一个相邻的正方形可以让您更深入地进入特里树。

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

这一切有意义吗？

Answer 2

设置不变参数（字母、宽度、高度和 tt）字段。不要使用 Linq，它在多次迭代中会很慢。另外，将单词列表更改为更有效的词典或某种类型的排序列表。

Answer 3

从相反的方向攻击可能更有效。迭代可能的单词列表，在网格中查找该单词的第一个字母，如果找到它，则在相邻的方块中查找第二个字母，如果发现它，则继续尝试沿着该行进一步匹配。

通过这种方式，您可以快速完全消除单词，而不是重复检查每个可能位置的每个单词。

仅查看您在将重复数千次 LINQ 的代码中使用的代码可能是一个禁忌。您正在使用字符串操作，因此您在内存中生成数千个字符串，并且可能导致垃圾收集器在递归期间运行，您应该切换到字符串生成器或某种字符数组。

此时您可以进行大量优化，例如，对列表进行快速的第一次检查，检查每个单词的每个字母是否位于网格中的某个位置（只需将网格中的所有字母放入一个字符串中即可轻松完成此操作） ，那么您可以快速消除并非所有字母都在网格中的单词 - 甚至无需担心它们的顺序是否正确。

您可以将网格转换为一系列字符串，每个字符串代表网格的某个方向，然后仅使用纯字符串搜索。如果您找到匹配项，您只需要确保匹配项没有跨越网格边界，这可以通过快速检查匹配项的起点和终点来完成。

Answer 4

我想我可以根据埃里克·利珀特的回答提出代码。埃里克（Eric）做到了，但硬代码总是更好。 ;-)

首先，这是一个 trie 的简单实现：

public class Trie : Dictionary<char, Trie>
{
    public int Frequency { get; set; }

    public void Add(IEnumerable<char> chars)
    {
        if (chars == null) throw new System.ArgumentNullException("chars");
        if (chars.Any())
        {
            var head = chars.First();
            if (!this.ContainsKey(head))
            {
                this.Add(head, new Trie());
            }
            var tail = this.GetSafeTail(head, chars.Skip(1));
            if (tail.Any())
            {
                this[head].Add(tail);
            }
        }
    }

    public bool Contains(IEnumerable<char> chars)
    {
        if (chars == null) throw new System.ArgumentNullException("chars");
        var @return = false;
        if (chars.Any())
        {
            var head = chars.First();
            if (this.ContainsKey(head))
            {
                var tail = this.GetSafeTail(head, chars.Skip(1));
                @return = tail.Any() ? this[head].Contains(tail) : true;
            }
        }
        return @return;
    }

    private IEnumerable<char> GetSafeTail(char head, IEnumerable<char> tail)
    {
        return ((!tail.Any()) && (head != '
此代码允许您将字符串传递到 Add & 包含方法，字符串为IEnumerable。
它可以像这样使用：
var trie = new Trie();
var before = trie.Contains("Hello"); // == false
trie.Add("Hello");
var after = trie.Contains("Hello"); // == true

现在，给定一个字母网格和一个加载了可能单词的特里树，我可以运行以下查询来获取匹配项：
var matches =
    from w in this.GetPossibleWords(letters)
    where trie.Contains(w)
    select w;

 GetPossibleWords 方法的实现如下
public IEnumerable<string> GetPossibleWords(char[,] letters)
{
    return
        from ws in this.GetPossibleWordLists(letters)
        from w in ws
        select w;
}

private IEnumerable<IEnumerable<string>> GetPossibleWordLists(char[,] letters)
{
    Func<int, int> inc = x => x + 1;
    Func<int, int> nop = x => x;
    Func<int, int> dec = x => x - 1;
    for (var r = letters.GetLowerBound(0);
        r <= letters.GetUpperBound(0); r++)
    {
        for (var c = letters.GetLowerBound(1);
            c <= letters.GetUpperBound(1); c++)
        {
            yield return new [] { letters[r, c].ToString(), };
            yield return this.GetPossibleWords(letters, r, c, dec, dec);
            yield return this.GetPossibleWords(letters, r, c, inc, dec);
            yield return this.GetPossibleWords(letters, r, c, nop, dec);
            yield return this.GetPossibleWords(letters, r, c, dec, nop);
            yield return this.GetPossibleWords(letters, r, c, inc, nop);
            yield return this.GetPossibleWords(letters, r, c, nop, inc);
            yield return this.GetPossibleWords(letters, r, c, dec, inc);
            yield return this.GetPossibleWords(letters, r, c, inc, inc);
        }
    }
}

private IEnumerable<string> GetPossibleWords(char[,] letters,
    int r, int c,
    Func<int, int> rd, Func<int, int> cd)
{
    var chars = new List<char>();
    while (r >= letters.GetLowerBound(0) && r <= letters.GetUpperBound(0)
        && c >= letters.GetLowerBound(1) && c <= letters.GetUpperBound(1))
    {
        chars.Add(letters[r, c]);
        if (chars.Count > 1)
        {
            yield return new string(chars.ToArray());
        }
        r = rd(r);
        c = cd(c);
    }
}

：这个解决方案的性能看起来相当不错。
 OP 有一个 4x4 网格，大约需要 120 秒（2 分钟）。我的代码可以在 20.3 秒内匹配 40x40 网格中 208,560 个单词的列表。
不错吧？
再次感谢 Eric 提出使用 trie 的想法。
)) ? new [] { '
此代码允许您将字符串传递到 Add & 包含方法，字符串为IEnumerable。
它可以像这样使用：

现在，给定一个字母网格和一个加载了可能单词的特里树，我可以运行以下查询来获取匹配项：

 GetPossibleWords 方法的实现如下

：这个解决方案的性能看起来相当不错。
 OP 有一个 4x4 网格，大约需要 120 秒（2 分钟）。我的代码可以在 20.3 秒内匹配 40x40 网格中 208,560 个单词的列表。
不错吧？
再次感谢 Eric 提出使用 trie 的想法。
, } : tail;
    }
}

此代码允许您将字符串传递到 Add & 包含方法，字符串为IEnumerable。

它可以像这样使用：

现在，给定一个字母网格和一个加载了可能单词的特里树，我可以运行以下查询来获取匹配项：

GetPossibleWords 方法的实现如下

：这个解决方案的性能看起来相当不错。

OP 有一个 4x4 网格，大约需要 120 秒（2 分钟）。我的代码可以在 20.3 秒内匹配 40x40 网格中 208,560 个单词的列表。

不错吧？

再次感谢 Eric 提出使用 trie 的想法。

Answer 5

1. 使用准备得更好的数据结构。不是使用List来存储所有单词，而是使用一些树状结构。或者至少是排序列表+二分搜索。这一点应该会显着提高性能。我建议使用有序集合并通过递归方法传递范围索引。即，您将查找第一个字母并确定以该字母开头的单词有 123-456 个索引。下次您附加新字母时，您将使该范围变得更加狭窄，并且您无需遍历整个集合！
2. 预过滤您的单词集合。你只有 16 个字母，这意味着少了 10 个以上的字母。您可以过滤单词集合并删除所有缺少数字的单词。
3. 惰性 LINQ。如果您想使用 Linq，则不要强制迭代整个集合（我的意思是不要调用 ToList 方法）。您可以利用它的惰性性质仅进行迭代，直到您需要为止，因为如果该数字大于 2，您并不关心有多少单词以此子词开头。
4. 不要复制 cov。无需每次都复制整个数组，只需设置 cov[x, y] = true; 并在嵌套搜索尝试后放回 false 值：cov[x, y] = false;
5. 使用探查器。 ;-)

Answer 6

一种优化是定向搜索。您只需要对角线向下、向左和左下搜索，而对角向上、向右和右上搜索将得到与简单反转字符串相同的结果。

编辑：

感兴趣的可能还有 Project Euler Problem #11 以及使用 C# 和 LINQ 的解决方案的撰写 此处。

这是我试图描述的一个完全未经测试的例子。

    static List<string> Solve()
{
    // Declaring a empty list of strings to hold our results up front.
    List<string> words = new List<string>();

    // I'm using set as the term for your grid of letters.
    string set = @"ABCD
                   EFGH
                   HIJK
                   LMNO";

    // i'm explicitly defining the dimensions, you need to figure this out.
    int sizeX = 4;
    int sizeY = 4;

    // i'm also specifying a maximum word length. you might find a word like 
    // supercalifragilisticexpialidocious, but i doubt it so lets not waste time.
    int maximumWordSize = 3;

    // first, our trie/wordlist/etc. assume `GetWordList()` gets a list of all
    // valid words with indicated number of characters.
    List<string> wordList = GetWordList(3);

    // second, we load a character array with the set.
    char[,] data = new char[sizeX, sizeY];
    string[] lines = set.Split('\n');
    for (int i = 0; i <= lines.Count() -1; i++)
    {
        string line = lines[i].Trim();
        for (int j = 0; j <= line.Length - 1; j++)
        {
            char[j,i] = lines[j];
        }
    }

    // third, we iterate over the data
    for(int x = 0; x <= sizeX - maximumWordSize; x++)
    {
        for (int y = 0; y <= sizeY - maximumWordSize; y++)
        {
            // check to see if we even have any words starting with our cursor
            var validWords = wordList.Where(w=>w.Contains(data[x,y]));
            if (validWords.Count() > 0)
            {
                // ok, we have words. continue on our quest!
                // (this is where your initial qualifier changes if you use a trie
                // or other search method)

                char[] characters = char[maximumWordSize];

                // search left
                for (int i = x; i <= x + maximumWordSize - 1; i++)
                    characters[i] = data[i, y];
                words.AddRange(Search(characters, wordList));

                // search down
                for (int i = y + maximumWordSize - 1; i <= y; i--)
                    characters[i] = data[x, y];
                words.AddRange(Search(characters, wordList));

                // search diagonal right
                for (int i = x; i <= x + maximumWordSize - 1; i++)
                    for (int j = y + maximumWordSize - 1; j <= y; j--)
                        characters[i] = data[i, j];
                words.AddRange(Search(characters, wordList));

                // search diagonal left
                for (int i = x; i <= x - MaximumWordSize + 1; i++)
                    for (int j = y + maximumWordSize - 1; j <= y; j--)
                        characters[i] = data[i, j];
                words.AddRange(Search(characters, wordList));
            }
        }
    }

    return words;
}

static List<string> Search(char[] Input, List<string> WordList)
{
    List<string> result = new List<string>();
    string word = "";
    // find forwards
    for (int i = 0; i <= Input.Length - 1; i++)
    {
        word += Input[i];
        if (WordList.Contains(word))
            result.Add(word);
    }

    // find backwards
    Array.Reverse(Input);
    for (int i = 0; i <= Input.Length - 1; i++)
    {
        word += Input[i];
        if (WordList.Contains(word))
            result.Add(word);
    }

    return result;
}

Answer 7

另一个优化是数据结构：

List<aWord> t = tt.Where(w => w.word.StartsWith(pass)).ToList();

对于所有有效单词来说，这是 O(n)，您可以通过使用 ie trie 来提高性能。

Answer 8

我不太了解 C#，但这是我在 C++ 中的做法（有些内容是伪代码，以便于阅读）；它应该很容易翻译：

struct word_search {
  const set<string>& words; // This is a balanced search tree
  const vector<vector<char> >& letters;
  const int width, height;
  vector<vector<bool> > marks;
  string word_so_far;

  // Add constructor
  void search(int x, int y) {
    if (x < 0 || x >= width || y < 0 || y >= height || marks[x][y]) return;
    word_so_far += letters[x][y];
    set<string>::const_iterator it = words.lower_bound(word_so_far);
    if (it == words.end() ||
        it->substr(0, word_so_far.size()) != word_so_far) {
      word_so_far.resize(word_so_far.size() - 1);
      return;
    }
    marks[x][y] = true;
    for (int dx = -1; dx <= 1; ++dx)
      for (int dy = -1; dy <= 1; ++dy)
        search(x + dx, y + dy);
    marks[x][y] = false;
    word_so_far.resize(word_so_far.size() - 1);
  }
};

在 C# 中，set 将是 SortedSet，而 vector 将是 SortedSet。 > 类型将是二维数组。不过，我不确定与 lower_bound 的等价物； SortedSet 似乎没有类似的东西。