改进单词搜索游戏最坏的情况

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 位于 旁边，则拼贴中的字母表 i_index 与另一个字母表 j_index 相邻 j_index位于以下任意位置：

* * *
* x *
* * *

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

任务是在图块中找到给定的字符串。条件是给定字符串的所有字符都应该相邻，并且图块中的任何一个字符都不能多次使用来构造给定字符串。

我想出了一个简单的回溯解决方案，该解决方案的速度相当快，但最坏情况下的时间确实更糟。

举个例子：假设图块有 4x4 填充了所有 a，因此有 16 个 a，要查找的字符串是 aaaaaaaaaaaaaaaab ，即 15 个 a 和 1 个 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 完成工作，执行回溯。

有更好的办法吗？或者是否有可能缩短最坏情况的时间？

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完全的。

---

*我记得不久前看到过一个证明，维基百科证实了这一点，但没有链接到参考文献>：/

---

我很确定这个问题还有更多内容。我刚刚从我的屁股里拿出了这个证据，我很确定我不是第一个看到这个问题的人。至少有一个很好的机会对你在真正的杂志谜题中得到的非退化案例进行很好的启发......

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;

Answer 3

我想你可能会发现，关注最坏的情况会适得其反，因为没有真正的改进可做。然而，在“现实世界”的情况下还有许多有用的改进需要进行。例如，如果单词总是从字典中提取，它们的长度是否可能受到限制（或者从统计角度来看，具有自然的长度分布）。对于小网格，您可以想象提前搜索它们以从字典中查找所有单词，将列表存储在哈希图中，然后在需要“测试”单词时执行简单的查找。所有时间都花在构建索引上，但如果网格很少发生变化，这可能是可以接受的。