Tecnicas De Busqueda.- Inteligencia Artificial

Introducción

La resolución de problemas es fundamental para la mayoría de las aplicaciones de Inteligencia Artificial (IA). De hecho, la capacidad de resolver problemas suele usarse como una medida de la inteligencia tanto para el ser humano como para la computadora. Hay principalmente dos clases de problemas. Una primera clase puede ser resuelta usando algún tipo de procedimiento determinista cuyo éxito esté garantizado.

A este procedimiento se le llama de computación. La resolución por computación normalmente sólo se aplica a aquellos tipos de problemas para los que existan tales procedimientos, como en matemáticas. Se puede con frecuencia traducir los métodos usados para resolver estos problemas de manera fácil, a un algoritmo que pueda ser ejecutado por una computadora 

Existen dos tipos de problemas que se han estado investigando en el área de Inteligencia Artificial: Los denominados problemas de juguete y problemas del mundo real.

Problemas de Juguetes

Un problema de juguete se utiliza para ilustrar o ejercitar los métodos de resolución de problemas. Éstos se pueden describir de forma exacta y concisa. Esto significa que diferentes investigadores pueden utilizarlos fácilmente para comparar el funcionamiento de los algoritmos. Un problema del mundo real es aquel en el que la gente se preocupa por sus soluciones. Ellos tienden a no tener una sola descripción, sin embargo se podría dar la forma general de sus formulaciones.

El mundo de la aspiradora es un problema de juguete, como se vio en la sección previa este problema puede formularse como sigue:

• Espacio de estados: La aspiradora está en una de dos habitaciones, cada una de las cuales puede o no contener suciedad.

• Estado Inicial: Cualquier estado puede designarse como un estado inicial.

• Objetivo o estado final: Cuando todos las habitaciones están limpias;

• Reglas: La aspiradora puede: moverse a la habitación izquierda, moverse a la habitación derecha o aspirar la habitación.

Problemas del Mundo Real

Los problemas de búsqueda de una ruta están definidos en términos de posiciones y transiciones a lo largo de ellas. Los algoritmos de búsqueda de rutas de han utilizado en una variedad de aplicaciones, tales como rutas en redes de computadores, planificación de operaciones militares, y en sistemas de planificación de viajes de líneas aéreas. Estos problemas son complejos de especificar.

La navegación de un robot es una generalización del problema de encontrar una ruta. Más que un conjunto discreto de rutas, un robot puede moverse en un espacio continuo con un conjunto infinito de acciones y estados posibles. Para un robot circular que se mueve en una superficie plana, el espacio es esencialmente de dos dimensiones. Cuando el robot tiene manos y piernas o ruedas que se deben controlar también, el espacio de búsqueda llega a ser de muchas dimensiones.

La secuenciación para el ensamblaje automático por un robot de objetos complejos es factibles. En el problema de ensamblaje, lo principal es encontrar el orden en los objetos a ensamblar. Si se elige un orden equivocado, no habrá forma de añadir posteriormente una parte de la secuencia sin deshacer el trabajo ya hecho. Verificar un paso para la viabilidad de la sucesión es un problema de búsqueda geométrico difícil muy relacionado con la navegación del robot. Así, la generación de sucesores legales es la parte costosa de la secuenciación para el ensamblaje.

Evaluación de una Búsqueda

La evaluación de la eficiencia de una técnica de búsqueda está fuera del alcance de este curso ya que puede ser muy complicada. De hecho, esta evaluación se lleva gran parte de la investigación en IA. Sin embargo, veremos dos medidas elementales que son importantes para obtener una idea de las ventajas y desventajas de utilizar una u otra técnica:

1. La rapidez con que se encuentra la solución.

2. La calidad de la solución.

La Técnica de Búsqueda Primero en Profundidad

Una búsqueda primero en profundidad explora cada camino posible hasta su conclusión antes de intentar otro camino. Esta técnica de búsqueda pertenece a las estrategias de búsqueda no informada, es decir la búsqueda no utiliza más que la información proporcionada por la definición del problema.

Esta estrategia de búsqueda en profundidad puede implementarse a través de una estructura de tipo pila (último en entrar primero en salir) o alternativamente puede aplicarse como una función recursiva que se llama en cada uno de sus hijos.

La búsqueda primero en profundidad tiene unos requisitos muy modestos de memoria. Necesita almacenar sólo un camino desde la raíz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino. Una vez que un nodo se ha expandido, se puede quitar de la memoria tan pronto como todos sus descendientes han sido explorados.

La Técnica de Búsqueda Primero en Amplitud

La búsqueda primero en amplitud o en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los

...