Inteligencia Artificial

Introducción

Heurística

Búsqueda primero el mejor

Coste y búsqueda óptima

Tema 4: Búsqueda informada mediante
técnicas heurísticas
José Luis Ruiz Reina
José Antonio Alonso
Franciso J. Martín Mateos
1 Departamento

de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla

Inteligencia Artificial I, 2011

Búsqueda A∗

Introducción

HeurísticaBúsqueda primero el mejor

Índice

Introducción
Heurística
Búsqueda primero el mejor
Coste y búsqueda óptima
Búsqueda A∗

Coste y búsqueda óptima

Búsqueda A∗

Introducción

Heurística

Búsqueda primero el mejor

Coste y búsqueda óptima

Búsqueda A∗

Búsqueda informada
• Búsqueda ciega o no informada (anchura,

profundidad,. . . ): no cuenta con ningún conocimiento
sobrecómo llegar al objetivo.
• Búsqueda informada: aplicar conocimiento al proceso de

búsqueda para hacerlo más eficiente.
• El conocimiento vendrá dado por una función que estima

la “bondad” de los estados:
• Dar preferencia a los estados mejores.
• Ordenando la cola de ABIERTOS, comparando su bondad

estimada.
• Objetivo: reducir el árbol de búsqueda, ganando eficiencia

en la práctica.Introducción

Heurística

Búsqueda primero el mejor

Coste y búsqueda óptima

Búsqueda A∗

Concepto de heurística
• Heurística:
• Del griego heuriskein, descubrir: ¡Eureka!
• Según el DRAE: “técnica de la indagación y del

descubrimiento”.
• Otro significado: método para resolver problemas que no

garantiza la solución, pero que en general funciona bien.
• En nuestro caso, unaheurística será una función numérica

sobre los estados.
• Función heurística, heurística(estado):
•
•
•
•

Estima la “distancia” al objetivo.
Siempre mayor o igual que 0.
Valor en los estados finales: 0.
Admitimos valor ∞.

• Todo el conocimiento específico que se va a usar sobre el

problema está codificado en la función heurística.

Introducción

Heurística

Búsqueda primeroel mejor

Coste y búsqueda óptima

Búsqueda A∗

Recordar: problema del viaje por Andalucía

• Ir de Sevilla a Almería, mediante una secuencia de

desplazamientos a capitales de provincia fronterizas
• 8 posibles estados:
• Almería, Cádiz, Córdoba, Granada, Huelva, Jaen, Málaga,

Sevilla
• Estado inicial: Sevilla.
• Estado final: Almeria.
• Operadores:
• Ir a Almería, Ir a Cádiz,Ir a Córdoba, Ir a Granada, Ir a

Huelva, Ir a Jaén, Ir a Málaga, Ir a Sevilla.

Introducción

Heurística

Búsqueda primero el mejor

Coste y búsqueda óptima

Una heurística para el problema del viaje

• Coordenadas:
Almeria
Granada
Malaga
Cadiz
Huelva
Sevilla
Cordoba
Jaen

:
:
:
:
:
:
:
:

(409.5
(309
(232.5
( 63
(3
( 90
(198
(295.5

93 )
127.5)
75 )57 )
139.5)
153 )
207 )
192 )

• Función heurística (distancia en línea recta):
heurística(estado) =
distancia(coordenadas(estado),
coordenadas(almeria))

Búsqueda A∗

Introducción

Heurística

Búsqueda primero el mejor

Coste y búsqueda óptima

Búsqueda A∗

Recordar: problema del 8-puzle
• Un tablero cuadrado (3x3) en el que hay situados 8

bloques cuadrados numerados(con lo cual se deja un
hueco del tamaño de un bloque). Un bloque adyacente al
hueco puede deslizarse hacia él. El juego consiste en
transformar una posición inicial en la posición final
mediante el deslizamiento de los bloques. En particular,
consideramos el estado inicial y final siguientes:
2

8

3

1

1

6

4

8

5

7

7

Estado inicial

2

3

6

5

4Estado final

• Estados: cada una de las posibles configuraciones del

tablero
• Operadores: arriba, abajo, izquierda, derecha

(movimientos del hueco)

Introducción

Heurística

Búsqueda primero el mejor

Búsqueda A∗

Coste y búsqueda óptima

Primera heurística en el problema del 8–puzle

• Problema del 8-puzle (primera heurística):
• heurística(estado): número de piezas...