5

私は Coursera のアルゴリズム、パート IIコースに登録しました。課題の 1 つは、ボーグル ゲームを解くことです: http://coursera.cs.princeton.edu/algs4/assignments/boggle.html

名誉規定では、解決策を公に投稿しないことが求められているため、代わりに基本アルゴリズムの疑似コードを次に示します。

visit:
  word <- board[i][j]
  start <- dictionary.match(word, start)
  if start is not null
      visited[i][j] <- true
      word <- prefix + word
      if word is longer than min required length 
          words <- words + word

      for (x, y) ∊ adj(i, j)
          if not visited(x, y)
            visit (x, y)

  visited[i][j] <- false

ディクショナリは Trie を使用して実装されます。

上記のコードは機能し、私は割り当てに合格しましたが、動的プログラミングを使用したより高速なソリューションを主張する次のブログ投稿に出くわしました。

気の利いた動的計画法を使用して、単語 (この場合は辞書から) をボードから構築できるかどうかをすばやく確認できます。

動的計画法の考え方の要点は次のとおりです。

ボードの [i, j] 番目の位置 (終了位置) で長さ k の単語が見つかるには、その単語の k-1 番目の文字が [i, j] の隣接するセルの 1 つに配置されている必要があります。 j].

基本ケースは k = 1 です。

長さ 1 の文字は、ボードの [i, j] 番目のセルで見つかります (終了位置)。単語内の唯一の文字は、ボードの [i, j] 番目の位置の文字と一致します。

動的計画法テーブルに基本ケースが入力されると、その上に長さ k (k > 1) の任意の単語を構築できます。

残念ながら、著者の説明は不十分であり、私は彼の解決策をたどることができません。私はしたいのですが、ここの誰かが私にそれを説明してくれることを願っています.

PS:

  1. DPを使用していないため、この質問の複製ではありません。それらの重複した幸せな指を抑えてください。

  2. 私の側では十分な努力が示されており、誰にも宿題をするように頼むことはありません. 私はすでに独自の解決策を持っています。私が興味を持っているのは、問題を解決するためのより良い方法があればそれを学ぶことです。

ありがとう！

4

1 に答える 1

2

DP (間違った) ソリューションのアイデアは単純で、"apple" という単語がテーブルに存在するかどうかを確認したいとします。

  • 長さのある単語の接頭辞がセルで終わるかどうかdp[k][n][n]をdp[a][x][y]意味するテーブルを作成しましょう。a(x, y)

    [a][p][p]
[x][x][l]
[x][x][e]

上記の表の場合dp[1][0][0] = true、 、 のプレフィックス長 1appleはa などですdp[2][0][1] = true。

  • dp[a][x][y]では、真かどうかを確認するにはどうすればよいでしょうか。の隣接するすべてのセルをチェックし、隣接するセルの(x,y)1 つに がある場合dp[a - 1][][] = true、これdp[a][x][y]も true です。この例では、セル(0,2),dp[3][0][2] = trueの場合、隣接するセルの 1 つとして、セル(0,1)は次のようになります。dp[2][0][1] = true
  • デフォルトでは、すべてdp[0][x][y] = true
  • 任意のセル(x, y)の場合、dp[length of word][x][y] = true-> 単語がテーブルに存在する場合。

このソリューションでは、文字が複数回使用されている場合にチェックできないことに注意してください。

apa上の表で単語を探す必要がある場合のように

dp[1][0][0] = true -> dp[2][0][1] = true -> dp[3][0][0] = true
于 2018-07-12T10:31:21.200 に答える