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

...