Busqueda Optima

La búsqueda óptima también es llamada búsqueda heurística, trata de resolver los problemas mediante un nueva técnica. Podemos expandir nodos por selección seleccionando el nodo más prometedor, donde estos nodos estarán identificados por el valor de su fuerza comparada con sus competidores homólogos, con la ayuda de funciones intuitivas especializadas, llamadas funciones heurísticas. La búsquedaheurística generalmente trabaja para dos tipos distintos de problemas: Forward reasoning (razonamiento hacia delante)Backward reasoning (razonamiento hacia atrás).

Funcionamiento
• Analizar primero los nodos con menor coste.
• Ordenar la cola de abiertos por coste, de menor a mayor 
• De esta manera, cuando se llega por primera vez a un estado final, se llega con el menor costo posible.
• Setrata de una búsqueda ciega
• No usa conocimiento para guiar la búsqueda hacia el objetivo
• Caso particular: búsqueda en anchura.

Propiedades de la búsqueda óptima
• Complejidad:
r: factor de ramificación.
p: profundidad de la solución.
Complejidad en espacio: O(rp).
Complejidad en tiempo: O(rp).
• Es completa.
• Es óptima.
• Salvo en espacios de estadospequeños, en la práctica esta búsqueda no esposible, debido a la cantidad de tiempo y espacio consumidos.

Implementación de la búsqueda óptima

FUNCION BUSQUEDA-OPTIMA ()
1. Hacer ABIERTOS la cola formada por el nodo inicial (es decir, el nodo cuyo estado es *ESTADO-INICIAL*, cuyo camino es vacío y cuyo coste es 0); Hacer CERRADOS vacío.
2. Mientras que ABIERTOS no esté vacía,
2.1 Hacer ACTUAL elprimer nodo de ABIERTOS y ABIERTOS el resto de ABIERTOS
2.2 Poner el nodo ACTUAL en CERRADOS.
2.3 Si ES-ESTADO-FINAL (ESTADO (ACTUAL)),
2.3.1 devolver el nodo ACTUAL y terminar.
2.3.2 en caso contrario,
2.3.2.1 Hacer NUEVOS-SUCESORES la lista de nodos de SUCESORES (ACTUAL) que o bien tienen un estado que no aparece en los nodos de ABIERTOS ni de CERRADOS, o bien su coste es menor que cualquierotro nodo con el mismo estado que apareciera en ABIERTOS o en CERRADOS
2.3.2.2 Hacer ABIERTOS el resultado de incluir NUEVOS-SUCESORES en ABIERTOS y ordenar todo en orden creciente de los costes de los caminos de los nodos
3. Devolver FALLO
Ejemplo de algoritmo de búsqueda optima

Inicio
1.- Identificar los posibles estados iniciales y medir la distancia (f) del más cercano con a la meta;ponerlos en una lista (L)
2.- Mientras L no este vacía has
Inicia
a) Identificar el nodo n de L que tenga el mínimo f; Si existe más de un nodo con un f mínimo, seleccionar uno de ellos, (tomar n, arbitrariamente)
b) Si n es la meta
Entonces regresar n a lo largo del camino desde el nodo inicial; salir con éxito.
Si no remover n de L y agregar todos los hijos de n a L, junto con sucamino etiquetado desde el nodo inicial
Fin del mientras;
Fin
































Búsqueda de una solución óptima
Estrategias no informadas para la búsqueda de una solución óptima.

Comenzamos planteando el problema a resolver. Este tipo de estrategias aparece cuando en el sistema de producción el disparo de las reglas tiene asociado un coste, que,en lo que sigue, será un número (real o natural) estrictamente mayor que cero. Esta condición es equivale a que en el espacio de estados cada arista tenga asociado como peso un coste numérico mayor que cero. Llamaremos coste de un camino en el espacio de estados a la suma de los costes de las aristas que lo constituyen. Como es habitual, la longitud de un camino es su número de aristas. Si elcoste de cada arista es 1, coste y longitud coinciden. Este es el caso en sistemas de producción para los que ninguna noción de coste es adecuada, pero para los que queramos aplicar las estrategias de búsqueda de una solución óptima.

El problema consiste pues en encontrar una solución óptima, es decir un camino solución cuyo coste sea mínimo entre los de los caminos solución. A un tal camino,...