SOLUCIÓN DE PROBLEMAS.

La resolución de problemas es fundamental para la mayoría de las aplicaciones de Inteligencia artificial. De hecho la capacidad de resolver problemas suele usarse como una medida de la inteligencia tanto para el ser humano como para la computadora.

El proceso general de un sistema de Resolución de Problemas en IA, se modela generalmente como un proceso de búsqueda a través de un espacio de estados.

Definición del problema

a) Definir una representación de posibles estados del problema.

b) Determinación de un estado inicial.

c) Determinación explicita del estado final meta, o de las condiciones de un estado meta.

d) Reglase de transición o de movimiento: Permiten transformar un estado del problema en otro.

Objetivo: encontrar las secuencias de reglas (solución) que aplicadas a una descripción del problema (estado inicial) lo transformen en otra (estado meta), mediante un proceso de búsqueda en un proceso de estados.

Espacios de estados: Conjunto de estados del problema alcanzables a partir del estado inicial, aplicando reglas de transición. Un espacio de estado es un grafo cuyos nodos corresponden a estados del problema. De este modo, utilizando está representación, la solución a los problemas se convierte en la búsqueda de caminos ó rutas óptimas dentro del grafo.

SISTEMA DE PRODUcCIÓN.

Debido a que la búsqueda es el núcleo de muchos procesos inteligentes, es adecuado estructurar los programas de IA de forma que facilite describir y desarrollar el proceso de búsqueda. Los sistemas de producción  proporcionan tales estructuras. Un sistema de producción consiste en:

·       * Un conjunto de reglas.

·        *Una o más bases de datos (conocimiento)

·        *Una estrategia de control que especifique el orden en el que las reglas comparan con la base de datos, y la forma de resolver los conflictos que surjan cuando varias pueden, ser aplicada a la vez.

·       * Un aplicador de reglas.

El proceso de solución del problema puede modelarse como un sistema de producción. El problema que se plantea es escoger la estructura de control apropiada para el sistema de producción con el fin de que el proceso de búsqueda sea lo más eficiente posible.

BÚSQUEDA EN AMPLITUD O EN ANCHURA (Breadth-first Search).

Se basa en desarrollar completamente cada nivel del árbol antes de pasar a desarrollar el siguiente. La búsqueda de amplitud no queda atrapada explorando callejones sin salida, además si existe una solución la búsqueda en anchura garantiza que se encuentre. Si existe múltiples soluciones se encuentra las solución mínima, es decir, la que requiere el mínimo numero de pasos. Este algoritmo de búsqueda visita cada nodo del árbol por niveles, es decir visita los nodos de un nivel antes de visitar los del siguiente.  El pseudo-codigo de este algoritmo.

BUSQUEDA EN PROFUNDIDAD (Depth- First Search).

Este algoritmo de búsqueda continua por una rama del árbol hasta encontrar la solución o decidir terminar la búsqueda por esa dirección porque se encontró un callejón sin salida .  Al fracasar una ruta, se realiza un backtracking o vuelta atrás, continuando la exploración en el paso inmediato anterior.  La búsqueda en profundidad necesita menos memoria ya que solo almacena los nodos del camino que se siguen en ese instante. Esto contrasta con la búsqueda en anchura en la cual se debe almacenarse todo el árbol que haya sido generado hasta ese momento. A continuación se detalla el pseudo-codigo.

http://www.unistmo.edu.mx/~daniel.garcia/unidadiii_ia.pdf
http://revistas.utp.edu.co/index.php/revistaciencia/article/viewFile/3171/1933
file:///C:/Users/juliO/Downloads/T2.pdf
http://dmi.uib.es/~abasolo/intart/1-introduccion.html
http://www.slideshare.net/alanl0pez/tipos-de-bsqueda-en-inteligencia-artificial