Алгоритм поиска по рекурсивному слову - PullRequest
Новая
       36

Алгоритм поиска по рекурсивному слову

0 голосов
/ 26 октября 2011

Пришло время написать вашей бабушке ее первую программу поиска слов на 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()
        );
}

В моей голове я представляю алгоритм поиска точно так же, как алгоритм обхода рекурсивного дерева, но у каждого узла (в данном случае записи) есть 4 дочерних элемента (записи касательных), а конечные узлы являются границами сетки.

Кроме того, расположение курсора при первоначальном входе в функцию определяется простым циклом for, psuedocoded здесь: 

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

Я уже некоторое время думаю об этом и пробую разные подходы ... но я все еще не могу обернуться и заставить это работать. Может кто-нибудь показать мне свет? (Ради меня и твоей бабушки!: D)

Ответы [ 3 ]

0 голосов
/ 27 октября 2011

Что бы я сделал, это построил древовидную структуру.Где узел определяется следующим образом: 

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();
    }
}

Каждый раз, когда у вас появляется новое начальное место, вы хотите создать новый корневой узел для дерева 

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;

И затем вы хотите построитьдерево по ходу дела 

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));
    }
}

Возможно, это не лучший способ сделать это, но мне кажется, что за ним просто и легко следовать.

0 голосов
/ 27 октября 2011

Я думаю, что дерево - это путь, но не так, как его используют другие ответы.Что бы я сделал, это построил бы дерево синтаксического анализа слов, которые вы ищете (из словаря) - каждая буква - это узел с 26 возможными дочерними элементами, по одному для каждой буквы алфавита (проверьте для nullдети до рекурсивные) и флаг, указывающий, является ли это полным словом.Проверьте каждое направление, посмотрите, можете ли вы двигаться в этом направлении и двигаться соответственно.

Я собирался сказать, что сложная часть будет строить дерево, и это не должно быть сделано рекурсивно, но я простодругая мысль.Лучший способ построить дерево также рекурсивный.

Это, очевидно, просто обзор, но, надеюсь, достаточно, чтобы дать вам старт.Если вы снова застряли, прокомментируйте, и я посмотрю, смогу ли я подтолкнуть вас в правильном направлении.

0 голосов
/ 27 октября 2011

Итак, что вам нужно сделать, это сначала установить сетку. В этом случае вы выбрали 3х3. Вам нужен способ отслеживать все действительные точки на сетке. Могу ли я порекомендовать объект с именем Point, который принимает два int s в качестве конструктора. Следующее, что вам нужно, это класс, который состоит из Point и char, это позволит нам увидеть, какая буква имеется у каждого Point.

Теперь, когда у нас есть структура данных, нам нужно отслеживать действительные ходы для игры. Например, если я нахожусь в позиции 3,3 (нижний правый угол или 2,2, если вы основаны на нуле), мне нужно будет понять, что единственные действительные ходы, которые у меня есть, - вверх или влево. Чтобы определить это, оставьте Set из Point s, которые сообщат мне все места, которые я посетил, это позволит рекурсивному алгоритму завершиться.

Какой-то псевдокод для рекурсии, который может помочь 

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