ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmos de búsqueda en grafos : que es, definición y significado, descargar videos y fotos.

videos internet

salud  ıllı Algoritmos de búsqueda en grafos : que es, definición y significado, descargar videos y fotos.  


Los algoritmos de busca en grafos nacen por la necesidad de crear un mecanismo de navegación autónoma, bien sea de robots, vehículos, o bien personajes en un juego para videoconsolas. Ciertos más conocidos son DFS, BFS, A*, IDA*, Fringe Search o bien D*.



Un grafo, representa un conjunto de nodos unidos en una red. Si 2 nodos están unidos, al viajar de uno a otro se considerara sucesor el nodo al que nos movemos, y precursor el nodo del que venimos. Además de esto, por norma general va a existir un costo vinculado al desplazamiento entre nodos. Un algoritmo de busca va a tratar de localizar un camino optimo entre 2 nodos como por servirnos de un ejemplo un camino que minimice el costo de desplazamiento, o bien el número de pasos a efectuar. La primordial diferencia entre los algoritmos es la información que guardan sobre el grafo. Ciertos de ellos no guardan información alguna, sencillamente expanden la busca desde el nodo inicial, hasta el momento en que se llega al nodo final, otros guardan el costo de viajar desde el origen hasta ese nodo, o bien aun una estimación de lo prometedor que es un nodo para conducir el camino a su objetivo. La expansión de la busca se efectúa en forma de árbol. Partiendo del nodo inicial, se extenderá la busca a sus nodos vecinos, de cada uno de ellos de estos nodos vecinos, a sus respectivos nodos vecinos, y de esta manera hasta el momento en que uno de los nodos a los que se expande la busca es el nodo objetivo. En esta página se desarrollará un algoritmo de busca suficientemente general para trabajar en la mayor parte de los grafos, y que da paso a otros métodos de busca más complejos.


El algoritmo consta de 2 listas, Abierta, y Cerrada. En la lista Abierta se guardan los nodos que todavía no se han expandido para la busca, que en otras palabras, serían las hojas de un árbol. En la lista Cerrada, se guardan los nodos que se han procesado y expandido, estos nodos se guardan por el hecho de que la expansión de la busca podría procurar regresar a pasar por uno de esos nodos y de estar guardados, se tiene perseverancia de los nodos que se han procesado. Además de esto, cada nodo, guardará información a cerca de quien es su nodo precursor.


Ejemplo de algoritmo simple


Pseudocódigo de búsqueda


Explicación del algoritmo


Primero se crean 2 listas que guardarán nodos, la lista Abiertos, que contiene los nodos que se deben expandir, y la lista Cerrados que contiene los que han sido expandidos. El nodo de origen, llamado O bien en un caso así, se mete en la lista de Abiertos para ser expandido. En este punto, se comienza la propagación de la busca, se crea un bucle que terminará en 2 posibles ocasiones: Cuando la lista Abiertos este vacía, o bien cuando se halle el nodo destino. El bucle consiste en múltiples pasos: Primero se consigue el primer nodo de la lista Abiertos. El nodo a coger el arbitrario, en otros algoritmos se cogería un nodo que cumpliese ciertas propiedades, mas no es lo que se busca acá. Si esta lista está vacía, desea decir que no quedan pero aspirantes para la expansión, y incluso de esta manera no se halló el destino, el algoritmo ha fallado. Por otro lado, si el nodo que cojimos de la lista Abiertos es el destino, el algoritmo va a haber acabado, puesto que hemos encontrado el destino. El camino entre el origen y el destino es un conjunto de nodos que se conseguirán guardando cada precursor del nodo destino. En otro caso, se proseguirá expandiendo la lista, consiguiendo una lista de sucesores del nodo actual, y guardando en la lista Abiertos, aquellos nodos que no estuviesen ya antes en una lista, o bien con otras palabras, aquellos nodos a los que todavía no se había llegado. Así, el algoritmo terminará encontrando el destino, o bien recorriendo todo el mapa.



Nota: La animación tiene un fallo, puesto que el camino debería haber comenzado en dirección norte en lugar de en dirección oeste. Esto ha pasado pues no se metió el cuadro destino en la lista abierta en el instante oportuno (se metió 2 turnos después). El algoritmo trata de llegar desde el cuadro verde (el origen), hasta el cuadro colorado (el destino). La zona negra es un nodo por el que no puede pasar. Siguiendo el algoritmo, el nodo inicial se ira expandiendo, pasando a estar el nodo actual en la lista Cerrados (color violeta) y metiendo otros nodos en la lista de Abiertos (color azul). Además de esto cada nodo guardará quien es su precursor, que está simbolizado con las muescas en los bordes de los cuadrados. En el momento en que la expansión alcanza el nodo destino, se produce un camino siguiendo la cadena de precursores.


Como se aprecia, la expansión se efectúa sin orientación alguna, a lo largo y ancho del espacio. Esto va a aumentar sensiblemente el tiempo de computación, en tanto que se procesan considerablemente más nodos que si la expansión estuviese orientada en la dirección del destino. Otro factor a tomar en consideración es que pese a haber alcanzado el nodo destino, el algoritmo no concluye hasta el momento en que lo procesa, o bien en otras palabras, hasta el momento en que pasa a ser el primer nodo de la lista Abiertos. Estas 2 taras, están relacionadas con la prioridad de busca, y en algoritmos más avanzados se corrige a través de el empleo de estimadores heurísticos como la distancia manhattan, o bien la distancia euclídea. Utilizando estos estimadores el algoritmo procesará primero los nodos de la lista abierta que tengan una menor distancia al origen, eludiendo de este modo expansiones superfluas.


Otra desventaja esencial del algoritmo, es que no tiene capacidad para solucionar cambios inopinados en el mapa. Una vez calculada la senda, si un obstáculo se interpone en el camino conseguido no se va a hacer nada por evitarlo. Esto se soluciona en algoritmos como D*, que si tienen presente estas alteraciones.


Programa en Java que ilustra el empleo de algoritmos de busca.


Código fuente de ese programa.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmos de búsqueda en grafos : que es, definición y significado, descargar videos y fotos.

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas