8

考虑：

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_indexi_indexj_index

* * *
* x *
* * *

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

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

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

举个例子：假设瓷砖有 4x4 填充了所有a，因此是 16 个a，要查找的字符串是aaaaaaaaaaaaaaaab，即 15个 a和一个b。一种是消除带有未出现在图块中的字符的字符串。但是仍然会出现最坏的情况，例如瓷砖有ababababababababab并且要查找的字符串是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完成工作，执行回溯。

有没有更好的办法 ？或者是否有可能降低最坏情况的时间？

4

3 回答 3

4

没有多项式算法，所以我认为你不能变得更好......

可以使用字母矩阵对任何网格图（具有度 <= 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-complete。

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

我很确定那里有更多关于这个问题的信息。我刚刚从我的屁股中拿出了这个证据，我很确定我不是第一个看到这个问题的人。至少有一个很好的启发式方法可以很好地启发你在真正的杂志拼图中遇到的非退化案例......

于 2011-10-01T05:08:41.553 回答
1

一个简单的改进是r在每次调用后检查sp. 如果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;
于 2011-10-01T09:18:00.783 回答
0

I think you might find that focusing on the worst case is counterproductive here, because there is no real improvement to be made. However, there are many useful improvements to be made in "real world" cases. For example, if the words are always drawn from a dictionary, if they may be limited in length (or have a natural distribution of lengths, statistically speaking). For small grids you could imagine searching them in advance to find all words from a dictionary, storing the list in a hashmap, and then performing a simple lookup as words need to be "tested". All the time goes into building your index, but that may be acceptable if the grid rarely changes.

于 2011-10-01T21:49:17.453 回答