使用DFS解决8-Puzzle

Question

我正在寻找java中的代码,通过给定初始状态实现8-puzzle游戏的DFS和BFS:

1 2 3
8 0 4
7 6 5

和目标状态

2 8 1
0 4 3
7 6 5

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

这是我的代码.到目前为止,我只能实现DFS.到目前为止,我的程序执行的是一旦找到目标状态就输出SUCCESS.然而,它永远不会达到这一点.

谁能告诉我哪里出错了？

Answer 1

好的,所以你的程序花费的时间比预期的要长.首先,我们要确定它是否陷入无限循环,或者只是缓慢.为此,让程序通过在主循环中添加以下内容来打印其进度:

    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个.这就解释了为什么处理状态会越来越慢.因此,我们希望选择具有更高效的包含操作的数据结构,例如a 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".