Inteligencia Artificial
Eivy Pereyra
Carvalho
Unidad 4
Búsquedas
heurísticas: con
información
BUSQUEDAS CON INFORMACION A PRIORI
(HEURISTICAS)
Búsquedas a Ciegas (sin información):
- Busca la primer solución sin importar que tan óptima sea;
- No detecta si se esta aproximando o alejando de la
solución.
- No es capaz de encontrar una solución aceptable en caso
de que
- No exista o sea demasiado costoso encontrar la solución
óptima.
Búsquedas Heurísticas (con información):
- Busca soluciones aceptables;
- Reduce el espacio de búsqueda
- Es capaz de determinar su proximidad a una solución y la
calidad
de la misma utilizando conocimiento a priori
BUSQUEDAS CON INFORMACION A PRIORI
(HEURISTICAS)
1. Búsqueda preferentemente por lo mejor
2. Búsqueda Tacaña (avara) o Voraz
3. Búsqueda A*
( combina Costo uniforme g(n) + Busqueda Avara
(h(n) )
4. Búsqueda A* por profundización iterativa
(A* PI)
5. Búsqueda A* SRM (acotada por memoria
simplificada)
Búsquedas heuristicas
Heuristica deriva del griego
“heurisken” que significa “encontrar”
Las heurísticas son criterios, métodos
o principios para decidir cuál de entre
varias acciones promete ser la mejor
para alcanzar una determinada meta
El conocimimiento en que se apoya
esta decisión es obtenido desde una
función de evaluación, la cual
produce un número que sirve para
representar lo deseable
Aplicaciones reales
Encontrar la ruta optima: transporte,
ingeniería, VLSI, diseño, medicina,
robótica, visión, manufactura.
Encontrar combinación más
deseable: horarios, finanzas,
ingeniería, medicina, administración
negocios.
Minimizar costo de producción y/o
materiales.
Función de evaluación
Es una función real definida sobre las
descripciónes de los estados
La búsqueda preferentemente por lo mejor
Utiliza una ó más funciones de
evaluación
Se expandirá el nodo n para el que se
obtenga el mejor valor f(n)
Se terminará el proceso cuando el
nodo a expandir sea un nodo objetivo
Técnica de la escalada (por lo
mejor)
Técnica de la escalada (por lo
mejor)
f(nodo)= # de casillas bien colocadas (maximizo)
f’(nodo)= # de casillas mal colocadas (minimizo)
Como ejemplo del juego 8-puzzle se puede definir una
función de evaluación que fuera igual:
f(nodo)= # de casillas bien colocadas (máximo)
Que devuelven un número que representa como está de
cerca un determinado estado de la solución, cuanto mayor
sea el número se estará cerca de la solución.
Por tanto si se tiene que elegir entre varios estados se
debería escoger aquel, que tendría un valor mayor de esta
función, es decir es una función que se debe maximizar.
Búsqueda preferentemente por lo mejor
Funcion BusquedaPreferentementePorLoMejor (problema,
FuncionEvaluacion) responde con una secuencia de solucion
función_lista_de_espera = una función que ordena los nodos
mediante
FuncionEvaluacion
responde con BusquedaGeneral (problema,
función_lista_de_espera)
Se trata de dos tipos de aproximación básicos:
1. El primero trata de expandir el nodo más cercano a la meta:
Búsqueda avara
2. El segundo, el correspondiente a la ruta solución menos costosas:
Busqueda A*
Búsqueda avara (tacaña)
Funcion BusquedaAvara(problema) responde con una
solución o falla
responde con BusquedaPreferentementePorLoMejor(problema, h)
h(n) costo estimado de la ruta más barata que une el estado del nodo n con
un estado meta.
En la mayoría de los casos h(n) es insuficiente para la lograr una
solución optima
h(n) = 0 cuando n es una meta
Es posible que una búsqueda avara equivoque las pistas
Se puede atorar en un callejón sin salida
Es similar a la busqueda preferentemente por profundidad: No es optima ni
completa
Tanto la complejidad espacial como la temporal es O(b ^m) donde m es la
profundida máxima del espacio de búsqueda
Función heurística para el mapa de Rumania: Distancia en línea recta
Cuando f(n) es igual a h(n) no siempre se logra la ruta
optima
Busqueda A*
Combina g(n) y h(n)
f(n) = g(n) + h(n)
): mejor costo desde el nodo raíz al nodo n
): costo estimado del camino mas barato
desde n hasta el objetivo
): coste más barato estimado de la solución a través d
Notación usada en la búsqueda heuristica
Progreso de un árbol de búsqueda para Bucahrest
Código Busqueda A* para ir de una ciudad a
otra
[Link]
v=NWS-_VsMab4
Funciones
heurísticas para el
puzle - 8
Otro ejemplo: Puzle - 8
Compartamiento de A*
con el puzzle - 8
[Link]
resolucion-busqueda/algoritmo-a-
2XO7b
Comparación de costos
¿Cómo inventar funciones heurísticas?
Relajar el problema:
¿Cómo inventar funciones
heurísticas?
[Link]
resolucion-busqueda/diseno-de-
funciones-heuristicas-Azp3p
Explicación de Russel del Algoritmo A*
Funcion Busqueda_A* (problema) responde con una solución o falla
{ retorna con
Busqueda_preferentemente_por_lo_mejor(problema, g+h) }
on Busqueda_preferentemente_por_lo_mejor(problema, FuncionEvaluaci
nde con una secuencia solución
ción_lista_espera = función que ordena los nodos mediante FuncionEval
onde con BusquedaGeneral(problema, función_lista_espera) }
on BusquedaGeneral (problema, FunciónListaEspera)
nde con solución o falla
os =Hacer lista de espera (HacerNodo(EstadoInicial[problema]))
e hacer
nodos está vacío, conteste con falla
do = EliminarDelFrente (nodos)
PruebaMeta[problema]
e aplica a Estado(nodo) y se tiene éxito, contestar con nodo
nodos = función_lista_espera(nodos, EXPANDIR(nodo, OPERADORES[pro
Explicación del Nils Nilsson del Algorítmo A*
Ejemplos de heurísticas y Explicación adicional del
Nils Nilsson del Algorítmo A*
[Link]
ia/transparencias/
busqueda_heuristica.pdf
OTRO EJEMPLO: Búsqueda heurística con planificador de rutas
https://
[Link]/watch?v=X-5JMScsZ14
[Link]
v=nd9L5UrAKto
Implementar el algoritmo A*
para el puzzle-8 usando otra
heurística:
La distancia de Manhatan
PseudoCodigo del algoritmo A*
[Link]
z35/
el-algoritmo-a-asterisco
https://
[Link]/
2011/08/14/implementacion-
algoritmo-a-estrella-explicacion/
Alternativa: Algoritmo recursivo para la búsqueda primero el
mejor
(optimiza memoria)
