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。

タスクは、タイル内の特定の文字列を見つけることです。条件は、指定された文字列のすべての文字が隣接している必要があり、指定された文字列を構成するためにタイル内の1つの文字を複数回使用することはできないということです。

私は単純なバックトラックソリューションを考え出しました。そのソリューションはかなり高速ですが、最悪の場合の時間は本当に悪いです。

例：タイルの4x4がすべての's、つまり16 a 'で満たされ、検索する文字列がaaaaaaaaaaaaaaaab、つまり15a 'sと1つのbであるとします。1つは、タイルに表示されない文字を含む文字列を削除することです。しかし、それでも最悪のケースは、タイルにababababababababがあり、検索する文字列がabababababababbbbであると言うことで表示される可能性があります。

私の試みは次のようなものです：

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

元のグラフでハミルトンパスを検索することは、文字列BaBaBaBaBaBaBaBaBaB（9つのBすべてを含む）を検索することと同じです。しかし、NP完全*のグリッドのハミルトン閉路問題であるため、単語検索の問題はNP困難です。

単語パスは明らかに多項式証明書であるため、行列での単語検索問題はNP完全です。

*私はしばらく前にこれの証拠を見て、ウィキペディアが確認したことを覚えていますが、参照にリンクしていません>：/

私はそこにこの問題についてもっとあるとかなり確信しています。私はちょうどこの証拠を私のお尻から引き出しました、そして私は問題を最初に見たのではないと確信しています。少なくとも、実際の雑誌のパズルで得られる非退化のケースについて、優れたヒューリスティックの可能性があります...

于 2011-10-01T05:08:41.553 に答える
1

r簡単な改善点の1つは、を呼び出すたびにの値を確認することspです。その後、r == 1呼び出しを停止しspます。あなたはあなたの解決策を見つけました。これは、考えられるすべての解決策を見つける必要がない限りです。

このようなもの（最初が真の場合、論理OR演算子は2番目のオペランドを計算しません）：

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

ここでは、実際に改善する必要がないため、最悪のケースに焦点を当てることは逆効果であることに気付くかもしれません。ただし、「実世界」の場合には、多くの有用な改善を行う必要があります。たとえば、単語が常に辞書から抽出されている場合、長さが制限されている可能性がある場合（または、統計的に言えば、長さが自然に分布している場合）。小さなグリッドの場合、辞書からすべての単語を見つけるために事前に検索し、リストをハッシュマップに保存してから、単語を「テスト」する必要があるため、単純なルックアップを実行することを想像できます。常にインデックスの作成に使用されますが、グリッドがめったに変更されない場合は、それで問題ない場合があります。

于 2011-10-01T21:49:17.453 に答える