Inteligencia Artificial Ejemplo

`
Intel.ligencia
Artificial

`
Enginyeria en Informatica

`
APUNTS D’INTEL.LIGENCIA
ARTIFICIAL

`
Departament de Llenguatges i Sistemes Informatics

CURS 2010/2011 1Q

cbea

This work is licensed under the Creative Commons
Attribution-NonCommercial-ShareAlike License. cbea
To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.0/ or
send aletter to:
Creative Commons,
559 Nathan Abbott Way, Stanford,
California 94305,
USA.

Índice general

0. Introducción

1

I

3

Resolución de problemas

1. Resolución de problemas
1.1. ¿Qué es un problema? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. El espacio de estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.Algoritmos de búsqueda en el espacio de estados . . . . . . . . . . . . . . . . . . . . .
2. Búsqueda no informada
2.1. Búsqueda independiente del problema
2.2. Búsqueda en anchura prioritaria . . .
2.3. Búsqueda en profundidad prioritaria
2.4. Búsqueda en profundidad iterativa .
2.5. Ejemplos . . . . . . . . . . . . . . . .
3. Búsqueda heurística
3.1. El conocimiento importa . . . . .
3.2.El óptimo está en el camino . . .
3.3. Tú primero y tú después . . . . .
3.4. El algoritmo A∗ . . . . . . . . . .
3.5. Pero, ¿encontraré el óptimo? . . .
3.5.1. Admisibilidad . . . . . . .
3.5.2. Consistencia . . . . . . . .
3.5.3. Heurístico más informado
3.6. Mi memoria se acaba . . . . . . .
3.6.1. El algoritmo IDA∗ . . . .
3.6.2. Otras alternativas . . . . .

.
.
.
.
.
.
.
..
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

4. Búsqueda local
4.1. El tamaño importa, a veces . . . . . .
4.2. Tu sí, vosotros no . . . . . . . . . . . .
4.3. Demasiado calor, demasiado frío . . . .
4.4. Cada oveja con su pareja . . . . . . . .
4.4.1. Codificación . . . . . . . . . . .
4.4.2. Operadores . . . . . . . . . . .
4.4.3.Combinación de individuos . . .
4.4.4. El algoritmo genético canónico .
4.4.5. Cuando usarlos . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
..
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
..
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
....