Metodos De Busqueda

ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS

CURSO: Sistemas Inteligentes

DOCENTE: TENORIO CABRERA Julio

INTEGRANTES:

INGA CAMPOS Sumner

LARA TANTAQUILLA Jenss

ANGELES ACEVEDO Carlos

SIFUENTES ALCANTARA Carloz

SINTESIS DE MÉTODOS DE BÚSQUEDA

BÚSQUEDA BÚSQUEDA A* (A STAR)

DEFINICIÓN

Es una búsqueda representada por una función de coste una heurística y una combinatoria es usada para encontrar la ruta más cercana para ir de un lugar a otros (llamados nodos)

CARACTERÍSTICAS

Tiene un nodo o punto inicial.

Un nodo final que representa el final del algoritmo.

Un método para identificar que nodos son traspasables y cuales son sólidos.

Un método para determinar el costo directo (g) de moverse entre los nodos.

Un método para determinar el costo indirecto (h).

Una lista de nodos abiertos, en esta lista se guardaran todos los nodos que se han identificado como posibles movimientos, pero aún no han sido evaluados.

Una lista de nodos cerrados, donde se guardaran todos los nodos evaluados y descartados, aunque no es necesario una lista, basta con un estado que indique que el nodo se encuentra cerrado.

Una forma de identificar que nodo procede a otro, para poder retornar la cadena de los nodos.

ALGORITMO

Si el nodo inicial es igual al nodo final, se retorna el nodo inicial como solución

Si no, se adiciona el nodo inicial a la lista abierta.

Mientras la lista abierta no esté vacía, se recorre cada nodo que haya en la lista abierta y se toma el que tenga el costo total más bajo.

Si el nodo obtenido es igual al nodo final, se retornan todos los nodos sucesores al nodo encontrado.

Si no, se toma el nodo y se elimina de la lista abierta para guardarse en la lista cerrada y se buscan todos los nodos adyacentes al nodo obtenido y se adicionan a la lista abierta a menos que el nodo se encuentre en la lista cerrada o que el nodo sea sólido.

Si el nodo adyacente ya se encuentra en la lista abierta se verifica que el costo sea menor, si es menor se cambian los valores de costo, sino se ignora.

Se vuelve al paso 3 y se repite hasta que el punto 4 sea verdadero o que la lista abierta quede vacía.

VENTAJAS

Es el algoritmo más sencillo de usar

Es el algoritmo que encuentra una solución más rápida

PRACTICA

BUSQUEDA VORAZ PRIMERO EL MEJOR

Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.

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.

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.

FUNCIÓN HEURÍSTICA

Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.

Algoritmos primero el mejor

Familia de algoritmos de búsqueda en grafos, informados

Se caracterizan por el uso de una función heurística

...