Algoritmos geneticos

Búsqueda Heurística I

Pedro Meseguer IIIA-CSIC Bellaterra, Spain pedro@iiia.csic.es

Temario curso
• Introducción • Búsqueda sistemática
• • • • • Búsqueda ciega Búsqueda informada: primero elmejor, A* Búsqueda en memoria acotada Búsqueda con adversario (juegos) Búsqueda en tiempo real

• Búsqueda local
• Vecindad • Función de evaluación • Criterios de salto
Búsqueda Heurística 2Parámetros
• Curso 22 horas • Nivel: postgraduado
• es autocontenido •se supone un cierto conocimiento del tema

• Transparencias: www.iiia.csic.es/~pedro/

• Clases :
• jueves de 15 a 17, IIIA• Calendario:
• Evaluación: examen
• de conceptos generales • no es muy duro, pero ... • ... se suspende • Octubre: 26 • Noviembre: 2, 9, 16, 23, 30 • Diciembre: 14, 21 • Enero: 18 • Febrero: 1,8 (EXAMEN)
Búsqueda Heurística 3

a confirmar en Navidad

¿Qué es búsqueda?
• Búsqueda: método computacional para resover problemas • ¿Qué problemas?
• single-agent path-finding: único agenteencuentra camino • two-player games: juegos de dos jugadores • constraint satisfaction: satisfacción de restricciones

• Características:
• problemas difíciles: NP-completos • la solución secalcula por enumeración • se supone que requieren inteligencia → Inteligencia Artificial
Búsqueda Heurística 4

Ejemplos
single-agent path-finding constraint satisfaction

PUZZLE de 8
1 4 6 7 5 2 38

8 REINAS
3 4 5

?

1 2 8 7 6

two-player games

AJEDREZ
movimientos que llevan a situación ganadora
Búsqueda Heurística

poner 8 reinas de ajedrez en un tablero 8x8 y que no seataquen
5

Conceptos básicos

espacio del problema

• Estado: una posible configuración de un problema • Espacio de estados: todas las configuraciones • Operadores:
• acciones legales • generanestados sucesores de un estado

• Estados inicial
explícito

y

objetivo
puede ser implícito

problema concreto

• Solución:
• secuencia operadores de inicial a objetivo: path-finding,...