Tarea Generar Sucesores y Mostrar Puzzle

Código que dado al ingresar un string (ej: 123045678) que emula un puzzle8 con cualquier estado inicial entrega los estados hijos (nodos hijos) dado por los posibles movimientos permitidos.

package puzzle8;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Puzzle8 {

    Queue<String> nodos = new LinkedList<String>();
    Integer i = 0;

    public static void main(String args[]){
        System.out.println ("Ingrese Valores:");
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        Puzzle8 e = new Puzzle8();
        e.printPuzzle(str);//IMPRIME ESTADO INICIAL
        e.generaSucesores(e, str);
    }
   
    void generaSucesores(Puzzle8 e, String str) {
        //ARRIBA
        int a = str.indexOf("0");
        if(a>2){
            String nextState = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
            printPuzzle(nextState);
        }
        //ABAJO
        if(a<6){
            String nextState = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
            printPuzzle(nextState);
        }
        //IZQUIERDA
        if(a!=0 && a!=3 && a!=6){
            String nextState = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
            printPuzzle(nextState);
        }
        //DERECHA
        if(a!=2 && a!=5 && a!=8){
            String nextState = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
            printPuzzle(nextState);
        }
    }

    private void printPuzzle(String puzzle) {
        if(i==0){
            System.out.println("-------");
            System.out.println("Estado Inicial:");
        } else {
            System.out.println("Nodo Hijo:" + i);
        }
        System.out.println(puzzle.substring(0,1)+"|"+ puzzle.substring(1,2)+"|"+ puzzle.substring(2,3));
        System.out.println(puzzle.substring(3,4)+"|"+ puzzle.substring(4,5)+"|"+ puzzle.substring(5,6));
        System.out.println(puzzle.substring(6,7)+"|"+ puzzle.substring(7,8)+"|"+ puzzle.substring(8,9));
        System.out.println("-------");
        i = i + 1;
    }
}

INFORME PROBLEMA PUZZLE 8

Fundamentos de Sistemas Inteligentes

ACI 710

 

Trabajo Práctico de Búsqueda en el Espacio de Estados

Integrantes:

Nathalia Astorga

Rodrigo Cofré

Pablo Guzmán

Erika Torres

Introducción

“Puzzle refiere en su idioma de procedencia (inglés) a una pregunta o problema difícil de entender o responder”.

El siguiente informe es sobre la resolución del puzzle 8. El puzzle 8 es un clásico problema de un tablero matricial de 3x3 (total 9) en cual hay 8 posiciones ocupadas por fichas numeradas (en forma aleatoria) además de un espacio vacío (sin número asignado), la idea es resolverlo para ello debemos mover este espacio de forma horizontal (h) o vertical (v), con la ficha adyacente.

El objetivo es llegar de un estado inicial (desordenado) a un estado final (ordenado).

El informe se compone de las siguientes etapas:

·         Desarrollo de una representación del problema en el Espacio de Estados.

·         Implementación de los algoritmos de Búsqueda en Profundidad y Búsqueda en Anchura.

·         Comprobación del código para varios estados iniciales.

Representación de problemas en el espacio de estados

Estados

Definiremos primeramente el estado Inicial y Final del puzzle:

Figura N°1: Estado Inicial                                                           Figura N°2: Estado Final

 

Definiremos el estado inicial como “desordenado”, o simplemente como cualquier estado distinto al final. En la imagen 1 podemos ver un ejemplo de estado inicial. En la imagen 2 vemos el estado final.

Operadores

En este problema tenemos cuatro operadores, arriba, abajo, derecha e izquierda, que se corresponde con los movimientos que puede la ficha vacía (hueco o “0”).

Análisis de la Solución

Existen 9! estados posibles (362.880), con solo 1 estado final, como ya habíamos definido. Ahora como máximo 4 posibles movimientos, o sea 4 estado posibles, y eso sucede cuando la ficha vacía se encuentra en el centro. En cualquier otra posición solo tiene 2 opciones de movimiento (obviamente no consideraremos como movimiento valido realizar un retroceso, o sea volver al estado anterior).

Figura N°3: Grafo para puzzle

 

En la figura anterior podemos ver los 4 primeros estados posibles, y los siguientes 6 posibles estados para cierto estado inicial. Así podríamos seguir completando el árbol hasta dar con la solución (estado final).

Búsqueda en Profundidad (DFS)

Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Figura N°4: Grafo de Búsqueda en Profundidad

 

En la figura anterior se muestra un grafo ejemplo para una búsqueda en profundidad, el árbol es recorrido en el orden 1,2,3…

La búsqueda en profundidad es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol (esto se conoce como backtracking).

Figura N°5: Búsqueda en profundidad para un ejemplo de puzzle

 

Búsqueda en Anchura (BFS)

Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.

Figura N°6: Grafo de Búsqueda en Anchura

 

En la figura anterior se muestra un grafo ejemplo para una búsqueda en anchura, el árbol es recorrido en el orden 1, 2, 3…

Figura N°7: Búsqueda en Anchura para un puzzle.

 

Explicación Algoritmo BFS

