使用DFS解决8难题

好的,所以你的计划花费的时间比预期的要长。首先,我们想知道它是卡在无限循环中,还是只是缓慢。为此,让程序通过向主循环添加以下内容来打印其进度:

    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”。

我建议你使用 Hipster library 使用BFS、DFS、A*、IDA*等轻松解决8难题 full example here (这可能有助于您设计搜索策略)。

如果您感兴趣,解决问题的基本步骤是首先定义允许您遍历状态空间搜索问题的函数,然后选择一个算法来搜索状态空间问题。为了创建搜索问题,可以使用 ProblemBuilder 类别:

SearchProblem p = 
  ProblemBuilder.create()
    .initialState(Arrays.asList(5,4,0,7,2,6,8,1,3))
    .defineProblemWithExplicitActions()
    .useActionFunction(new ActionFunction<Action, List<Integer>>() {
    @Override
    public Iterable<Action> actionsFor(List<Integer> state) {
        // Here we compute the valid movements for the state
        return validMovementsFor(state);
    }
    }).useTransitionFunction(new ActionStateTransitionFunction<Action, List<Integer>>() {
    @Override
    public List<Integer> apply(Action action, List<Integer> state) {
        // Here we compute the state that results from doing an action A to the current state
        return applyActionToState(action, state);
    }
    }).useCostFunction(new CostFunction<Action, List<Integer>, Double>() {
    @Override
    public Double evaluate(Transition<Action, List<Integer>> transition) {
        // Every movement has the same cost, 1
        return 1d;
    }
    }).build();

一旦有了问题定义,就可以选择任何算法来解决问题:

System.out.println(Hipster.createDijkstra(p).search(Arrays.asList(0,1,2,3,4,5,6,7,8)));

在本演示中,您可以阅读更多关于8道难题的详细信息,以及如何使用Hipster解决它 https://speakerdeck.com/pablormier/hipster-an-open-source-java-library-for-heuristic-search

您不应该将已经添加到其中的开放堆栈组合推入。(另外,ArrayDeque会更好,Stack是一个旧类,请参见javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

更完整和一致的LIFO堆栈操作集是 由Deque接口及其实现提供 优先于该类使用。例如:

Deque堆栈=新数组Deque(); )

为了避免无数次探索相同的状态,必须使用Set作为关闭列表,并验证您试图添加到打开列表中的状态从未添加到关闭列表中。

此外,使用byte[]数组(而不是int[]来节省内存)而不是字符串来执行操作可能会更舒服。

总之,您可以这样构造代码:

public class Taquin {
    private byte[][] state = new byte[3][3];

    public Taquin(String s) { ... }
    public List<Taquin> successors() { ... }
    public boolean isSolvable(Taquin goal) { ... }
    //Necessary to use the Set !////////////
    public int hashCode() { ... }
    public boolean equals(Object o) { ... }
    public String toString() { ...state }
    ////////////////////////////////////////

    public void solve(Taquin goal) { 
        if (isSolvable(goal)) {
            Deque<Taquin> open   = new ArrayDeque<>();
            Set<Taquin>   closed = new HashSet<>();
            closed.add(this);
            open.add(this);

            Taquin current = this;
            //if isSolvable is correct you should never encounter open.isEmpty() but for safety, test it
            while (!current.equals(goal) && !open.isEmpty()) {
                current = open.pop();
                System.out.println(current);
                for (Taquin succ : current.successors())
                    //we only add to the open list the elements which were never "seen"
                    if (closed.add(succ))
                        open.add(succ);
            }
            System.out.println("Success");
        } else
            System.out.println("No solution");
    }
}

这具有对图形中的任何类型的搜索都通用的优点。如果您想解决另一个难题,只需修改我没有实现的方法(实际上是Node接口的一部分)。如果你想改变算法,例如A星,它通常用于8个谜题,你只需要改变求解方法。我希望这段代码对您有所帮助。