busquedas heuristica

Búsquedas
heurísticas
Abraham Sánchez López
FCC/BUAP

(C) A. Sánchez L. 2011

1

Introducción
Problemas que no poseen una solución exacta.
Problemas que dan lugar a una explosión combinatoria.
Aplicar un método de búsqueda exhaustiva en ambos tipos de
problemas resulta ineficiente. El número de nodos a expandir es muy
grande, lo que acaba con los recursos de tiempo y memoriadisponibles.
La exploración del espacio de estados puede verse reducida por el uso
de información peculiar asociada a cada problema concreto.
En la mayoría de los casos esta información se obtiene de la
experiencia y de las características específicas de cada problema.
A este tipo de información se le llama información heurística.

(C) A. Sánchez L. 2011

2

Búsqueda informada
Búsquedaciega o no informada (anchura, profundidad,. . . ): no
cuenta con ningún conocimiento sobre como llegar al objetivo.
Búsqueda informada: aplicar conocimiento al proceso de
búsqueda para hacerlo mas eficiente.
El conocimiento estará dado por una función que estima la
“bondad” de los estados:
Utilizar una estimación del costo de la solución para guiar la
búsqueda.
Dar preferencia a los mejoresestados.
Ordenando la cola de ABIERTOS, comparando su bondad estimada.
Objetivo: podar el espacio de búsqueda, ganando eficiencia en la
practica.
No siempre garantizan el óptimo, ni una solución.

(C) A. Sánchez L. 2011

3

Concepto de heurística
Heurística:
Del griego heuriskein, descubrir: !Eureka¡
Según el diccionario: “Técnica de la indagacion y del descubrimiento”
Otrosignificado: método para resolver problemas que no garantizan la
solución, pero en general funciona bien.
En nuestro caso, una heurística será una función numérica sobre los
estados.

Función de evaluación heurística, heurística(estado):
Estima la “distancia” al objetivo
Siempre mayor o igual que 0
Valor en los estados finales: 0
Se admite el valor ∞

Todo el conocimiento específico sobre elproblema está codificado en
la función heurística.

(C) A. Sánchez L. 2011

4

Problema del viajero

Partida:
Puebla
Llegada:
Ajalpan

(C) A. Sánchez L. 2011

5

Ejemplos de heurística
Problema del paseo:

heurística(estado) = |estado - *estado-final*|
Problema del agente viajero por Puebla
Coordenadas:
Puebla : (409.5 93 )
Atlixco : (309 127.5)
Cholula : (232.5 75 )
SanMartín: ( 63 57 )
Tehuacan: ( 3 139.5)
Zacatlan : ( 90 153 )
Izúcar : (198 207 )
Teziutlan : (295.5 192 )
Función de evaluación heurística (distancia en línea recta):
heurística(estado) = distancia(coordenadas(estado),coordenadas(Puebla))

(C) A. Sánchez L. 2011

6

Heurísticas para el 8-puzzle
Heurística(estado)=“número de piezas mal colocadas respecto de su
posición en el estadofinal”

Heurística(estado)=“suma de las distancias Manhattan de cada pieza a
donde debería estar en el estado final”

(C) A. Sánchez L. 2011

7

Búsqueda bidireccional
En este tipo de búsqueda se llevan a la vez dos búsquedas: una
descendente desde el nodo inicial y otra ascendente desde el nodo
final.
Al menos una de estas búsquedas, debe ser en anchura para que el
recorridoascendente y descendente puedan encontrarse en algún
momento.
Es importante considerar que los operadores deben ser reversibles, los
conjuntos de predecesores y sucesores son iguales, pero hay casos en
los cuales, calcular los predecesores es muy difícil.

(C) A. Sánchez L. 2011

8

Algoritmo de la búsqueda bidireccional
Procedimiento Bidireccional (Estado-inicial Estado-final)
1. ABIERTA-I= Estado-inicial, ABIERTA-M = Estado-final, EXITO = Falso
2. Hasta que alguna de ABIERTA-I o ABIERTA-M estén vacías o ÉXITO
Quitar de ABIERTA-I el primer nodo, N
Generar sucesores de N, introducirlos en ABIERTA-I
Si algún sucesor de N equipara con algún elemento de ABIERTA-M
Entonces EXITO = Verdadero
Si no quitar de ABIERTA-M el primer nodo M
Generar sucesores de M, introducirlos en...