优化一个单词查找游戏的最坏情况

Question

考虑以下内容：

a c p r c 
x s o p c 
v o v n i 
w g f m n 
q a t i t

如果在方块中，一个字母 i_index 在任意一个以下位置与另一个字母 j_index 相邻，即 i_index 与 j_index 在下列位置相邻:

* * *
* x *
* * *

这里的*表示与x相邻的位置。

任务是在方格图中查找给定字符串。条件是给定字符串中的所有字符应该是相邻的，并且方格图中的任何一个字符都不能重复使用以构建给定字符串。

我提出了一个简单的回溯解决方案，解决方案非常快，但最坏情况时间确实很糟糕。

例如：假设方格图是4x4，填满了所有的a，因此有16个a，要查找的字符串是aaaaaaaaaaaaaaab，即15个a和一个b。其中一种方法是消除不在方格图中出现的字符的字符串。但是最坏情况仍然可能出现，例如方格图是abababababababab，要查找的字符串是abababababababbb。

我的尝试如下： https://ideone.com/alUPf:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 5

int sp (char mat[MAX][MAX], char *pat, int c, int i, int j)
{
  int r = 0;
  char temp;


  if (c == strlen (pat))
    return 1;
  if (((i<0) || (j<0)) || (i>=MAX) || (j>=MAX))
        return 0;
  if (mat[i][j] != pat[c])
    return 0;
  if (isupper (mat[i][j]))
    return 0;


  /* Save character and mark location to indicate
   * DFS has visited this node, to stop other branches
   * to enter here and cross over path
   */
  temp = mat[i][j];
  mat[i][j] = 0;

  r |= sp (mat, pat, c+1, i-1, j-1);
  r |= sp (mat, pat, c+1, i-1, j);
  r |= sp (mat, pat, c+1, i-1, j+1);
  r |= sp (mat, pat, c+1, i, j+1);
  r |= sp (mat, pat, c+1, i+1, j+1);
  r |= sp (mat, pat, c+1, i+1, j);
  r |= sp (mat, pat, c+1, i+1, j-1);
  r |= sp (mat, pat, c+1, i, j-1);

  /* restore value */
  mat[i][j] = temp;

  /* mark if success */
  if ((mat[i][j] == pat[c]) && (r == 1))
    mat[i][j] = toupper (mat[i][j]);

  return r;
}

/* Testing the `sp` module */
int main (void)
{
  char mat[MAX][MAX] = {
                     {'a', 'c', 'p', 'r', 'c'},
                     {'x', 's', 'o', 'p', 'c'},
                     {'v', 'o', 'v', 'n', 'i'},
                     {'w', 'g', 'f', 'm', 'n'},
                     {'q', 'a', 't', 'i', 't'}
                   };
  char pat[] = "microsoft";
  int i, j;

  for (i=0; i<5; i++)
  {
    for (j=0; j<5; j++)
      printf ("%c ", mat[i][j]);
    printf ("\n");
  }

  for (i=0; i<5; i++)
    for (j=0; j<5; j++)
      sp (mat, pat, 0, i, j);

  printf ("\n\n\n");
  for (i=0; i<5; i++)
  {
    for (j=0; j<5; j++)
    {
      if (isupper (mat[i][j]))
        printf ("%c ", mat[i][j]);
      else
        printf (". ");
    }
    printf ("\n");
  }
  printf ("\n");
  return 0;
}

这将输出:

a c p r c 
x s o p c 
v o v n i 
w g f m n 
q a t i t 



. . . R . 
. S O . C 
. O . . I 
. . F M . 
. . T . . 

函数sp执行工作，执行回溯。

是否有更好的方法？或者能否降低最坏情况下的时间？

- phoxis

---

@Chris：我认为经过编辑现在更好了。 - phoxis

@Bart Kiers：感谢修改。 - phoxis

Answer 1

没有多项式算法，因此我认为你不可能得到更好的结果...

使用字母矩阵可以对任何网格图（具有度数≤4的平面图）进行编码。以下是一个网格图示例：

0-0-0
| | |
0 0-0
| | 
0-0-0

可以通过将边缘转化为'a'，将顶点转化为'b'，将空白空间转化为'z'来进行转换。

B a B a B  
a z a z a  
B z B a B  
a z a z z  
B a B a B 

在原始图中寻找哈密顿路径等同于搜索字符串BaBaBaBaBaBaBaBaB（所有9个B）。但是，对于网格的哈密顿路径问题是NP完全的，因此单词搜索问题是NP难的。

由于单词路径显然是一个多项式证书，矩阵上的单词搜索问题是NP完全的。

---

我记得之前看到过这个证明，维基百科 也证实了，但没有链接到参考文献 >:/

---

我相信这个问题还有更多的解决方案。我只是凭空想出了这个证明，而且我相信我们不是第一个研究这个问题的人。至少，在真正的杂志谜题中，你会得到一些非退化情况的好启发式方法...

- hugomg

---

没注意到汉密尔顿先生藏在这个谜题里。这会帮助我更深入地了解它。感谢图模型。是的，我们肯定不是第一个，让我们看看。 - phoxis

Answer 2

一个简单的改进是在每次调用sp后检查r的值。如果r == 1，则停止调用sp。你找到了解决方案。除非你需要找到所有可能的解决方案。

类似这样（逻辑或运算符不计算第二个操作数，如果第一个为真）：

r = sp (mat, pat, c+1, i-1, j-1)) ||
  sp (mat, pat, c+1, i-1, j) ||
  sp (mat, pat, c+1, i-1, j+1) ||
  sp (mat, pat, c+1, i, j+1) ||
  sp (mat, pat, c+1, i+1, j+1) ||
  sp (mat, pat, c+1, i+1, j) ||
  sp (mat, pat, c+1, i+1, j-1) ||
  sp (mat, pat, c+1, i, j-1) ? 1 : 0;

- Dialecticus

---

是的，这样简单的编码调整可以做到，例如，如果字符串的长度大于nxn，则立即停止该过程等等，但这并不会减少最坏情况下的时间。我想研究算法改进。 - phoxis

@phoxis，请尝试使用此处提供的代码替换原有代码进行实验。我对结果很好奇。 - Dialecticus

基本上是一样的，但如果其中一个函数返回true，它就不会调用下一个函数。我考虑过这种可能性，但在这种情况下，并不是所有的匹配都会被找到，因为在找到一个匹配后，它就不会调用下一个匹配。当然，如果第一个调用返回true，这将停止搜索很多空间。感谢更新，如果只需要找到一个匹配，它肯定会有所改进，但不会改善最坏情况。 - phoxis

Answer 3

我认为在这里专注于最坏情况是不利的，因为没有真正的改进。然而，在“现实世界”中有许多有用的改进。例如，如果单词总是来自字典，如果它们可能长度有限（或者在统计上具有自然分布）。对于小网格，您可以想象预先搜索它们以查找字典中的所有单词，将列表存储在哈希映射中，然后在需要“测试”单词时执行简单的查找。所有时间都花在构建索引上，但如果网格很少更改，则可能是可以接受的。

- Mike Sokolov