BUSQUEDA PRIMERO EN ANCHURA

Fecha de clase: 27/mayo/2014

BÚSQUEDA PRIMERO EN ANCHURA

Se convierte en una cola (o fila de espera) que expande primero el nodo raíz, posteriormente todos los sucesores del nodo raíz, después sus sucesores, etc., expandiendo todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel (Russell y Norvig. 2004).

Los nodos de igual profundidad se ordenan arbitrariamente. Ese orden arbitrario es directamente heredado del que exista entre los operadores del sistema de producción. Mediante esta estrategia, el árbol de búsqueda se va generando por niveles de profundidad. Hasta que todos los nodos de un nivel no han sido revisados no se revisa ninguno del siguiente nivel (Rubio et al. 1998); es decir, cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)  

Las búsquedas a ciegas aplican los operadores (modelos de los efectos de las acciones, que al aplicarlos crean nodos sucesores) sin conocer bien el problema. La búsqueda por anchura es el método más simple de búsquedas a ciegas.  Este procedimiento actúa de forma uniforme construyendo un grafo de estados explícito desde el nodo inicial a cada uno de los predecesores con la propiedad de que una vez encontrado el nodo objetivo, se habrá encontrado el camino más corto, pero para esto tiene que almacenar el árbol completo y esto es un inconveniente puesto que el tamaño crece de manera exponencial respecto a la profundidad del nodo objetivo (menos profundo) (Nils, J. 2001)

Russell y Norvig (2004) puntualiza el siguiente punto que se debe considerar antes de elegir un método de búsqueda:

-          La cantidad de tiempo y memoria que utiliza para completar una búsqueda.

-          Son un problema más grande los requisitos de memoria para realizar una búsqueda por anchura que el tiempo de ejecución. Pero existen otras estrategias que requieren menos memoria.

-          Los problemas de búsqueda de complejidad exponencial no pueden resolverse por métodos a ciegas (sin información) salvo los casos pequeños.

A continuación se expresa el método de búsqueda primero en anchura utilizando un puzzle de 8 piezas, en el que se muestra el nodo inicial y el nodo objetivo, así mismo el orden como se genera un árbol de búsqueda mediante el uso de los operadores (mover la celda vacía a la izquierda, arriba, a la derecha y abajo) y la solución óptima para llegar al objetivo.   

Figura 1. Búsqueda primero en anchura para un puzzle de ocho piezas

Autor: Nils, J. (2001)

Si un estado objetivo es alcanzable, la búsqueda en anchura lo encuentra. La demostración es sencilla: el estado objetivo aparecerá en un cierto nivel de profundidad y, en un número finito de pasos (suponiendo un número finito de operadores y un número finito de posibles aplicaciones de un operador sobre un estado), llegará a ese nivel. Este mismo razonamiento muestra que la búsqueda en anchura siempre encuentra la secuencia solución más corta (una de las que tienen el mínimo número de aristas). Pero esto no significa en absoluto que realice un número pequeño de operaciones. Se trata de una propiedad de la secuencia solución encontrada, no del proceso por el que ha sido construida; de hecho, la búsqueda en anchura puede llegar a ser extremadamente ineficaz. (Rubio et al. 1998)

BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf