Rekursive Suche nach Wort Algorithmus

Es ist Zeit für mich zu schreiben, dass Ihre Großmutter Ihr erstes Java-Wortsuche-Programm. Aber anstatt Ihr zu tun, die Arbeit suchen Wörter innerhalb der Buchstaben-raster, eine rekursive Funktion 4WaySearch tut es für Sie!

Das problem ist nur:

Ich finde es schwer zu konzipieren ist ein rekursiver Algorithmus, der baut alle möglichen Buchstaben-Kombination beim Start auf einmal Platz in der Startaufstellung.

Hier ist der code, den ich bereits geschrieben habe, dass ich erachten einen großen Schritt in die richtige Richtung:

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

In meinem Kopf, ich Stelle mir die search-Algorithmus genauso wie eine rekursive Struktur traveral Algorithmus, aber jeder Knoten (Eintrag in diesem Fall) hat 4 Kinder (Tangens-Werte), und die Endknoten sind die Grenzen des Rasters.

Auch, die Position des Cursors beim ersten Eintritt in die Funktion wird bestimmt durch eine einfache for-Schleife psuedocoded hier:

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

Denke ich darüber nach dies für eine Weile jetzt, und Sie versuchen, verschiedene Ansätze... aber ich kann immer noch nicht scheinen zu wickeln meinem Kopf herum und machen es zu arbeiten. Kann mir jemand zeigen, das Licht? (Zum Wohle von mir und deiner Großmutter! :D)

Ist dies eine Hausaufgaben-Frage?
Warum willst du diese rekursiv, Hausaufgaben?
Sie sagen CATZ nicht gültig ist, aber warum kann man nicht beginnen mit dem C auf der unteren Reihe? Dann scheint gültig zu sein.
Ja, es muss getan werden rekursiv.
mein Fehler, zu ignorieren, dass unten C. ersetzen Sie es mit.... O
Ja es ist eine Hausaufgabe. Versteh mich nicht falsch... ich möchte nicht, dass jemand den code schreiben, für mich, ich Suche gerade nach einem push in die richtige Richtung.
Das erste, was zu beachten ist, dass in einem wordsearch, das Wort hat alles in einer Linie, so dass Sie nicht wollen, um zu überprüfen, alle vier Richtungen, jede Rekursion. Zweitens, wo ist currentWord definiert?
Ich denke, es ist mehr wie ein boggle-Typ-Spiel suchen. Wo Sie suchen können in alle 4 Richtungen, aber gerade nicht die gleichen Buchstaben zweimal.
Ich sehe. Das macht zumindest mehr Sinn machen, Rekursion zu verwenden, für.
Das Wort muss nicht in einer geraden Linie. Solange die einzelnen Buchstaben des Wortes neben einander, es ist gültig. So könnten Sie haben verrückte Schlange-wie der Blick Worte. Und currentWord ist eine Klasse variabel, dies ist nur eine Methode aus der Klasse. Davon, dass alle Erklärungen, Funktionsaufrufe und syntaktische Zeug ist richtig.

InformationsquelleAutor snnth | 2011-10-26

Was ich tun würde, ist das aufbauen einer Baumstruktur. Wo ein Knoten definiert ist, wie so

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

Jedes mal, wenn Sie einen neuen Ausgangspunkt zum erstellen eines neuen root-Knoten für den Baum

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;

Und dann wollen Sie bauen den Baum, wie Sie gehen

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

Dies ist möglicherweise nicht der beste Weg, es zu tun, aber mir scheint es einfach und leicht zu Folgen.

Ich habe eigentlich die meisten des Programms implementiert, wie, dass. Aber statt mit Ihrer version von Knoten, wir wurden mit etwas ähnliches, das wir haben, zu verwenden: - Eintrag. Eintrag don ' T wissen über die "Kinder" (wenn Sie können) den Eintrag rechts neben Ihnen, Sie wissen nur, was Charakter ist in sich selbst. Aber die Klasse, die die 4WaySearch Methode hat auch eine Methode, schnappt sich den Eintrag an jeder position auf der raster: getGridEntry. Ich kann all das Zeug, um gut funktionieren... ich glaube einfach nicht, wir BEIDE sind rekursiv Durchlaufen des Gitters (Suche nach top-Eintrag, dann Links, unten, rechts) ist der richtige Weg.
Das ist der richtige Weg, um die traverse alle Einträge. Sie sind wesentliche Traversierung eines Baumes (en.wikipedia.org/wiki/Tree_traversal#Sample_implementations), sondern wo jeder Eintrag hat 4 Kinder.
JA. Also meine ursprüngliche Umsetzung war dann richtig. Ich war einfach nicht sicher, ob das Konzept dahinter. Danke für die Aufklärung für mich!

InformationsquelleAutor Danny

0

Also, was Sie tun müssen, ist zunächst das raster. In diesem Fall haben Sie gewählt für 3x3 . Was Sie brauchen, ist ein Weg, um zu verfolgen alle gültigen Punkte auf dem raster, kann ich empfehlen ein Objekt namens Point zwei ints, wie man den Konstruktor verwendet. Das nächste, was Sie brauchen, ist eine Klasse, die aus einer Point und ein char dies wird es uns ermöglichen, zu sehen, welcher Buchstabe steht an jeder Point .

Nun haben wir unsere Daten Struktur, die wir brauchen, um zu verfolgen gültigen Züge für das Spiel. Zum Beispiel, wenn ich bei der position 3,3 (in der unteren rechten Ecke, oder 2,2, wenn Sie null-basiert) würde ich brauchen, um zu realisieren, dass der einzig gültige Bewegungen, die ich oben oder Links. Die Art und Weise, dies zu bestimmen ist, um einen Set von Points, die mir sagen, all die Orte, die ich besucht habe, dies ermöglicht den rekursiven Algorithmus zu beenden.

Einige pseudocode für die Rekursion, die helfen können,
```
if(!validMovesRemaining)  
     return
else  
    removeValidPosition(pointToRemove);  
    captureLetter(composedObject);
    recurse(pointsRemaining);
```
InformationsquelleAutor Woot4Moo
0

Denke ich, ein Baum ist der Weg zu gehen, aber nicht in der Weise anderen Antworten zu sein scheinen, es zu benutzen.
Was ich tun würde, wäre der Aufbau der parse-Baum der Wörter, die Sie suchen (aus dem Wörterbuch) - jeder Brief ist ein Knoten, mit 26 möglichen Kinder, eine für jeden Buchstaben des Alphabets (überprüfen Sie null Kinder vor recursing), und ein flag zu sagen, ob es ein vollständiges Wort. Prüfen Sie für jede Richtung, sehen, wenn Sie in diese Richtung zu bewegen, und bewegen sich entsprechend.

Ich würde sagen, dass der harte Teil würde den Aufbau der Struktur, und es sollte nicht getan werden, die rekursiv, aber ich hatte gerade einen anderen Gedanken. Der beste Weg zu bauen, der Baum ist auch rekursiv.

Dies ist natürlich nur ein überblick, aber hoffentlich genug, um Ihnen einen start. Wenn Sie nicht weiterkommen, wieder, Kommentar, und ich werde sehen, ob ich kann drücken Sie mehr in die richtige Richtung.

InformationsquelleAutor Kevin

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.