Instituto Tecnológico Superior
de Loreto
Ingeniería en Sistemas Computacionales
Materia
Inteligencia Artificial.
Grupo
8vo. A
Tema
Tema 1
Evidencia
Síntesis.
Alumno(a): 20060175 – Gallegos Hernández Bryan Alejandro.
Docente: Ing. Joan Sebastian Guerrero Campos.
Fecha de Entrega: 02-02-2024
Búsqueda Heurística.
Los métodos de búsqueda heurística disponen de alguna información sobre la
proximidad de cada estado a un estado objetivo, lo que permite explorar en primer
lugar los caminos más prometedores.
Características de los métodos heurísticos:
❖ No garantizan que se encuentre una solución, aunque existan soluciones.
❖ Si encuentran una solución, no se asegura que ésta tenga las mejor esas
propiedades (que sea de longitud mínima o de coste óptimo).
❖ En algunas ocasiones (que, en general, no se podrán determinar a priori),
encontrarán una solución (aceptablemente buena) en un tiempo razonable.
En general, los métodos heurísticos son preferibles a los métodos no informados en
la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría
un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los
problemas reales que interesan en Inteligencia Artificial.
Si nos planteamos seguir concretando como aprovechar la información sobre el
problema en sistemas de producción, la siguiente idea consiste en concentrar toda
la información heurística en una única función que se denomina función de
evaluación heurística. Se trata de una función que asocia a cada estado del espacio
de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor
que es ese estado para acceder a un estado objetivo. Habitualmente, se denota esa
función por h(e).
Función heurística.
Por una parte, la función puede ser una estimación de lo próximo que se encuentra
el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor
heurístico son los preferidos. Pero en otros casos puede suceder que lo que
convenga sea maximizar esa función.
Ejemplo de función heurística.
El problema del viajante.
❖ Estado inicial: un viajante se encuentra en una capital de provincia.
❖ Estado meta: quiere viajar a otra capital por la mejor ruta posible (la más
corta)
❖ Medios: Las capitales de provincia colindantes están unidas por carreteras;
se dispone de un mapa con la disposición de las provincias y sus
"coordenadas" en kilómetros respecto al "centro" (por ejemplo, Madrid, con
coordenadas (0,0)).
Una función heurística para ese problema consiste en asignar a cada estado un
valor que es la distancia aérea (en línea recta) con el estado objetivo. Dicha
distancia es la distancia euclídea entre las coordenadas de dos ciudades.
Se elige una ciudad como siguiente en el camino cuando la suma de la distancia a
la ciudad actual más la distancia aérea a la meta sea la menor.
Métodos de escalada.
Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada
paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese
momento.
Se dividen en dos grupos:
❖ Los métodos irrevocables, que no prevén la vuelta a un lugar del espacio de
estados si el camino resulta inadecuado.
❖ Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos
que el camino elegido no es el más adecuado.
Algoritmo de escala simple.
El algoritmo:
1. Denominar m al estado inicial y evaluarlo. Si es estado objetivo, entonces
devolverlo y terminar, si no, convertirlo en estado actual. Asignar m a una varibla
llamada elegido.
2. Repetir hasta que se encuentre solución o hasta que una iteración completa no
produzca un cambio en el estado actual:
2.1 Expandir m. Para ello,
1) Aplicar cualquier operador aplicable al estado actual m y obtener un nuevo
estado Ei.
2) Evaluar Ei:
2.1 Si Ei es estado objetivo, devolverlo y terminar.
2.1 Si Ei no es estado objetivo no es así, evaluar si Ei es mejor que el estado
actual: (H(Ei) ->H(elegido)), en cuyo caso hacer m=Ei.
2.2 Si f(elegido) # f(m) asignar m =elegido, y volver a 2.
Algoritmo de escalada por la máxima pendiente.
El algoritmo:
1. Denominar m al estado inicial y evaluarlo. Si es estado objetivo, entonces
devolverlo y terminar, si no, convertirlo en estado actual. Asignar m a una varibla
llamada elegido.
2. Repetir hasta que se encuentre solución o hasta que una iteración completa no
produzca un cambio en el estado actual:
2.1 Expandir m creando el conjunto de todos sus sucesores.
A. Aplicar cada operador aplicable al estado actual m y conseguir
nuevos estados E1, ... En.
B. Evaluar E1 .... En. Si alguno es objetivo, devolverlo y terminar Si no
es así, seleccionar el mejor H(Em)
C. Si el mejor estado Em es mejor que el estado actual, hacer que Em
sea el estado actual. Volver al paso 2.
Algoritmo A.
Definiremos una función heurística f como la suma de dos funciones g y h:
❖ Función g: es una medida del coste para ir desde el estado inicial hasta el
nodo actual (suma de los costes o valores heurísticos de todos los nodos).
❖ Función h: es una estimación del coste adicional necesario para alcanzar un
nodo objetivo a partir del nodo actual, es decir, es una estimación de lo que
me queda por recorrer hasta la meta.
❖ La función combinada f una estimación del coste necesario para alcanzar un
estado objetivo por el camino que se ha seguido para generar el nodo actual
(si se puede generar por varios caminos el algoritmo se queda con el mejor).
❖ NOTA: los nodos buenos deben poseer valores bajos.
1. Empezar con ABIERTA conteniendo sólo el nodo inicial. Poner el valor g de ese
nodo a 0, su valor h al que corresponda, y su valor f a h+0, es decir, a h.
2. Inicializar CERRADA como una lista vacía.
3. Hasta que se encuentre una meta o de devuelva fallo realizar las siguientes
acciones:
3.1 Si ABIERTA está vacía terminar con fallo; en caso contrario continuar.
3.2 Eliminar el nodo de ABIERTA que tenga un valor mínimo de f; llamar a
este nodo m e introducirlo en la lista cerrada.
3.3 Si m es meta, abandonar el proceso iterativo iniciado en 2 devolviendo el
camino recorrido (punteros a sus antepasados)
3.4 En caso contrario expandir m generando todos sus sucesores.
4) Si n’ no cumple 3), comprobar si está en cerrada; llamar n al nodo encontrado en
dicha lista y realizar las siguientes acciones:
Si 3.1) no se cumple, abandonar 4); en caso contrario propagar el nuevo
menor coste g(n’) (por lo que también actualizarán los valores de f
correspondientes(que llamaremos ni tal que i=1,2,…, siendo sus costes
anteriores g( ni )), realizando un recorrido en profundidad de éstos,
empezando en n’ y teniendo en cuenta las siguientes consideraciones:
4.1) Para los nodos descendientes ni cuyo puntero (que debe apuntar
siempre al mejor predecesor hasta ese momento) conduzca hacia el nodo ni
, actualizar g(ni )=g( ni’) y f( ni)=g( ni‘)+h( ni) y seguir el recorrido hasta que
se encuentre un ni que no tenga más sucesores calculados o se llegue a un
nodo en que ya ocurra que g(ni )=g(ni ‘), en cuyo caso se habría producido
un ciclo y también habría que terminar la propagación.
4.2) Para los nodos descendientes ni cuyo puntero no conduzca hacia el nodo
n’, comprobar si g(ni ‘ )< g( ni ), en cuyo caso se debe actualizar el puntero
para que conduzca hacia el nodo n’ (mejor camino desde la raíz encontrado
hasta ese momento) y se continúa el proceso de propagación.
5) Si n´no está en ABIERTA o en CERRADA, calcular h(n’) y f(n’)=g(n’)+h(n’),
introducirlo en ABIERTA y añadirlo a la lista de sucesores de m.
Conclusión:
• Los métodos de búsqueda heurística son una herramienta poderosa para
resolver problemas difíciles. No siempre encuentran la mejor solución, pero
pueden ser muy útiles para encontrar soluciones aceptables en un tiempo
razonable.
• El algoritmo A es uno de los algoritmos de búsqueda heurística más
eficientes.
