我正在寻找通过给定初始状态为 8 拼图游戏实现 DFS 和 BFS 的 java 代码:

1 2 3
8 0 4
7 6 5

和目标状态

2 8 1
0 4 3
7 6 5

我需要打印从初始状态到目标状态的解决方案路径(尚未完成)

这是我的代码。到目前为止，我只能实现 DFS。到目前为止，我的程序所做的是在找到目标状态后输出 SUCCESS。 然而，它永远不会达到这一点。

谁能告诉我哪里出错了？

最佳答案

好的，所以您的程序花费的时间比预期的要长。首先，我们想知道它是否陷入了无限循环，或者只是变慢了。为此，让我们通过将以下内容添加到主循环来让程序打印其进度:

    int statesVisited = 0;
    while (OPEN.empty() == false && STATE == false) {
        statesVisited++;
        System.out.println(statesVisited);

然后我们看到该程序每秒访问几千个状态。由于我们的处理器每秒执行数十亿条指令，这意味着处理一个状态需要大约一百万条 CPU 指令。它不应该那么高，不是吗？那么是什么原因造成的呢？

一般来说，我们现在会使用分析器来衡量所有这些时间花在了代码的哪一部分上，但是由于程序太短了，我们可以先尝试猜测。我的第一个猜测是打印我们访问的每个州可能会非常昂贵。为了验证这一点，让我们每第 1000 个状态打印一次:

    while (OPEN.empty() == false && STATE == false) {
        statesVisited++;
        if (statesVisited % 1000 == 0) {
            System.out.println(statesVisited);
        }

我们就地改变，我们注意到前 5000 个州在不到一秒的时间内被访问，所以打印确实很重要。我们还注意到一些奇怪的事情:虽然前 5000 个状态在一秒钟内被访问，但由于某种原因，程序似乎变得越来越慢。在访问 20000 个州时，访问 1000 个州大约需要一秒钟，而且情况会越来越糟。这是出乎意料的，因为处理一个状态不应该变得越来越昂贵。所以我们知道我们循环中的一些操作变得越来越昂贵。让我们检查一下我们的代码以确定它可能是哪个操作。

无论集合的大小如何，推送和弹出都需要恒定的时间。但是您还使用 Stack.search 和 LinkedList.contains。这两个操作都被记录为需要遍历整个堆栈或列表。因此，让我们输出这些集合的大小:

        if (statesVisited % 1000 == 0) {
            System.out.println(statesVisited);
            System.out.println(OPEN.size());
            System.out.println(CLOSED.size());
            System.out.println();
        }

稍等片刻后，我们看到:

40000
25947
39999

所以 OPEN 包含 25000 个元素，而 CLOSED 将近 40000 个。这就解释了为什么处理状态越来越慢。因此，我们希望选择具有更高效包含操作的数据结构，例如 java.util.HashSet 或 java.util.LinkedHashSet(这是两者的混合体)一个散列集和一个链表，允许我们按照添加的顺序检索元素)。这样做，我们得到:

public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
public static HashSet<String> CLOSED = new HashSet<String>();
public static boolean STATE = false;

public static void main(String args[]) {

    int statesVisited = 0;

    String start = "123804765";
    String goal = "281043765";
    String X = "";
    String temp = "";

    OPEN.add(start);

    while (OPEN.isEmpty() == false && STATE == false) {

        X = OPEN.iterator().next();
        OPEN.remove(X);

        int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
        if (X.equals(goal)) {
            System.out.println("SUCCESS");
            STATE = true;
        } else {
            // generate children
            CLOSED.add(X);

            temp = up(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = left(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = down(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
            temp = right(X, pos);
            if (!(temp.equals("-1")))
                OPEN.add(temp);
        }
    }

}

/*
 * MOVEMENT UP
 */
public static String up(String s, int p) {
    String str = s;
    if (!(p < 3)) {
        char a = str.charAt(p - 3);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT DOWN
 */
public static String down(String s, int p) {
    String str = s;
    if (!(p > 5)) {
        char a = str.charAt(p + 3);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
    }

    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT LEFT
 */
public static String left(String s, int p) {
    String str = s;
    if (p != 0 && p != 3 && p != 7) {
        char a = str.charAt(p - 1);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

/*
 * MOVEMENT RIGHT
 */
public static String right(String s, int p) {
    String str = s;
    if (p != 2 && p != 5 && p != 8) {
        char a = str.charAt(p + 1);
        String newS = str.substring(0, p) + a + str.substring(p + 1);
        str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && CLOSED.contains(str) == false)
        return str;
    else
        return "-1";
}

public static void print(String s) {
    System.out.println(s.substring(0, 3));
    System.out.println(s.substring(3, 6));
    System.out.println(s.substring(6, 9));
    System.out.println();
}

它几乎立即打印出“SUCCESS”。

关于java - 使用 DFS 解决 8-Puzzle，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25230298/