Nuestro código usa un tipo de algoritmo básico, definitivamente no tiene infinita cantidad de estados, ya lo habíamos calculado ese dato. Es un tipo de algoritmo de búsqueda no informada, es decir sigue un orden preestablecido.

Explicando más a fondo usa una estructura llamada HashMap, que permite almacenar pares clave/valor. De tal manera que para una clave solamente tenemos un valor. En esta estructura almacenamos el estado, como un par ordenado (estado_nuevo, estado_antiguo), esto es muy útil dado que se descarta automáticamente los estados repetidos.

Se recorre esta estructura hasta encontrar el estado final ("123456780"). Si no es encontrado el estado final genera un mensaje.

Finalmente si encuentra el estado final genera los pasos, entrega el nivel en el cual se encuentra el estado final y la cantidad de nodos leídos

Conclusiones

Lamentablemente el algoritmo no es lo suficientemente eficaz hay ejemplos en los cuales no encuentra la solución. Por ejemplo para el estado inicial: “123456870” no hay solución, lo cual lleva a pensar que sería muy fácil de resolver, pero dado que guarda una única vez en el HashMap cada estado es que no se puede repetir dicho estado.

En la siguiente imagen se muestran estadísticas de para algunos estados iniciales:

Estado Inicial	Tiempo (seg)	Nodos Leidos	Nivel	Estado Final
087465132		178881	28	SI
123456780	0	4	0	SI
203145786	0	53	5	SI
123750486				NO
283164705				NO
481302765				NO
216408753				NO
523048761				NO

Código BFS

package puzzle8;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

import java.util.Queue;

import java.util.Scanner;

class Puzzle8 {

    Queue<String> nodos = new LinkedList<String>();  

    Map<String,Integer> estado_inicio = new HashMap<String, Integer>();

    Map<String,String> estadoHistorico = new HashMap<String,String>();

    Integer i = 0;

    Integer j[] = new Integer[50];

   

    public static void main(String args[]){

        /*System.out.println ("Ingrese Valores:");

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();  */   

       

        //String str="203145786";                               

        //String str="283164705";

        String str="087465132";

        //String str="203145786";

       

        Puzzle8 e = new Puzzle8();                              

        e.add(str, null);                                               

        while(!e.nodos.isEmpty()){

            String currentState = e.nodos.remove();

            e.up(currentState);                                       

            e.down(currentState);                                   

            e.left(currentState);                                   

            e.right(currentState);                         

        }

       

        /*for(i=0; i<j.length; i++){

           

        }*/

       

        System.out.println("No se Encontro el Estado Final");

    }

   

       void add(String estadoNuevo, String estadoAntiguo){

       

        if(!estado_inicio.containsKey(estadoNuevo)){

            int nivel = estadoAntiguo == null ? 0 : estado_inicio.get(estadoAntiguo) + 1;

            estado_inicio.put(estadoNuevo, nivel);

            nodos.add(estadoNuevo);

            estadoHistorico.put(estadoNuevo, estadoAntiguo);

           

            i += 1;

            /*if(nivel == 5)//SEGUIMIENTO POR NIVEL

                System.out.println(estadoNuevo + " - Nivel: " + nivel);*/

            //j[nivel] += 1;

           

        }

        //if(nivel == 5)//SEGUIMIENTO POR NIVEL

        //System.out.println("Cantidad ESTADOS por Nivel: " +cant);

    }

  

    void up(String currentState){//ARRIBA

        int a = currentState.indexOf("0");

        if(a>2){

            String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);

            Verifica(currentState, nextState);

        }

    }

    void down(String currentState){//ABAJO

        int a = currentState.indexOf("0");

        if(a<6){

            String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);

            Verifica(currentState, nextState);

        }

    }

    void left(String currentState){//IZQUIERDA

        int a = currentState.indexOf("0");

        if(a!=0 && a!=3 && a!=6){

            String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);

            Verifica(currentState, nextState);

        }

    }

    void right(String currentState){//DERECHA

        int a = currentState.indexOf("0");

        if(a!=2 && a!=5 && a!=8){

            String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);

            Verifica(currentState, nextState);

        }

    }

    private void Verifica(String oldState, String estadoNuevo) {

        add(estadoNuevo, oldState);

        if(estadoNuevo.equals("123456780")) {

            System.out.println("Estado Final - Nivel :"+estado_inicio.get(estadoNuevo)+" Nodos Leidos: " + i);

            String estadoTrazado = estadoNuevo;

            while (estadoTrazado != null) {

                printPuzzle(estadoTrazado);

                estadoTrazado = estadoHistorico.get(estadoTrazado);

            }

            System.exit(0);

        }

    }

   

    private void printPuzzle(String puzzle) {

        System.out.println(puzzle.substring(0,1)+"|"+ puzzle.substring(1,2)+"|"+ puzzle.substring(2,3));

        System.out.println(puzzle.substring(3,4)+"|"+ puzzle.substring(4,5)+"|"+ puzzle.substring(5,6));

        System.out.println(puzzle.substring(6,7)+"|"+ puzzle.substring(7,8)+"|"+ puzzle.substring(8,9));

        System.out.println("-------");

    }

}