MÉTODOS DE BÚSQUEDA Y EJEMPLOS PRÁTICOS

 

¿Qué es búsqueda?
 

Es el Método computacional para resolver problemas.

Las técnicas de búsqueda son una serie de esquemas de representación del conocimiento, que mediante diversos algoritmos nos permite resolver ciertos problemas desde el punto de vista de la I.A.
 

¿Qué son las técnicas de búsqueda y cuáles son sus elementos?
 

Conjunto de estados: todas las configuraciones posibles en el dominio.

 

Estados iniciales: estados desde los que partimos.

Estados finales: las soluciones del problema.

Operadores: se aplican para pasar de un estado a otro.

                                                                                                      

Tipos de búsqueda

 

1.  Sin información (ciega) 

 

     En pequeños dominios, podemos intentar aplicar todos nuestros métodos de mindless search… pero no es práctico por que la búsqueda se vuelve enorme.
 

      Sólo utiliza información acerca de si un estado es o no objetivo para guiar su proceso de búsqueda.

      

      Definiciones para este tipo de búsqueda:

 

Expandir un nodo: se trata de obtener los posibles hijos de un nodo a partir de la aplicación de los distintos operadores sobre él.

Nodo cerrado: se han aplicado todos los posibles operadores sobre él, obteniéndose todos sus posibles hijos.

Tipos de búsqueda ciega

• Ventajas: tiene menos complejidad espacial que búsqueda en amplitud.
• Desventajas: se pueden encontrar soluciones que están más alejadas de la raíz que otras, existe el riesgo de presencia de bucles infinitos.

·         Búsqueda en amplitud

       

      Se basa en desarrollar completamente cada nivel del árbol antes de pasar a desarrollar el siguiente.

Búsqueda en profundidad

Se basa en elegir un camino en el árbol y seguirlo hasta el final, sino se encuentra la solución se retrocede y se prueba por otro camino.

·         Búsqueda en profundidad progresiva

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.

·         Búsqueda bidireccional

Es básicamente una búsqueda simultánea que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio.

La idea de este método es buscar simultáneamente tanto hacia adelante del estado inicial como hacia atrás de la meta, y parar cuando las dos búsquedas se encuentran en el medio.

 

 2. Con información (Heurística) 

   Para reducir la extensión de la búsqueda desinformada debemos incorporarle tipos adicionales de conocimiento – incorporando experiencia en resolución de problemas durante la tarea de resolución de problemas.

 

Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores.

Son características de los métodos heurísticos:

• No garantizan que se encuentre una solución, aunque existan soluciones.
• Si encuentran una solución, no se asegura que ésta tenga las mejor esas propiedades (que sea de longitud mínima o de coste óptimo).
• En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.
• En general, los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.
• La información del problema concreto que estamos intentando resolver se suele expresar por medio de heurística.
• El concepto de heurística es difícil de aprehender. Newell, Shaw y Simón en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".