Reporte miguel angel_garcia_wha

BUSQUEDA EN ANCHURA Y HILL CLIMBING USANDO ELJUEGO DEL 8-PUZZLE

Asignatura: INTELIGENCIA ARTIFICIAL

Profesor: Dra. Heidy Marisol Marín Castro

Alumno: Miguel Angel Garcia Wha

Matricula: [email protected]

Maestría en Ingeniería

Fecha: Martes 26 de enero del 2016

Cd. Victoria, Tamaulipas.

Índice

1. Introducción

2. Desarollo

3. Analisis de resultados

4. Conclusiónes

5. Fuentes de información

6. Fuentes de Anexos

1. Introducción

El uso de herramientas de busqueda o de algoritmos nos facilita el uso de estrategias para encontrarmucho mas rapido un valor,meta u objetivo con la �nalidad de ir descubriendo mediante estas técnicas debusqueda lo que es el uso de algortmos que van basados o en relacion con la IA (Inteligencia Arti�cial) queen este reporte se veran solo dos estrategias de busqueda que son la busqueda en anchura y la busqueda dehill climbing, en las cuales mediante el juego del 8 puzzle que es un juego en su versión simpli�cada del juego15 puzzle que fue inventado por Sam Loyd en 1870 ,Loyd propuso un juego de mesa para un único jugadorque consistía en una caja cuadrada que contenía 15 piezas cuadradas numeradas del 1 al 15. La casilla vacíapermitirá mover a las piezas adyacentes de forma que estas fueran ordenadas en forma creciente. El objetivodel ocho puzzle es alcanzar un estado solución solo realizando movimientos permitidos, a esto se le puedellamar �espacio de estados�.

2. Desarollo

En este apartado se vera lo que es el desarollo o implementacion de ambos algoritmos de busqueda en eljuego del 8-puzzle y con sus capturas de pantalla para ver los resultados que estos arrojan en consola y consus respectivas caracteristicas cada uno.

1. BUSQUEDA EN ANCHURA:Al igual que en la búsqueda en profundidad se comienza en un estado (la raíz) que es el primer estadoactivo. En el siguiente paso se etiquetan como visitados todos los vecinos del estado activo que no han sidoetiquetados. Se continúa etiquetando todos los vecinos de los hijos de E (que no hayan sido visitados aún).En este proceso nunca se visita un estado dos veces por lo que se construye un grafo sin ciclos, que será unárbol generador de la componente conexa que contiene a v. Nuestra implementación utiliza una pila FIFO(primero en entrar, último en salir) por esta razón siempre nos avanzamos desde la derecha.

1 CLASE 1 PRINICIPAL:

2

3 package busquedaanchura_angelwha;

4

