1.
8 EL PAPEL DE LA
HEURISTICA
M.T.E. WENDY CARRANZA DÍAZ
Concepto:
◦ Consiste en encontrar o construir algoritmos con buena velocidad para ser ejecutados como los
juegos informáticos o los programas que detectan si un correo electrónico es un spam o no.
◦ Se conoce como heurística al conjunto de técnicas o métodos para resolver un problema. La palabra
heurística es de origen griego εὑρίσκειν (heuriskein), que significa “hallar, inventar, encontrar o
descubrir”.
◦ Se denomina heurística a la capacidad de un sistema para realizar de forma inmediata innovaciones
positivas para sus fines.
◦ El arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad
y el pensamiento lateral o pensamiento divergente.
En computación
◦ Objetivos fundamentales:
◦ Encontrar algoritmos con buenos tiempos de ejecución y
◦ Buenas soluciones, usualmente las óptimas.
◦ Una heurística es un algoritmo que aborda uno o ambos objetivos;
◦ Ejemplo:
◦ Normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser
arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco
prueba de que siempre será así.
◦ Las heurísticas generalmente son usadas cuando no existe una solucion óptima bajo las restricciones
dadas (tiempo,espacio,etc.), o cuando no existe del todo.
1.8.1 Algoritmos de exploración de
alternativas.
◦ Al escribir algoritmos, la alternativa múltiple se representa de este modo: Nos proporcionan uno o dos
caminos alternativos para nuestros programas, respectivamente.
◦ La alternativa múltiple evalúa una expresión que puede tomar n valores distintos. Según sea el valor que
tome la expresión, el flujo del programa seguirá un camino determinado entre los n posibles.
◦ Se denomina heurística a la capacidad de un sistema para realizar de forma inmediata innovaciones
positivas para sus fines.
◦ Puede haber tantos elementos caso como caminos diferentes necesitemos en nuestro algoritmo.
Ejemplo
◦ Nos sirve para proporcionar 1 o más
caminos alternativos a la solución del
problema dentro de un algoritmo, la
alternativa múltiple evalúa una
expresión que puede tomar n valores
distintos, según sea el valor que tome la
expresión, el flujo del programa seguirá
un camino determinado entre las n
posibilidades.
También se puede utilizar para resolver el cubo Rubik
mostrándonos cómo hacerlo con la menor cantidad de
movidas.
Algoritmo A*
◦ ¿Cómo funciona el algoritmo A *?
◦ A* es un algoritmo de búsqueda inteligente o informada que busca el camino más corto desde un
estado inicial al estado meta a través de un espacio de problema, usando una heurística óptima.
Como ignora los pasos más cortos (más "chatos") en algunos casos rinde una solución subóptima.
◦ A* es un algoritmo informado que basa su comportamiento en la evaluación de una función expresada
del siguiente modo: f(n) = g(n) + h(n)
◦ La función se encuentra compuesta por: g(n) : es el costo de las movidas realizadas. h(n) : es la
función heurística. Representa el costo estimado del mejor camino.
◦ Dicha estimación debe ser realizada por defecto, es decir, siempre menor o igual a la real.
◦ En búsqueda de caminos, la función heurística suele ser el camino recto hacia la meta, ya que no
importa como sea el mapa, es imposible que exista camino de costo menor.
◦ El modo de realizar el cálculo de la distancia necesaria para llegar a la meta depende del tipo de movidas
permitidas.
◦ Si solo podemos movernos vertical y horizontalmente podremos realizar el cálculo de la distancia
Manhattan, que consiste en sumar la cantidad de bloques en horizontal y vertical que restan para llegar a
la meta.
◦ Si además se permiten movidas diagonales, deberemos aplicar Pitágoras y el cálculo será la raíz cuadrada
de la suma de los cuadrados de los catetos. El movimiento de un punto a otro en simple pero la búsqueda
de rutas optimas en mas compleja
◦ El movimiento de un punto a otro en simple pero la búsqueda
de rutas optimas en mas compleja.
◦ En la figura mostrada el algoritmo trata de llegar del punto de
inicio (recuadro verde Start) en la parte inferior hasta la parte
superior, no hay nada en el área que muestre que no debería
moverse directamente hacia arriba, cerca de llegar a la parte
de arriba se encuentra con un obstáculo y cambia su ruta
dándole la vuelta al obstáculo en forma de “U” siguiendo
la trayectoria roja, de haber empleado un buscador de ruta
como el A* este seguiría la ruta mas optima a la meta que en
esta caso se describe por la ruta azul
Algoritmo A*
1.8.3.- Algoritmo de búsqueda local
Paisaje de estados:
◦ Es donde se encuentra el conjunto de soluciones y sirve para comprender mejor la búsqueda local. Su
posición se basa en el estado y la evaluación se basa en la función de coste del objetivo o de la heurística
