Heurística, y búsquedas heurísticas

Heurística

Heurística, es un término para técnicas basadas en la experiencia, que ayudan en la resolución de un problema, aprendizaje, y descubrimiento. Un método heurístico es usado para llegar a una solución rápidamente que se espera sea cercana a la mejor respuesta posible, o “solución óptima”. Una heurística es una conjetura, un juicio intuitivo, o simplemente sentido común.

En ciencias computacionales, una heurística es una técnica diseñada para resolver un problema que ignora si la solución puede ser probada correcta, pero que usualmente produce una buena solución o resuelve un problema más simple que contiene o intersecta con la solución de un problema más complejo.

La intención de las heurísticas, es ganar desempeño computacional, o simplicidad conceptual, potencialmente al costo de precisión.

Búsqueda heurística

Una búsqueda heurística, es aquella que emplea  una “heurística”, tal como fue definida en la sección anterior. En una búsqueda de este tipo, cada sucesión iterativa, depende del paso anterior, por lo tanto, la búsqueda heurística aprende qué caminos perseguir, y qué caminos ignorar midiendo qué tan cerca la iteración actual, se encuentra a la solución. Por lo tanto, algunas posibilidades nunca serán generadas pues son consideradas de menor probabilidad para llegar a la solución.

Un método heurístico puede lograr su tarea, usando árboles de búsqueda. Sin embargo, en lugar de generar todas las ramas de posibles soluciones, una búsqueda heurística selecciona las ramas con mayor probabilidad de producir resultados, que otras ramas. Es selectiva en cada punto de decisión, escogiendo las ramas, que tienen mayor probabilidad de generar soluciones.

Búsqueda primero el mejor (Best first search)

La aproximación general para estrategias de búsqueda informada, es conocida como búsqueda primero el mejor (best first search), donde un nodo es seleccionado para expansión, basados en una función de evaluación f(n).

La función de evaluación se interpreta como un estimado del costo, de tal manera que el nodo con la menor evaluación, se expande primero.

Lo anterior, implica para la implementación del algoritmo, la necesidad de ordenar los nodos en la frontera de acuerdo a un orden incremental de los costos.

La mayoría de los algoritmos primero el mejor, incluyen a una función heurística como componente de f, denominado h(n):

h(n) = costo estimado de la ruta de menor costo desde el estado en el nodo n, al estado final.

Existen dos casos especiales de búsqueda primero el mejor:

• Búsqueda voraz primero el mejor (Greedy best first search).
• Búsqueda A*.

Estos algoritmos se analizan con mayor detenimiento a continuación.

Búsqueda voraz primero el mejor (Greedy best first search)

La búsqueda voraz primero el mejor, intenta expandir el nodo que se encuentra más cerca de la meta, bajo la suposición de que esto es probable que lleve a una solución rápidamente. De esta manera, evalúa nodos usando sólo la función heurística; esto es, f(n) = h(n).

Propiedades

• Este algoritmo no es completo, puede quedarse atascado en ciclos.
• Tiempo: O(b^m), pero una buena heurística puede proporcionar una mejora dramática.
• Espacio: O(b^m), mantiene todos los nodos en memoria.
• Óptimo: No.

Búsqueda A*

Es un algoritmo  que se utiliza ampliamente en la búsqueda de rutas, y el recorrido de grafos, el proceso de trazar un camino eficientemente transitable entre puntos, denominados nodos. Conocido, por su desempeño, y precisión, goza de un amplio uso. Se le considera una extensión del algoritmo de Dijkstra. A* logra un mejor desempeño (con respecto al tiempo), haciendo uso de heurísticas.

Descripción

El algoritmo A* utiliza una búsqueda primero el mejor, y encuentra la ruta de menor costo dado un nodo inicial, hacia un nodo objetivo.

Utiliza una función heurística de “distancia más costo” (generalmente denominada f(x)) para determinar el orden en que la búsqueda visitará los nodos en el árbol. La heurística de “distancia más costo” es una suma de dos funciones:

• La función del costo de la ruta, la cual consiste en el costo desde el nodo inicial, al nodo actual (usualmente denominada g(x)).
• Y un “estimado de heurística” admisible de la distancia a la meta (usualmente denominado h(x)).

La parte h(x), de la función f(x), debe ser una heurística admisible, lo que significa, que no debe sobrestimar la distancia a la meta. De esta manera, para una aplicación como el ruteo, h(x) puede representar la distancia en línea recta a la meta, dado que físicamente, es la distancia más pequeña posible entre dos puntos, o nodos cualquiera.

Si la heurística satisface además la condición h(x) ≤ d(x, y) + h(y) para toda arista x, y del grafo (donde d denota la longitud de esa arista), entonces h es llamada monótona, o consistente. En tal caso, A* puede ser implementado más eficientemente.

Propiedades

De la misma manera que la búsqueda primero en anchura, A* es completa, y siempre encontrará una solución, si es que existe.

Si la función heurística h es admisible, entonces A* es admisible (óptimo) si no usamos una lista de nodos ya visitados (conjunto cerrado).

Si se utiliza un conjunto cerrado, entonces h debe ser monótona (o consistente) para que A* sea óptimo.

Asimismo, A* es óptimamente eficiente, para cualquier heurística h, lo cual significa, que ningún algoritmo que emplee la misma heurística, expandirá menos nodos que A*, excepto cuando existan múltiples soluciones parciales, donde h predice exactamente el costo del camino óptimo.

La complejidad en tiempo de A* depende se la heurística. En el peor caso, el número de nodos expandidos es exponencial en la longitud de la solución (el camino más corto), pero es polinomial cuando el espacio de búsqueda es un árbol, hay un sólo estado objetivo, y la función heurística cumple la condición de que su error no crecerá más rápidamente que el logaritmo de la “heurística perfecta” (aquella que regresa la verdadera distancia a la meta).