5 public class Principal {

6

7 public static void main(String [] args) {

8

9 /* int[] estadoInicial = {8, 0, 3,

10 2, 6, 1,

11 4, 7, 5};*/

12

13 int[] estadoInicial = {4, 1, 2,

14 7, 0, 3,

15 5, 6, 8};

16

17 if (tieneSolucion(estadoInicial)) {

18 BusquedaAnchura.busqueda(estadoInicial);

19 } else {

20 System.out.println("El estado inicial insertado no tiene solucion , el

numero de sus inversiones es impar");

21 }

22

23 System.exit(-1);

24 }

25

26 public static boolean tieneSolucion(int[] estado) {

27

28 int numeroDeValores = estado.length; // 9

29 int dim = (int) Math.sqrt(numeroDeValores); // 3

30 int inversiones = 0;

31

32 for (int i = 0; i < numeroDeValores; ++i) {

33 int iValor = estado[i];

34 if (iValor != 0) {

35 for (int j = i + 1; j < numeroDeValores; ++j) {

36 int jValor = estado[j];

37 if (jValor != 0 && jValor < iValor) {

38 ++ inversiones;

39 }

40 }

41 } else {

42 if (! esImpar(dim)) {

43 inversiones += (1 + i / dim);

44 }

45 }

46 }

47

48 if (esImpar(inversiones)) {

49 return false;

50 }

51 return true;

52 }

53

54 // funcion que indica que si el numero es impar

55 public static boolean esImpar(int iNumero) {

56 if (iNumero % 2 != 0) {

57 return true;

58 } else {

59 return false;

60 }

61 }

62

63 }

1 CLASE 2 NODO:

2


4

5 public class Nodo {

6

7 private Estado estadoActual;

8 private Nodo padre;

9 private double costo; // este es el costo para llegar a este estado

10

11 public Nodo(Estado s) {

12 estadoActual = s;

13 padre = null;

14 costo = 0;

15 }

16

17 public Nodo(Nodo prev , Estado s, double c) {

18 padre = prev;

19 estadoActual = s;

20 costo = c;

21 }

22

23 public Estado getEstadoActual () {

24 return estadoActual;

25 }

26

27 public Nodo getPadre () {

28 return padre;

29 }

30

31 public double getCosto () {

32 return costo;

33 }

34

35 }

1 CLASE 3 ESTADO FINAL:

2


4

5 import java.util.ArrayList;

6 import java.util.Arrays;

7

8 public class EstadoFinal implements Estado {

9

10 private final int TOTALPOSICIONES = 9;

11

12 private final int[] OBJETIVO = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 0};

13 private int[] matrizActual;

14

15 public EstadoFinal(int[] matriz) {

16 matrizActual = matriz;

17 }

18

19 // Costo que se le asocia por llegar a este Estado

20 public double getCosto () {

21 return 1;

22 }

23

24 /*

25 * cuenta los valores fuera de lugar

26 */

27 private int getVacio () {

28 int vacioIndex = -1;

29

30 for (int i = 0; i < TOTALPOSICIONES; i++) {

31 if (matrizActual[i] == 0) {

32 vacioIndex = i;

33 }

34 }

35 return vacioIndex;

36 }

37

38

39 /*

40 * devuelve una copia de la matriz que se le pase como parametro

41 */

42 private int[] copiaMatriz(int[] state) {

43 int[] ret = new int[TOTALPOSICIONES ];

44 for (int i = 0; i < TOTALPOSICIONES; i++) {

45 ret[i] = state[i];

46 }

47 return ret;

48 }

49

50 public ArrayList <Estado > generadorNuevosEstados () {

51 ArrayList <Estado > hijos = new ArrayList <Estado >();

52 int vacio = getVacio ();

53

54 // izquierda

55 if (vacio != 0 && vacio != 3 && vacio != 6) {

56 intercambiaGuarda(vacio - 1, vacio , hijos);

57 }

58

59 // abajo


61 intercambiaGuarda(vacio + 3, vacio , hijos);

62 }

63

64 // arriba


66 intercambiaGuarda(vacio - 3, vacio , hijos);

67 }

68 // derecha


70 intercambiaGuarda(vacio + 1, vacio , hijos);

71 }

72

73 return hijos;

74 }

75

76 // copia la matriz y luego en la copia cambia los

77 // valores. Despues guarda el nuevo estado

78 private void intercambiaGuarda(int d1 , int d2, ArrayList <Estado > hijos) {

79 int[] copia = copiaMatriz(matrizActual);

80 int temp = copia[d1];

81 copia[d1] = matrizActual[d2];

82 copia[d2] = temp;

83 hijos.add((new EstadoFinal(copia)));

84 }

85

86 // compara el estado actual con el objetivo

87 public boolean isObjetivo () {

88 if (Arrays.equals(matrizActual , OBJETIVO)) {

89 return true;

90 }

91 return false;

92 }

93

94 public void ImprimeEstado () {

95

96 System.out.println(matrizActual [0] + " | " + matrizActual [1] + " | "

97 + matrizActual [2]);

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



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



104 System.out.println(" ");

105 System.out.println(" ");

106

107 }

108

109 public boolean equals(Estado s) {

110 if (Arrays.equals(matrizActual , (( EstadoFinal) s).getMatrizActual ())) {

111 return true;

112 } else {

113 return false;

114 }

115

116 }

