logo标签列表

使用深度优先搜索解决8-Puzzle问题

javaartificial-intelligencedepth-first-searchsliding-tile-puzzlestate-space
8
我正在寻找用Java实现8数码游戏的DFS和BFS代码，给定初始状态。
1 2 3
8 0 4
7 6 5

以及目标状态

2 8 1
0 4 3
7 6 5

我需要打印出从起始状态到目标状态的解决路径（目前还没有做到）

这是我已经有的代码。到目前为止，我只能实现深度优先搜索。目前我的程序所做的是在找到目标状态时输出SUCCESS。然而它从未达到这一点。

有人能告诉我我错在哪里吗？

他在谈论这个（http://en.wikipedia.org/wiki/15_puzzle），但是是3x3版本。它在法语中叫“Taquin”。 - Dici
3个回答
7

好的，所以您的程序运行时间比预期长。首先，我们需要确定它是否陷入了无限循环，或者只是运行缓慢。为此，让我们在主循环中添加以下代码，使程序打印其进展情况：

    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个元素。这就解释了为什么处理一个状态会变得越来越慢。因此，我们将选择使用具有更高效的contains操作的数据结构，例如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"。

我从你的解释中学到了很多。非常感谢！ - RK2015
我只是想知道如何将LinkedHashSet用作堆栈，也就是后进先出。在你提供的代码中，它是先进先出。 - RK2015
我不知道JDK中是否有LIFO映射，因此我会使用两个数据结构：一个用于跟踪顺序的堆栈，以及一个用于高效成员测试的HashSet。 - meriton
"left" 方法出现错误。p 不应为 0、3 或 6，而不是 0、3 或 7。 - Ron
2
我建议您使用Hipster library轻松解决8数码难题，可以使用BFS、DFS、A*、IDA*等算法。这里有一个完整的例子（它可能会帮助您设计搜索策略）。
如果您有兴趣，解决问题的基本步骤是首先定义函数，使您能够遍历状态空间搜索问题，然后选择一个算法来搜索状态空间问题。为了创建搜索问题，您可以使用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。
1
你不应该将已经添加到开放栈中的组合再次推入。此外，ArrayDeque会更好，Stack是一个旧类，请参阅javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html 更完整和一致的LIFO堆栈操作集由Deque接口及其实现提供，应优先使用该类。例如：
Deque stack = new ArrayDeque();
为了避免多次探索相同的状态，必须使用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* 算法，你只需更改解决方法。希望这段代码示例能帮到你。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接