再帰的な単語検索アルゴリズム

Question

私はあなたのおばあちゃんに初めてのJava単語検索プログラムを書く時が来ました。しかし、彼女にレターグリッド内の言葉を探してすべての仕事をさせる代わりに、再帰的な関数4WaySearchが彼女のためにそれを行います！

唯一の問題は、次のとおりです。

私はそれは難しい一度にグリッドに置く起動したとき、すべての可能な文字の組み合わせを構築する再帰アルゴリズムを概念化するために見つけています。

が

/* 
* This is the method that calls itself repeatedly to wander it's way 
* through the grid using a 4 way pattern, 
* creating every possibly letter combination and checking it against a 
* dictionary. If the word is found in the dictionary, it gets added to a 
* collection of found words. 
* 
* Here an example of a 3x3 grid with the valid words of RATZ and BRATZ, but 
* the word CATZ isn't valid. (the C is not tangent to the A). 
* 
* CXY 
* RAT 
* BCZ 
* 
* @param row Current row position of cursor 
* @param col Current column position of cursor 
*/ 
private void 4WaySearch(int row, int col) { 

    // is cursor outside grid boundaries? 
    if (row < 0 || row > ROWS - 1 || col < 0 || col > COLS - 1) 
     return; 

    GridEntry<Character> entry = getGridEntry(row, col); 

    // has it been visited? 
    if (entry.hasBreadCrumb()) 
     return; 

    // build current word 
    currentWord += entry.getElement(); // returns character 

    // if dictionay has the word add to found words list 
    if (dictionary.contains(currentWord)) 
     foundWords.add(currentWord); 

    // add a mark to know we visited 
    entry.toggleCrumb(); 

    // THIS CANT BE RIGHT 
    4WaySearch(row, col + 1); // check right 
    4WaySearch(row + 1, col); // check bottom 
    4WaySearch(row, col - 1); // check left 
    4WaySearch(row - 1, col); // check top 

    // unmark visited 
    entry.toggleCrumb(); 

    // strip last character 
    if (currentWord.length() != 0) 
     currentWord = currentWord.substring(
     0, 
     (currentWord.length() > 1) ? 
      currentWord.length() - 1 : 
      currentWord.length() 
     ); 
} 

が私の頭の中で、私は、再帰的なツリーtraveralアルゴリズムなどの検索アルゴリズムを可視化しますが、各ノード（：ここ

は、私はすでに、私は正しい方向への大きな一歩を考えることを書かれているコードですこのケースではエントリ）には4つの子（正接のエントリ）があり、リーフノードはグリッドの境界です。

また、機能への最初の進入時にカーソルの位置は、ここでpsuedocodedループのためのシンプルで決定されます。私は今、しばらくの間、これについて考え、そして異なるアプローチをしようとしている

for (int r = 0; r < ROWS; r++) 
    for (int c = 0; r < COLS; c++) 
    4WaySearch(r,c); 
    end for; 
end for; 

。 ..しかし、私はまだそれの周りに私の心を包み込み、それを動作させるように見える。誰かが私に光を見せてくれますか？ （私とあなたのおばあちゃんのために：D）

Answer 1

何を助けることが再帰のためのいくつかの擬似コードは、ツリー構造を構築しています。ノードがツリー

for (int r = 0; r < ROWS; r++) 
    for (int c = 0; r < COLS; c++) 
    4WaySearch(new Node(null,r,c); //it is the root and has no parent 
    end for; 
end for; 

のための新しいルート・ノードを作成したい。そして、あなたはあなたのようにツリーを構築したいので

public class Node { 
    private String data; 
    private int row,col; 
    private Node parent; 
    public Node(Node parent,int row,int col) { 
     this.parent = parent; 
     this.col = col; 
     this.row = row; 
    } 
    public boolean hasParent(int row, int col) { 
     Node current = this; 
     while((current=current.parent)!=null) { 
      if(current.row == row && current.col==col) 
       return true; 
     } 
     return false; 
    } 

    public String toString() { 
     Node current = this; 
     StringBuffer sb = new StringBuffer(); 
     do { 
      sb.append(current.data); 
     }while((current = current.parent)!=null); 
     return sb.reverse().toString(); 
    } 
} 

のような新しい出発点を持つたびに定義されている場合go

private void FourWaySearch(Node c) { 
    if (c.row < 0 || c.row > ROWS - 1 || c.col < 0 || c.col > COLS - 1 || c.hasParent(c.row,c.col)) 
     return; 
    else { 

     c.data = grid[c.row][c.col]; //get the string value from the word search grid 
     if(dictionary.contains(c.toString())) 
      foundWords.add(c.toString()); 
     FourWaySearch(new Node(c,c.row-1,c.col)); 
     FourWaySearch(new Node(c,c.row,c.col-1)); 
     FourWaySearch(new Node(c,c.row+1,c.col)); 
     FourWaySearch(new Node(c,c.row,c.col+1)); 
    } 
} 

これはこれを行う最良の方法ではないかもしれませんが、私にとってはそれは簡単で簡単なようです。

Answer 2

だから、まずグリッドを確立する必要があります。この場合、あなたは3x3のために選出されました。必要なのは、グリッド上のすべての有効な点を追跡する方法です。Pointというオブジェクトを、コンストラクタとして2つのintを使用することをお勧めします。あなたが必要とするのは、Pointとcharで構成されるクラスです。これにより、Pointの各レターが利用できるかどうかを確認することができます。

これで、データ構造が完成しましたので、ゲームの有効な動きを追跡する必要があります。たとえば、私が3,3位（右下隅、または、あなたがゼロベースの場合は2,2）にいる場合、私が持っている唯一の有効な動きがあるかどうかを知る必要があります。これを決定する方法は、私が訪問したすべての場所を教えてくれるPointのSetを維持することです。これにより、再帰アルゴリズムを終了させることができます。

私はどうなる

if(!validMovesRemaining) 
    return 
else 
    removeValidPosition(pointToRemove); 
    captureLetter(composedObject); 
    recurse(pointsRemaining); 

Answer 3

私は木が行く方法だと思っていますが、他の答えはそれを使用しているようです。 あなたが探している単語の解析木を構築することです（辞書から） - 各文字はノードであり、26の可能な子、アルファベットの各文字の1つ（nullの子の前、の再帰）、それが完全な単語かどうかを示すフラグ。それぞれの方向を確認し、その方向に移動できるかどうかを確認し、それに応じて移動します。

私は、ハードな部分はツリーを構築していると言いますが、再帰的に行うべきではありませんが、もうちょっと考えました。ツリーを構築する最善の方法は再帰的です。

これは明らかに概要に過ぎませんが、うまくいけば十分です。あなたが再び立ち往生した場合は、コメントして、私はあなたが正しい方向にもっと押し込むことができるかどうかを見ていきます。