117

118 public int[] getMatrizActual () {

119 return matrizActual;

120 }

121

122 }

1 CLASE 4 ESTADO:

2


4


6

7 public interface Estado {

8

9 boolean isObjetivo ();

10

11 // generate successors to the current state

12 ArrayList <Estado > generadorNuevosEstados ();

13

14 // determine cost from initial state to THIS state

15 double getCosto ();

16

17 // print the current state

18 public void ImprimeEstado ();

19

20 // compare the actual state data

21 public boolean equals(Estado s);

22 }

1 CLASE 5 BUSQUEDA ANCHURA:

2


4


6 import java.util.LinkedList;

7 import java.util.Queue;

8 import java.util.Stack;

9

10 public class BusquedaAnchura extends BusquedaNormal {

11

12 static long tiempoInicio = System.currentTimeMillis ();

13 static long totalTiempo = System.currentTimeMillis () - tiempoInicio ;

14

15 public static void busqueda(int[] matriz) {

16 Nodo root = new Nodo(new EstadoFinal(matriz));

17 Queue <Nodo > queue = new LinkedList <Nodo >();

18 queue.add(root);

19

20 realizarBusqueda(queue);

21 }

22

23 public static void realizarBusqueda(Queue <Nodo > q) {

24 int contadorIteraciones = 1; // cuenta las veces que se a entrado al metodo

25

26 while (!q.isEmpty ()) // revisa si la cola no esta vacia

27 {

28 Nodo tempNodo = (Nodo) q.poll();

29

30 if (! tempNodo.getEstadoActual ().isObjetivo ()) // si no es nodo buscado ,

pedimos generar sus hijos.

31 {

32 ArrayList <Estado > tempHijos = tempNodo.getEstadoActual ()

33 .generadorNuevosEstados ();

34

35 // recorro los estados hijos para convertirlos en nodos.

36 for (int i = 0; i < tempHijos.size(); i++) {

37 // paso los costos para ir sumandolos

38

39 Nodo newNodo = new Nodo(tempNodo ,

40 tempHijos.get(i), tempNodo.getCosto ()

41 + tempHijos.get(i).getCosto ());

42

43 //busco si de los nuevos sucesores tengo

repetidos

44 //para agregarlos a la cola

45 if (! revisaRepetidos(newNodo)) {

46 q.add(newNodo);

47 newNodo.getEstadoActual ().ImprimeEstado ();

48 contadorIteraciones ++;

49 }

50 }

51 // cuento cuantas veces he buscado

52

53 } else // si encontramos el objetivo

54 {

55 // se usa la estructura stack para guardar desde

56 // el estado inicial al estado objetivo.

57 Stack <Nodo > rutaSolucion = new Stack <Nodo >();

58 rutaSolucion.push(tempNodo);

59 tempNodo = tempNodo.getPadre ();

60

61 while (tempNodo.getPadre () != null) {


63 tempNodo = tempNodo.getPadre ();

64 }


66

67 int tamanoRuta = rutaSolucion.size();

68

69 for (int i = 0; i < tamanoRuta; i++) {

70 tempNodo = rutaSolucion.pop();

71 tempNodo.getEstadoActual ().ImprimeEstado ();

72 System.out.println ();

73 System.out.println ();

74 }

75 // impresion de las iteraciones y mas cosas

76 // System.out.println ("Es costo total es de: " + tempNodo.getCosto ()

);

77 System.out.println("El numero de iteraciones es de: " +

contadorIteraciones);

78 // System.out.println ("El tiempo total es de:"+ totalTiempo);

79 System.exit (0);

80 }

81 }

82 //sino se imprime que no tiene solucion la busqueda

83 System.out.println("Sin Solucion en esta tecnica !!!!!");

84 }

85

86 }

1 CLASE 6 BUSQUEDA NORMAL:

2


4

