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
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
|
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("-------");
}
}
tienes el de DFS?
ResponderEliminar