ESTRATEGIA DE BUSQUEDA INFORMADA BÚSQUEDA A *

INTRODUCCION

La presente temática muestra como estas búsquedas realizan su labor con el fin de ayudar a encontrar una solución más óptima. Esta búsqueda es más conocida como primero el mejor ya que para él todos los nodos van a representar una alternativa de solución esto quiere decir que el primer camino va hacer el mejor para este.

MARCO TEORICO

ESTRATEGIA DE BUSQUEDA INFORMADA

BÚSQUEDA A *: MINIMIZAR EL COSTO ESTIMADO TOTAL DE LA SOLUCIÓN.

Esta búsqueda también conocida como primero la mejor, evalúa los nodos combinados g(n), coste para alcanzar el nodo y h(n) el coste de ir al nodo objetivo es:

F(n)=g(n)+h(n)

 En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:

1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.

2. CERRADOS - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.

3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.

Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.

Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.

El algoritmo, en la forma que fue formulado, se aplica a grafos. Puede ser simplificado para aplicarse a árboles, si no se preocupa de comprobar si un nuevo nodo esta en ABIERTOS o en CERRADOS. Esto aceleraría la generación de nodos y la búsqueda, para casos en que es poco probable que se repitan nodos.

Usualmente, el costo de ir de un nodo a su sucesor, g, se fija en una constante igual 1, cuando se desea encontrar un sendero a la solución, que involucre el menor número de pasos. Si por el contrario nos interesa encontrar el camino menos costoso y algunos operadores cuestan más que otros, se asume un valor de g, que refleje esos costos. Un valor de g igual a cero significaría que simplemente nos interesa llegar a alguna solución, de cualquier manera.

CONCLUSION

Luego de haber analizado la temática en clases se concluye con que esta es la que realiza su búsqueda de acuerdo al medio que se encuentre y de aquí ella escoge primero el mejor ya que el primer nodo que encuentre esta supone que es el mejor.

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.