Algoritmos de busqueda

Apunte
Inteligencia Artificial

Indice

1.- Introducción

1.1- Breve historia
1.2.- Definición
1.3.- Intereses de la Inteligencia Artificial

2.- Representación de problemas

2.1.- Aspectos básicos
2.2.- Tipos de problemas

2.2.1.- Problemas de sentido común
2.2.2.- Problemas de demostración de conjeturas
2.2.3.- Juegos y rompecabezas3.- Técnicas de Inteligencia Artificial

3.1.- Introducción
3.2.- Métodos de búsqueda no informados

3.2.1.- Irreversible
3.2.2.- Backtracking
3.2.3.- Búsqueda en anchura
3.2.4.- Búsqueda en profundidad
3.2.5.- Búsqueda inversa
3.2.6.- Complejidad

3.3.- Métodos de búsqueda informados
3.3.1.- Algoritmo BF*
3.3.2.- Algoritmo A*

3.4.- Hipergrafos
3.4.1.-Definición y aplicaciones
3.4.2.- Algoritmo AO*

4.- Arboles de juegos
4.1.- Introducción
4.2.- Procedimiento MINIMAX
4.3.- Procedimiento ALFABETA (∂-ß)

5.- Representación del conocimiento con Lógica de Predicados
5.1.- Conceptos, definiciones y notación
5.2.- Resolución
5.3.- Refutación
5.4.- Transformación a cláusulas
5.5.- Unificación
5.6.- Deducción basada en reglas1.- Introducción

1.1.- Reseña histórica

Aunque la Inteligencia Artificial comienza a ser estudiada solamente en las últimas décadas, existen algunos autores que con una visión generalista encuentran el origen real hace algunos miles de años atrás, lo que tiene mucho sentido si se considera las definiciones que veremos posteriormente. En la primera aparecen conceptos asociados a los sereshumanos (inteligencia) o en general a los seres vivos que se remontan al inicio del hombre, tal como la actitud innata de imitar al ser humano. En este sentido es que a la Inteligencia Artificial se le puede buscar sus orígenes muchos siglos atrás. En particular Pazos (1987) inicia su análisis en el "Egipto de los Faraones", donde pequeñas estatuas reproducían los movimientos cotidianos máshabituales, siendo la reseña histórica por él contada la siguiente:

* Invención de todo tipo de mecanismos automáticos, combinando pistones, sifones, resortes, etc.
(Grecia en época Alejandrina : se destacan Ctesibios, Filón, Demetrio, Arquímides, Architas y Herón)

* En la mitología griega aparece la primera referencia a un androide : Talos un gigantesco robot que defendía aCreta de sus enemigos o Hefaisto dios del fuego construyó dos androides femeninos en oro masizo (Ver la Iliada de Homero).

* Edad Media.- El Golem, un ser artificial de barro a quien su dueño, el rabino Judio de Praga, en ceremonia secreta y mágica dotaba de vida. Fué un elemento importante en la protección de la ciudad del emperador Rodolfo.

* Edad Moderna (2a mitad del sigloXVIII).- Droz construye 3 androides en tamaño natural, dos niños y una niña. Accionados por mecanismos de relojería, uno de ellos escribía mensajes de hasta 40 caracteres. Otro hacía diversos dibujos y Marianne la niña tocaba un órgano real (Visitar Museo de Suiza en Neuchatel).

Construcción de una Máquina Automática (Pascal y Leibnitz)

Estos antecedentes forman parte de la inagotablecreatividad del ser humano, que a través de la historia ha permitido la evolución tecnológica, detacando la característica de representar, en alguna forma, con materiales inorgánicos parte de la inteligencia del ser humano.
Sin embargo, Pazos (1987) identifica un "punto de inflección" en lo que es el avance en el estudio de la Inteligencia Artificial. Este se localiza en el año 1943, cuando fueronpublicados tres artículos teóricos que serían los que dieron origen a la Cibernética.
En el primero Wiener, Rosenbleut y Bigelow en el MIT sugirieron diferentes formas de conferir fines y propósitos a las máquinas. En el segundo, McCulloch (del Colegio de Medicina de la Universidad de Illinois) y Pits (matemático del MIT) pusieron de manifiesto la manera en que las máquinas podían emplear los...