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

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相邻的位置。

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

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

举个例子:假设瓷砖有 4x4 填充所有 a，因此有 16 个 a，要查找的字符串是 aaaaaaaaaaaaaaab，即 15 个 a 和一个 b。一种是消除带有未出现在图 block 中的字符的字符串。但最坏的情况仍然会出现，比如瓷砖有 abababababababab 并且要查找的字符串是 ababababababbb。

我的尝试是这样的:

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-complete* 中网格的哈密顿路径问题，因此单词搜索问题是 NP-hard。

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

---

*我记得不久前看到了一个证明，Wikipedia确认，但没有链接到引用 >:/

---

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