Busquedas Heuristicas.

¿Qué es una heurística?

Etimológicamente significa “búsqueda” o “descubrir”.
Es usado para definir el estudio de los métodos para descubrir e inventar técnicas para
solucionar problemas, particularmente para los que requieren pruebas matemáticas. Tales
métodos no se consideran susceptibles de explicación.
Actualmente se usa más para describir que cualquier técnica mejore el rendimiento en
casos promedio de una tarea de solución de problemas. En el caso específico de los
algoritmos de búsqueda, se refiere a una función que proporciona el coste de una solución.

BEST-FIRST SEARCH
Definición:
Es un algoritmo que explora un grafo, expandiendo el nodo mas prometedor,
determinado por una regla especifica.

Características:
Se escoge el nodo que aparente ser el mejor o mas cercano, de acuerdo a una funcion
que evalué la importancia de los nodos.
function BEST-FiRST-SEARCH(/7/-oWew?, EVAL-FN) returns a solution sequence
inputs: problem, a problem
Eval-Fn, an evaluation function
Queueing-Fn <— a function that orders nodes by EVAL-FN
return GENERAL-SEARCH(proW
Complejidad:

Optimabilidad: No es óptimo, requiere de heuristicas para mejorarlo.

Completud: Es incompleto. La funcion que evalua los nodos puede fallar y tomar un mal camino.

Greedy Search.

Definición:

Búsqueda BFS que busca minimizar el costo estimado para alcanzar la meta.

Características:

Se mueve a la siguiente posición más atractiva.

Aquel nodo cuyo estado se inclina más a la meta es expandido primero.

Usa una función heurística para estimar el costo del camino más barato desde el estado del nodo “n” hasta la
meta.

El código sería:

function GREEDY-SEARCH(problem) returns a solution or failure

return BEST-FiRST-SEARCH(problem, h) //siendo “h” la function heuristic

Complejidad.- En el peor de los casos su complejidad es O(bm), donde “m” es la profundidad máxima del espacio

de búsqueda. Su complejidad espacial es la misma que la temporal porque retiene todos los nodos en memoria. Estas
dependen de la función heurística, si está bien implementada la complejidad se puede reducir.

Optimalidad.- No es óptimo

Completud.- Es incompleto, puede seguir un camino infinito y nunca regresara probar otras posibilidades.

A*

Que es ? Es una método de búsqueda que es el mejor-primera búsqueda que utiliza “f” que es la
función de evaluación y admite las funciones de “h”.

Como g (n) se obtiene el costo del camino desde el nodo inicial al nodo n y h (n) es el costo estimado de
los camino más baratas de n a la meta

/ («) = Costo estimado de la solución más barata a través de n

f(n) = g(n) + h(n).

Principales Características:

Por lo tanto, si estamos tratando de encontrar la solución más barata, una cosa razonable es intentar
primero con el nodo con el menor valor de f.

La restricción es escoger una función h que nunca sobreestima el costo para llegar a la
meta. Tal h se llama una heurística admisible. Heurísticas admisibles son, por naturaleza optimista,
porque creen que el costo de resolver el problema es menos de lo que realmente es.

Esto transfiere el optimismo a la función f, así: Si su trámite, f (n) nunca sobrestima los costes reales de
la mejor solución a través de n.

Propiedades fundamentales

Complejidad

El problema es que, para la mayoría de los problemas, el número de nodos en el espacio de búsqueda del
contorno meta sigue siendo exponencial en la longitud de la solución. Aunque la prueba del resultado
está fuera del alcance de este libro, se ha demostrado que el crecimiento exponencial se producirá a
menos que el error en el heurístico no crece más rápido que el logaritmo de la ruta real de costos.

\h(n) -A*(n)|<0(log/.*(«)),

Optimalidad

Esto contradice la suposición de que G ^ _ no es el óptimo, por lo que debe ser el caso que nunca
A * selecciona un objetivo óptimo para la expansión. Por lo tanto, porque sólo ofrece una solución
después de haberlo seleccionado para la expansión, A * es un algoritmo óptimo. Localmente finito

Completud

Por lo tanto, el comando correcto es que A * es completa de forma local en grafos finitos (gráficos con
una finitos factor de ramificación), siempre hay alguna constante positiva 6 de tal manera que todos los
operadores los costes son por lo menos 6.