Algoritmo de reducci n de grafos sin p rdida de informaci n
Páginas: 24 (5944 palabras)
Publicado: 13 de septiembre de 2015
Algoritmo de reducción de grafos sin pérdida de información
Rafael Rodríguez-Puente y Manuel S. Lazo-Cortés
Universidad de las Ciencias Informáticas, La Habana, Cuba
rafaelrp@uci.cu, manuellazo55@gmail.com
Resumen. Los algoritmos relacionados con la teoría de grafos han sido ampliamente estudiados. Varios estudios se enfocan en la disminución de la complejidad temporal de estos algoritmos. Lastécnicas utilizadas en este sentido, generalmente se basan en reducir un grafo o el espacio de búsqueda de solución, eliminando información redundante para el problema específico que se desea resolver. El proceso de reducción de un grafo consiste en obtener grafos más pequeños (con menos vértices) que tengan las características principales o relevantes del grafo original. En el caso de labúsqueda de caminos óptimos, los algoritmos que hacen uso de la reducción de grafos o del espacio de búsqueda de solución, no garantizan la obtención del óptimo en todos los casos. Lo mismo ocurre en otros tipos de problemas tales como la reducción de grafos en redes de workflow, de computadoras, etc. En este trabajo se propone un algoritmo de reducción de grafos sin pérdida de información. La propuestatiene una forma flexible de especificar la manera en que se quiere reducir el grafo; por consiguiente, puede ser utilizada en la solución de varios tipos de problemas, contribuyendo a la obtención de respuestas óptimas en tiempos menores.
Palabras clave. Reducción de grafos, reescritura de grafos, búsqueda de caminos óptimos.
1. Introducción
La teoría de grafos ha sido ampliamente estudiada enlos últimos años, con énfasis en los algoritmos sobre grafos. Varios de estos algoritmos tienen un elevado costo computacional y algunos son diseñados para resolver problemas NP o NP-Duros. Por consiguiente, varios estudios están relacionados con la reducción de la complejidad computacional de estos algoritmos.
Una de las estrategias que se ha utilizado consiste en reducir el grafo teniendo encuenta el problema que se está solucionando. Esto se sustenta en el hecho de que el tiempo de ejecución de estos algoritmos, generalmente, depende del número de vértices del grafo en cuestión. El proceso de reducción de un grafo consiste en obtener grafos más pequeños (con menos vértices) que tengan las características principales o relevantes del grafo original.
En la revisión bibliográfica realizadasobre este tema, se aprecia que varios algoritmos de reducción están enfocados en mantener las características relevantes de grafos que representan redes de carreteras. Esto se realiza con el objetivo de disminuir los tiempos en la búsqueda de caminos óptimos.
En este sentido se pueden mencionar varios trabajos, por ejemplo, en [7] Gutman propone un algoritmo en el cual se define un atributo delos vértices llamado reach, este atributo es una medida de la relevancia del vértice. El atributo reach se calcula utilizando el grafo, el mismo contribuye a reducir el tiempo de ejecución en la búsqueda de caminos óptimos reduciendo el espacio de búsqueda de solución.
Una propuesta relevante de algoritmo de reducción, en grafos que representan redes de carreteras, utiliza la jerarquía de la redcomo criterio de reducción. Varias estrategias utilizan este hecho, por ejemplo, en [18] se propone un algoritmo para construir jerarquías de redes, así como ejecutar consultas sobre la misma. Los autores alcanzan tiempos de ejecución menores y muestran la factibilidad de la propuesta. Otra propuesta introduce un enfoque similar al propuesto por Gutman [1]. Los autores usan nodos relevantes(transit nodes) para viajes de larga distancia, pre-calculando los caminos óptimos entre cada par de nodos relevantes y desde cada origen y destino potencial hasta estos nodos relevantes.
En [6] se utiliza la jerarquía de la red de carreteras para particionar la red en áreas y pre-calcular los caminos óptimos en estas áreas. Este enfoque utiliza el hecho de que algunas calles son más transitadas que...
Rafael Rodríguez-Puente y Manuel S. Lazo-Cortés
Universidad de las Ciencias Informáticas, La Habana, Cuba
rafaelrp@uci.cu, manuellazo55@gmail.com
Resumen. Los algoritmos relacionados con la teoría de grafos han sido ampliamente estudiados. Varios estudios se enfocan en la disminución de la complejidad temporal de estos algoritmos. Lastécnicas utilizadas en este sentido, generalmente se basan en reducir un grafo o el espacio de búsqueda de solución, eliminando información redundante para el problema específico que se desea resolver. El proceso de reducción de un grafo consiste en obtener grafos más pequeños (con menos vértices) que tengan las características principales o relevantes del grafo original. En el caso de labúsqueda de caminos óptimos, los algoritmos que hacen uso de la reducción de grafos o del espacio de búsqueda de solución, no garantizan la obtención del óptimo en todos los casos. Lo mismo ocurre en otros tipos de problemas tales como la reducción de grafos en redes de workflow, de computadoras, etc. En este trabajo se propone un algoritmo de reducción de grafos sin pérdida de información. La propuestatiene una forma flexible de especificar la manera en que se quiere reducir el grafo; por consiguiente, puede ser utilizada en la solución de varios tipos de problemas, contribuyendo a la obtención de respuestas óptimas en tiempos menores.
Palabras clave. Reducción de grafos, reescritura de grafos, búsqueda de caminos óptimos.
1. Introducción
La teoría de grafos ha sido ampliamente estudiada enlos últimos años, con énfasis en los algoritmos sobre grafos. Varios de estos algoritmos tienen un elevado costo computacional y algunos son diseñados para resolver problemas NP o NP-Duros. Por consiguiente, varios estudios están relacionados con la reducción de la complejidad computacional de estos algoritmos.
Una de las estrategias que se ha utilizado consiste en reducir el grafo teniendo encuenta el problema que se está solucionando. Esto se sustenta en el hecho de que el tiempo de ejecución de estos algoritmos, generalmente, depende del número de vértices del grafo en cuestión. El proceso de reducción de un grafo consiste en obtener grafos más pequeños (con menos vértices) que tengan las características principales o relevantes del grafo original.
En la revisión bibliográfica realizadasobre este tema, se aprecia que varios algoritmos de reducción están enfocados en mantener las características relevantes de grafos que representan redes de carreteras. Esto se realiza con el objetivo de disminuir los tiempos en la búsqueda de caminos óptimos.
En este sentido se pueden mencionar varios trabajos, por ejemplo, en [7] Gutman propone un algoritmo en el cual se define un atributo delos vértices llamado reach, este atributo es una medida de la relevancia del vértice. El atributo reach se calcula utilizando el grafo, el mismo contribuye a reducir el tiempo de ejecución en la búsqueda de caminos óptimos reduciendo el espacio de búsqueda de solución.
Una propuesta relevante de algoritmo de reducción, en grafos que representan redes de carreteras, utiliza la jerarquía de la redcomo criterio de reducción. Varias estrategias utilizan este hecho, por ejemplo, en [18] se propone un algoritmo para construir jerarquías de redes, así como ejecutar consultas sobre la misma. Los autores alcanzan tiempos de ejecución menores y muestran la factibilidad de la propuesta. Otra propuesta introduce un enfoque similar al propuesto por Gutman [1]. Los autores usan nodos relevantes(transit nodes) para viajes de larga distancia, pre-calculando los caminos óptimos entre cada par de nodos relevantes y desde cada origen y destino potencial hasta estos nodos relevantes.
En [6] se utiliza la jerarquía de la red de carreteras para particionar la red en áreas y pre-calcular los caminos óptimos en estas áreas. Este enfoque utiliza el hecho de que algunas calles son más transitadas que...
Leer documento completo
Regístrate para leer el documento completo.