Metodo el primero mejor the first better

INSTITUTO POLITÉCNICO NACIONAL
UNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERÍA Y CIENCIAS SOCIALES Y ADMINISTRATIVAS

TAREA 3.2
MÉTODO EL PRIMERO MEJOR (BEST FIRST)

BÚSQUEDA EL PRIMERO MEJOR

La búsqueda de el primero mejor (best-first search), representa una forma de combinar las ventajas que representan tanto la búsqueda primero en anchura como la primero en profundidad en un solométodo.
La búsqueda primero en profundidad tiene la ventaja de que permite encontrar una solución sin tener que expandirse completamente por todas las ramas. La búsqueda primero en anchura presenta la ventaja de que no queda atrapada en callejones sin salida. Una forma de combinar ambas ventajas puede consistir en seguir un único camino cada vez, y cambiarlo cuando alguna ruta parezca másprometedora que la que se está siguiendo en ese momento.
En cada paso del proceso de búsqueda el primero mejor, se selecciona el nodo más prometedor que se haya generado hasta ese momento. Esto se puede conseguir con una función heurística apropiada. A continuación se expande el nodo elegido aplicando las reglas para generar a sus sucesores. Si alguno de ellos es una solución, el proceso termina. Si noes así, estos nuevos nodos se añaden a la lista de nodos que se han generado hasta ese momento, De nuevo, se selecciona el más prometedor de ellos y el proceso continúa de la misma forma. Lo normal es que la forma de funcionar se parezca un poco a la búsqueda primero en profundidad al explorar las ranas. Sin embargo, si no se encuentra una solución, Ia rama empezará a parecer menos prometedora queotras por encima de ella y que se habían ignorado. En este caso, una rama que previamente se había ignorado aparece ahora c0m0 la más prometedora y, por lo tanto, comienza su exploración. Sin embargo, la vieja rama no se olvida. Su último nodo se almacena en el conjunto de nodos generados pero aún sin expandir. La búsqueda puede volver a él en el momento en que los otros sean lo suficientementemalos como para que este se de nuevo el camino más prometedor de todos.
En el método de búsquela de el primero mejor, se sigue seleccionando un movimiento, pero todos los demás: se mantienen de forma que pueden visitarse si el camino que se ha seleccionado llega a ser menos prometedor. Además de esto, en la búsqueda de el primero mejor se selecciona el mejor estado disponible, aun si este estadotiene un valor menor del qué se estaba explorando. Esto contrasta con el método de la escalada, en donde el proceso se detiene si no se encuentra un estado sucesor mejor que el estado actual.

A pesar de que el ejemplo se emplea un árbol para ilustrar el proceso de búsqueda el primero mejor, en ocasiones es importante realizar la búsqueda sobre un grafo de forma que los caminos duplicados no seexploren. Tal algoritmo debe realizar una búsqueda en un grafo dirigido donde cada nodo representa un punto en el espacio de estados.
Para poder implementar un procedimiento de búsqueda sobre un grafo se necesitan dos listas de nodos:
* ABIERTOS –nodos que se han generado y a los que se les ha aplicado la función heurística, pero que aún no han sido examinados (es decir, no se han generadossus sucesores), La lista ABIERTOS es, en realidad, una cola con prioridad en la que los elementos con mayor prioridad son aquellos que tienen un valor más prometedor de la función heurística. Para manipular la lista pueden utilizarse las técnicas usuales de manipulación de colas de prioridad.

* CERRADOS –nodos que ya se han examinado. Es necesario mantener estos nodos en memoria si lo que sedesea es hacer una búsqueda sobre un grafo y no sobre un árbol, debido a que cuando se genera un nuevo nodo, se debe verificar si ese nodo se había generado con anterioridad.
-También se necesita una función heurística que haga una estimación de los méritos de cada uno de los nodos que se van generando. Esto permite que el algoritmo examine primero los caminos más prometedores. Llamemos a esta...