Sistemas inteligentes

´ 1. INTRODUCCION A LA INTELIGENCIA ARTIFICIAL 1.1. ¿Qu´ es la Inteligencia Artificial? . . . . . . . . . . . . . . . e 1.2. Historia de la IA . . . . . . . . . . . . . . . . . . . . . . . . 1.3. El Test de Turing . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Inteligencia Humana vs Inteligencia Artificial . . . . . . . . . . . . . . . . . . . . 1.5. Herramientas derivadas de la InteligenciaArtificial . . . . . . . . . . . . . . . . . . . . . . ´ 2. PROBLEMAS Y SU CLASIFICACION 2.1. Problemas tratables e intratables . . . . . . 2.2. Maquinas de Turing . . . . . . . . . . . . . . 2.3. Problemas P y NP . . . . . . . . . . . . . . 2.4. Problemas NP completos . . . . . . . . . . . 2.5. Problemas t´ ıpicos de la Inteligencia Artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 1 1 5 8

. . .

. 10 . 11 . . . . . 13 13 17 22 23 25

´ ´ 3. METODOS HEUR´ ISTICOS Y DE BUSQUEDA PARA SOLU´ DE PROBLEMAS CION 35 3.1. Heur´ ıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2. B´ squeda Local . . . . . . . . . . . . . . . . . . . . . . . . . . 37 u 3.3. Algoritmos de B´ squeda Exactos . . . . . . . . . . . . . . . . 39u 3.4. M´todos Heur´ e ısticos . . . . . . . . . . . . . . . . . . . . . . . 45 e 3.4.1. Algoritmos gen´ticos . . . . . . . . . . . . . . . . . . . 45 3.4.2. Colonia de Hormigas . . . . . . . . . . . . . . . . . . . 50 3.4.3. Recocido Simulado . . . . . . . . . . . . . . . . . . . . 54 3.4.4. B´ squeda tab´ . . . . . . . . . . . . . . . . . . . . . . 58 u u u 3.4.5. B´ squeda dispersa . . . . . .. . . . . . . . . . . . . . 64

iii

UAA

´ INDICE GENERAL

iv

´ Indice de figuras
1.1. Prueba de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Secuencia smwm . . . . . . . . . . . . . . . . . . . . . . . . . 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. Espacio del problema . . . . . . . . . . . . . . . . . . . . . . . Representaci´n gr´fica del TSP. . . . . . . . . . . . . . . . . o a Movimientos permitidos de la Reina en el Ajedrez . . . . . . . Reinas por columna . . . . . . . . . . . . . . . . . . . . . . . . Soluciones esencialmente distintas . . . . . . . . . . . . . . . . Ubicaci´n de 8 Transmisores/Receptores sin conflicto entre ellos o Representaci´n gr´fica del problema de Misioneros y Can´ o a ıbales Representaci´n del espacio de b´squeda o u Representaci´n de cromosomas . . . . o Representaci´n del espacio de b´ squeda o u Recocido simulado . . . . . . . . . . . Enfriamiento . . . . . . . . . . . . . . Enfriamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 25 27 28 28 29 30 33 3746 47 56 57 57

v

UAA

´ INDICE DE FIGURAS

vi

´ Indice de tablas
2.1. 2.2. 2.3. 2.4. Tabla comparativa de operaciones . . Tabla comparativa en tiempo . . . . Tabla de Conteo binario . . . . . . . N´ mero total de soluciones Q(n) para u . . . . . . . . . . . . . . . . . . . . . 4 ≤ n ≤ 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 17 21 31

vii

UAA

´ INDICEDE TABLAS

viii

Cap´ ıtulo 1 ´ INTRODUCCION A LA INTELIGENCIA ARTIFICIAL

1.1.

¿Qu´ es la Inteligencia Artificial? e

Antes de intentar responder a la pregunta anterior presentamos un conjunto de definiciones de Inteligencia humana, que es a la que generalmente asociamos el t´rmino, aunque actualmente se reconocen otras acepciones. e a Adem´s, la inteligencia es un concepto tan extensoque solo puede ser descrito en forma aproximada ya que no se ha podido definir en su totalidad. A continuaci´n se listan algunas definiciones de inteligencia que proceden o de varias fuentes [Legg & Hutter, 2007], las primeras son colectivas, es decir, proceden de organizaciones. 1. “Es la capacidad para adquirir y aplicar conocimiento” The American Heritage Dictionary, fourth edition, 2000 2....