Técnicas de Búsqueda Técnicas de Búsqueda HeurísticaHeurística
Curso Inteligencia ArtificialCurso Inteligencia ArtificialProf. Demetrio A. Ovalle C.Prof. Demetrio A. Ovalle C.
Octubre 14 Octubre 14 de 2009de 2009
Técnicas de Búsqueda Técnicas de Búsqueda
HeurísticaHeurística♣ Generación y prueba
♣ Escalada (simple, máxima pendiente)
♣ Verificación de restricciones♣ Verificación de restricciones
♣ Análisis de medios y fines
(Planificación en IA)
♣ Búsqueda el primero mejor, A*
♣ Reducción de problemas
Generación y Prueba
1. Generar una posible solución.
2. Verificar si el objetivo elegido es
una solución al comparar conuna solución al comparar con
objetivo final.
3. Si se ha encontrado la solución,
terminar. Si no volver al paso 1.
Escalada
(Hill Climbing)
• Simple (Hill climbing)
• Máxima pendiente • Máxima pendiente (Steepest ascent hill climbing or
Gradient search)
Escalada Simple
Hill Climbing
• Dirigirse siempre a un estado mejor
que el actual.
• Función heurística de proximidad.• Función heurística de proximidad.
• No se mantiene reporte de estados
anteriores.
• Es un método local. Sus movimientos
están determinados por ser mejores
que los previos.
Búsqueda
• Si existe un sucesor s del estado actual n• Si existe un sucesor s del estado actual nmejor que n, entonces hacer a s como
estado actual. De lo contrario, detener.
• Mirar un paso hacia adelante para
determinar si algún sucesor es mejor que
el estado actual; si lo hay, moverse al
mejor sucesor.
Buscar no solamente un
Escalada por la Máxima Pendiente
(Steepest ascent hill climbing or
Gradient search)
Buscar no solamente un
estado mejor que el actual,
sino el mejor de todos estos
estados posibles (Máxima
pendiente).
Dificultades
de la EscaladaDificultad
• Máximo local.
Posible Solución
• Backtrack.• Máximo local.
• Mesetas.
• Crestas.
• Backtrack.
• Saltar.
• Moverse en varias
direcciones a la
vez.
Otras Ventajas y
DesventajasVentajas
• Produce una menor explosión
combinatoria.
Desventajas
• Pocas garantías de que va a ser eficaz.
combinatoria.
• Utiliza una cantidad arbitraria
de información si
está codificada en
la función
heurística.
• Sólo atiende a las consecuencias
inmediatas.
Ejemplo: El mundo de los bloques
A
H
G
F
E
D
H
G
F
E
D
CD
C
B
C
B
A
Estado Inicial (Eo) Estado Final (Ef)
Función Heurística: - Añadir un punto por cada bloque que
esté sobre un bloque o piso correcto. Restar un punto por
cada bloque que esté situado en un lugar incorrecto.
VERIFICACIÓN DE RESTRICCIONES
� En los problemas de
verificación de restricciones el
objetivo consiste en descubrirobjetivo consiste en descubrir
algún estado del problema que
satisfaga un conjunto dado de
restricciones
Ejemplos
• Problemas con rompecabezas y
criptoaritméticos.
• Etiquetado de percepciones en el• Etiquetado de percepciones en el
mundo real.
• El diseño de tareas (tiempo, costo y
materiales como limitantes).
¿Cómo funciona?
• Aunque se necesiten aún las
suposiciones, el número de las que
son permitidas se va reduciendoson permitidas se va reduciendo
conforme la búsqueda se va
restringiendo.
• Es un procedimiento de búsqueda
que funciona en un espacio de
conjuntos de restricciones.
¿Qué se busca?
• Un estado objetivo es aquel que ha
satisfecho las restricciones
“suficientemente”, donde “suficientemente”, donde
“suficientemente” debe definirse
para cada problema en particular.
Pasos para la búsqueda
�La propagación se hace necesaria
por el hecho de que normalmente
existen dependencias entre lasexisten dependencias entre las
restricciones. También debido a la
presencia de reglas de inferencia
que permiten la inferencia de
otras restricciones adicionales.
�Realizar nuevas hipótesis�En el caso de que con lasrestricciones iniciales no se llegue auna solución.
�Después comenzar de nuevo lapropagación de restricciones a partirpropagación de restricciones a partirde ese nuevo estado.
�Si se encuentra una solución semuestra.
�Si se detecta alguna contradicciónpuede usarse vuelta atrás.