Résolution du puzzle 8 en utilisant les optimisations DFS

Question

Je suis en train d'utiliser Java pour résoudre le problème du Puzzle à 8 cases en utilisant DFS.

Voici ce à quoi je suis arrivé :

    public static boolean found = false;

        public void solveDepthFirst(EightPuzzle currentState, int lastMove){

            if(currentState.goal()){
                System.out.println(currentState);
                found = true;//pour arrêter DFS lorsqu'une solution est trouvée (même si ce n'est pas optimal)
                return;
            }

            for(int i=0;i

`

!e.equals(currentState) vérifie si le déplacement est possible. (si currentState.move(i) est hors limites move() renvoie le même état)

i != lastMove assure que si lors de votre dernier déplacement vous avez bougé vers la droite vous ne bougez pas vers la gauche maintenant (car cela n'a aucun sens)

visitedNodes est un HashSet de nœuds visités.

Cela épuise l'espace de la pile. Lorsque j'utilise -xss10m pour augmenter l'espace de la pile de 128k à 10m, l'algorithme fonctionne bien. Cependant, je suis sûr qu'il y a beaucoup d'autres optimisations qui peuvent être faites.

tout conseil serait grandement apprécié.

`

Answer 1

Je pense que vous pouvez accélérer votre recherche considérablement en marquant un état comme visité avant de passer à un appel récursif. Sinon, il n'y a pas trop d'optimisations pour ce casse-tête : il vous suffit simplement d'essayer tous les mouvements possibles.

Answer 2

Tout d'abord, vous pouvez créer une pile à la place d'un appel récursif. Ajoutez lastMove à la classe EightPuzzle.

Voici ce que vous obtenez:

// Queue queue = new PriorityQueue();
Stack stack = new Stack();

public void solveDepthFirst() {

    while (true) {
        EightPuzzle currentState = stack.pop(); // queue.poll();
        if (currentState.goal()) {
            System.out.println(currentState);
            found = true; // pour arrêter DFS quand une solution est trouvée (même si non
                            // optimale)
            return;
        }

        for (int i = 0; i < 4; ++i) {
            if (found)
                return;

            EightPuzzle e = currentState.move(i);// 0 = haut, 1 = bas, 2 =
                                                    // gauche,
                                                    // 3= droite

            if (!e.equals(currentState) && i != currentState.getLastMove()
                    && !visitedNodes.contains(e)) {
                stack.push(e); // queue.add(e);
            }
            if (!visitedNodes.contains(currentState.toString())) {
                visitedNodes.add(currentState);
            }
        }
    }
}

Les performances chutent significativement lorsque vous utilisez des appels récursifs au lieu d'une conception itérative.

Ensuite, vous pouvez optimiser davantage (mais ce ne sera pas un vrai DFS) en utilisant une PriorityQueue. L'heuristique à utiliser peut être la distance de Manhattan. De cette manière, la première solution à rechercher sera la plus proche de la cible. C'est plus efficace mais ce n'est pas un strict DFS.

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/PriorityQueue.html