Post on 17-Jul-2015
description
transcript
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 1/7
Universidad Autónoma de Baja CaliforniaFacultad de ciencias químicas e ingeniería
Reporte Examen1 Solución de Puzzle 8 utilizando algoritmo A*
Materia: Inteligencia Artificial
Profesor:Dr. Alvarado Magaña Juan Paulo
Nombre:
Renteria Cuevas Roberto Alonso
Fecha de entrega: 23 de marzo del 2012
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 2/7
Solución de Puzzle 8 utilizando algoritmo A*
Introducción:
En esta práctica se busca aplicar el algoritmo A* para resolver el juego puzle 8 en la
menor cantidad de pasos, para esto tendremos que definir una heurística capaz de
guiar a nuestro algoritmo en la toma de decisiones de cual movimiento te llevara mas
pronto a la solución.
El problema trata de llegar al estado final que se muestra en la imagen de abajo en la
menor cantidad de pasos, esto partiendo de algún estado inicial como se muestra a
continuación.
Para definir la estructura de nuestro juego, creamos una serie de nodos los cuales
estarán conectados con otros nodos para formar la siguiente estructura:
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 3/7
Algoritmo:
Para resolver el problema se utiliza el algoritmo A* este es uno de los algoritmo más
utilizados en inteligencia artificial para la búsqueda de caminos. Este Algoritmo se conoce como A* y se lee A estrella. El Algoritmo A* desciende del algoritmo de Dijkstra. Es un algoritmo eficiente y nos garantiza la ruta más corta o la menos costosa entre 2 nodos,
siempre y cuando exista.
Pseudocodigo de A*
ABIERTOS := [INICIAL] //inicialización
CERRADOS := []
f'(INICIAL) := h'(INICIAL)
repetir
si ABIERTOS = [] entonces FALLO
si no // quedan nodos
extraer MEJORNODO de ABIERTOS con f' mínima
// cola de prioridad
mover MEJORNODO de ABIERTOS a CERRADOS
si MEJORNODO contiene estado_objetivo entonces
SOLUCION_ENCONTRADA := TRUE
si no
generar SUCESORES de MEJORNODO
para cada SUCESOR hacer TRATAR_SUCESOR
hasta SOLUCION_ENCONTRADA o FALLO
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 4/7
Implementación en JAVA para la solución del 8 puzzle:
public class AEstrella {
public ArrayList<Estado> A_Estrella(Estado e) {
//inicializamos las listas de estados abiertos y cerrados.ArrayList<Estado> abiertos = new ArrayList<Estado>();ArrayList<Estado> cerrados = new ArrayList<Estado>();
cerrados.add(new Estado(e));Estado nuevoEstado = new Estado(e);while (cerrados.get(cerrados.size() - 1).getNoPocisionados() != 0) {
nuevoEstado = new Estado(cerrados.get(cerrados.size() - 1));
//expandimos cada estado y lo agregamos a la lista de abiertos.for (int i = 0; i < nuevoEstado.getHueco().getNextNodes().size(); i++) {
abiertos.add(new Estado(nuevoEstado).mover(i));
} //si no existen estados abiertos entonces no tiene solucionif (abiertos.isEmpty()) {
return cerrados;}
//variables auxiliares para obtener el estado con mejor valor de heuristica.double mejorHeuristica = 1000000;int indexMejorHeuristica = 0;double auxH = 0;
//calculando el estado con mejor heuristicafor (int i = 0; i < abiertos.size(); i++) {
//obtenemos F(n)= g(n)+h(n)auxH = getHeuristica(abiertos.get(i), nuevoEstado.getProximoOrdenar().getValor());
//comparamos mejor heuristica con la nueva heuristica obtenidaif (auxH < mejorHeuristica) {
mejorHeuristica = auxH;indexMejorHeuristica = i;
}}
//anhadimos e estado con mejor heuristica a la lista de cerradoscerrados.add(new Estado(abiertos.get(indexMejorHeuristica)));
abiertos.clear();//liberamos memoria
}return cerrados;
}
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 5/7
/*** Este metodo calcula la heuristica que tiene el estado recibido.* F(n)= g(n)+h(n)* la heuristica que se utilizo es la siguiente:* valHeuristico = H1 + H2*10 + H3*100*
* DONDE:* H1= nodos que faltan de acomodar.* H2= Distancia Manhatan del nodo que queremos acomodar hasta el nodo en la posicion destino.* H3= Distancia Manhatan del nodo vacio "HUECO" hasta el nodo en la posicion destino.*** entre menor sea el valHeuristico se esta mas serca de la solucion.*/ public double getHeuristica(Estado e, int proximoOrd) {
double h = 0, h1 = 0, h2 = 0, h3 = 0;Nodo nodoProximoOrdenar = null, nodoDestino = null;
//calculamos la cantidad de nodos mal posicionados.h1 = e.getNoPocisionados();
nodoProximoOrdenar = e.getCasillas().get(e.getValIndex(proximoOrd));nodoDestino = e.getCasillas().get(e.getPosDestino(proximoOrd));
//obtenemos la distancia manhatan del nodo que vamos a acomodar al nodo Destino.h2 = nodoProximoOrdenar.getDistancia(nodoDestino);
//obtenemos la distancia manhatan del nodo HUECO al nodo Destino.h3 = e.getHueco().getDistancia(nodoDestino);
//calculamos el valor de la heuristicah = h1 + h2 * 10 + h3 * 100;
return h;}
}
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 6/7
Heuristica:
La heurística que se utilizo es la siguiente:valHeuristico = H1 + H2*10 + H3*100
DONDE:H1= nodos que faltan de acomodar.H2= Distancia Manhattan del nodo que queremos acomodar hasta el nodo en la
posición destino.H3= Distancia Manhattan del nodo vacio "HUECO" hasta el nodo en la posición
destino.
Entre menor sea el valHeuristico se esta mas cerca de la solución.
5/14/2018 Examen1 Inteligencia Artificial - slidepdf.com
http://slidepdf.com/reader/full/examen1-inteligencia-artificial 7/7
RESULTADO