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

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.

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

我想出了一个简单的回溯解决方案,解决方案非常快,但最坏的情况时间真的更糟.

举一个例子:假设瓷砖有4x4填充了所有的 s,因此16 a,并且要查找的字符串是aaaaaaaaaaaaaa,即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 完全的。

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

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