5 public abstract class BusquedaNormal {

6

7 public static boolean revisaRepetidos(Nodo n) {

8 boolean retValue = false;

9 Nodo checkNode = n;

10

11 while (n.getPadre () != null && !retValue) {

12

13 if (n.getPadre ().getEstadoActual ().equals(checkNode.getEstadoActual ()))

{

14 retValue = true;

15 }

16 n = n.getPadre ();

17 }

18

19 return retValue;

20 }

21 }

2. BUSQUEDA HILL CLIMBING:

3. Analisis de resultados

Como analisis de resultados se puede apreciar que el uso de estos algoritmos o busquedas dan como re-sultado las siguientes salidas en la consola en la forma de su implementación:

BUSQUEDA EN ANCHURA:

Salida 1:

Imagen 1 de la consola como base o prueba.

Salida 2:

Imagen 2 de la consola como base o prueba.

4. Conclusiónes

Como conclusión se puede mencionar que el uso de estas estrategias de busqueda u algoritmos se usaronde manera que en el juego del 8 puzzle ver cual de todas las iteraciones que se hacen en el juego, ir probandocual es la menor y la mayor en su optimización, el tiempo y el costo de cada cambio de estos estados en lasmatrizes hijos que vienen de un padre o matriz de entrada, al igual que tambien cual de estas 2 busquedas oalgoritmos es el mejor o el peor.Tambien se puede mencionar el uso del paradigma y lenguaje en java fue algo nuevo ya que se aplico almaximo los concimientos basicos como avanzados para la realización del proyecto, tanto que todo partiodesde las sentencias que se manejan para el manejo de las clases, hasta lo que es el paso de las lineas ocomentarios de un programa o variables, como trabajo futuro se puede mencionar que se puede mejorar esteproyecto ya que se cubrio cierta parte, pero se puede hacer mas complejo y con mucho mejor funcionamientotanto como para ambos algoritmos, ya que es muy importante para todo aquello que se requiera manejar endistintas practicas o proyectos.

5. Fuentes de información

A continuación se muestran la bibliografía o las fuentes de donde se recopilo la información de las bus-quedas o los algoritmos:

Fuentes:

6. Fuentes de Anexos

En este apartado pues se puede anexar un pequeño fragmento de como funciona ambos algoritmos obusquedas para que si no queda algo claro, se pueda entender y aplicar de diferente manera el uso de estasmismas.

BUSQUEDA EN ANCHURA:En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algo-ritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, secomienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos losvecinos de este nodo.A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta quese recorra todo el árbol.Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos deun árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.Si las aristas tienen pesos negativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos versiones.

Imagen de la busqueda o algoritmo de anchura.

BUSQUEDA HILL CLIMBING:En ciencia de la computación, hill climbing (ascenso de colinas, en alguna literatura) es una técnica deoptimización matemática que pertenece a la familia de los algoritmos de búsqueda local. Es un algoritmoiterativo que comienza con una solución arbitraria a un problema, luego intenta encontrar una mejor soluciónvariando incrementalmente un único elemento de la solución. Si el cambio produce una mejor solución, otrocambio incremental se le realiza a la nueva solución, repitiendo este proceso hasta que no se puedan encontrarmejoras.La relativa simplicidad de este algoritmo lo hace una primera elección popular entre los algoritmos de optimi-zación. Es usado ampliamente en inteligencia arti�cial, para alcanzar un estado �nal desde un nodo de inicio.La elección del próximo nodo y del nodo de inicio puede ser variada para obtener una lista de algoritmos dela misma familia. Aunque algoritmos más avanzados tales como simulated annealing o búsqueda tabú puedendevolver mejores resultados, en algunas situaciones hill climbing opera sin diferencias. El hill climbing confrecuencia puede producir un mejor resultado que otros algoritmos cuando la cantidad de tiempo disponiblepara realizar la búsqueda es limitada, por ejemplo en sistemas en tiempo real. El algoritmo puede devolveruna solución válida aún si es interrumpido en cualquier momento antes de que �nalice.

Imagen de la busqueda o algoritmo de hill climbing.

Reporte miguel angel_garcia_wha

Technology

Transcript of Reporte miguel angel_garcia_wha