java - 在 Boggle.java 游戏中部署启发式修剪搜索空间

Question

所以，我正在尝试编写一个模拟游戏 Boggle 的 java 程序。它输入两个文本文件，第一个是代表 nxn 板的文本文件，其中第一行包含板的尺寸，即 4x4.txt 文件的第一行将是数字 4，其余的将是板本身。第二个 txt 文件将是包含所有可能的字典单词的文件。

我首先想验证我们用于从 nxn 网格生成所有可能的字符串输出的算法是否正确。我使用深度优先搜索算法来做到这一点。

我相信我已经正确理解了这部分内容。但是，现在我要实现一种启发式方法来帮助识别死胡同并节省搜索浪费的单词和浪费时间。我不知道这应该如何进行。任何帮助将不胜感激。

这是我迄今为止的代码。就像我说的，我的深度优先搜索方法是正确的，并且给了我正确的输出。我也不热衷于使用 TreeSet 来存储字典单词，因为我什至不确定这是否正确。我这样做是因为我知道这是存储可能的字符串组合的正确 ADT。

import java.io.*;
import java.util.*;

public class Boggle {

    //Above main declare a static long int numWordsFormed=0;
    private static int numWordsFormed = 0;
    private static TreeSet<String> allPossWords = new TreeSet<String>();

    public static void main(String[] args) throws Exception
    {
        Scanner dfile = new Scanner(new FileReader(args[0]));
        TreeSet<String> dictionary = new TreeSet<String>();

        while(dfile.hasNext())
        {
            dictionary.add(dfile.next());
        }
        dfile.close();

        Scanner bfile = new Scanner(new FileReader(args[1]));
        int r = bfile.nextInt();
        int c = r;
        String[][] board = new String[r][c];

        for (int i = 0; i < r; i++) 
            for (int j = 0; j < c; j++)
                board[i][j] = bfile.next();

        for(int row = 0; row < board.length; row++)
            for(int col = 0; col < board[row].length; col++)            
                depthFirstSearch(board, row, col, "");

        for(String possWords : allPossWords)
            System.out.println(possWords);
    }

    public static void depthFirstSearch(String[][] board, int r, int c, String word)
    {
        word = word.concat(board[r][c]);
        ++numWordsFormed;
        allPossWords.add(word);

        if(((r-1) >= 0) && (Character.isLowerCase(board[r-1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c+1) < board[r-1].length) && (Character.isLowerCase(board[r-1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c+1) < board[r].length) && (Character.isLowerCase(board[r][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c+1) < board[r+1].length) && (Character.isLowerCase(board[r+1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && (Character.isLowerCase(board[r+1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c-1) >= 0) && (Character.isLowerCase(board[r+1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c-1) >= 0) && (Character.isLowerCase(board[r][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c-1) >= 0) && (Character.isLowerCase(board[r-1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }
    }

}

Answer 1

首先，实现一个 Trie，并在初始化时向其写入一个字典。任何单词的查找时间都是确定的，因为单词的长度是从 Trie 的空根到叶子的最后一个字母的遍历时间。

然后，根据 Trie 的结构，创建一个启发式。