ÁRBOL DE CAMINOS MÍNIMOS: ENRUTAMIENTO, ALGORITMOS APROXIMADOS Y COMPLEJIDAD

Efren Romero Riaño, Gabriel Mauricio Martínez Toro, Dewar Rico-Bautista

Resumen


El documento aborda la temática relacionada con los algoritmos aproximados como método para solución de problemas computacionalmente complejos. El objetivo de este paper, es presentar un análisis comparativo entre tres enfoques clásicos de solución de algoritmos y el enfoque de solución mediante algoritmos aproximados. Este análisis incluye la descripción de los códigos y pseudocódigos, así como su análisis comparativo en términos de complejidad en tiempo y espacio. La metodología implementada fue de revisión basada en indicadores biblio métricos de las fuentes y posterior análisis de contenido de los documentos seleccionados. La complejidad computacional de los algoritmos analizados se puede dividir en complejidad de tiempo y de espacio, cada una de estas agrupan los problemas según sus características dentro de los grupos P, NP, PSPACE, NPSPACE, entre otros. A través de la reducción del Set Cover Problem en una versión del Minimun Spanning Tree, MST, se logró comprobar la complejidad de este problema de conectividad. La eficiencia de los algoritmos se determinó con base en los recursos que son utilizados en el momento en que son ejecutados. Se presenta un paralelo entre algoritmos aproximados y algoritmos alternativos a la luz del ejemplo de la reducción del set cover en un árbol de expansión mínimo, logrando evidenciar la complejidad en algoritmos de conectividad. La complejidad computacional se mide a la luz del uso de los recursos, bien sea el uso de los recursos de tiempo o espacio, generando clasificaciones de problemas según sus características particulares medidas por estos dos parámetros.

Texto completo:

PDF

Referencias


Araque, J., Díaz, J., & Gualdrón, O. (2013). Optimización del thd en un convertidor multinivel monofásico usando algoritmos genéticos. Revista Colombiana Tecnologías de Avanzada , 1(21), 60-66. doi:https://doi.org/10.24054/16927257.v21.n21.2013.297.

Ariganello, E. (2014). Redes Cisco. Guía de estudio para la certificación. CCNA Routing y switching (Primera ed.). México D.F., México: Alfaomega. Recuperado el 15 de Mayo de 2017.

Barbehenn, M. (1998). A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices. IEEE Transactions on Computers, 47(2), 263. https://doi.org/10.1109/12.663776.

Bollobás, B., & Riordan, O. (1993). Dijkstra â€TM s Algorithm. Network, 69(1959), 36114. Retrieved from http://www.ncbi.nlm.nih.gov/pubmed/21282851.

Duarte Muñoz, A. (2007). Metaheuristicas. Madrid: Dykinson.

Fan, D., & Shi, P. (2010). Improvement of Dijkstra’s algorithm and its application in route planning. 2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery. https://doi.org/10.1109/FSKD.2010.5569452.

Frederickson, G. N., Hecht, M. S., & Kim, C. E. (1976). Approximation agorithms for some routing problems. 17th Annual Symposium on Foundations of Computer Science (Sfcs 1976), 7(2), 178–193. https://doi.org/10.1109/SFCS.1976.6.

Garroppo, R. G., Giordano, S., & Tavanti, L. (2010). A survey on multi-constrained optimal path computation: Exact and approximate algorithms. Computer Networks, 54(17), 3081–3107. https://doi.org/10.1016/j.comnet.2010.05.017.

Gupta, A., & Könemann, J. (2011). Approximation algorithms for network design: A survey. Surveys in Operations Research and Management Science, 16(1), 3–20. https://doi.org/10.1016/j.sorms.2010.06.001.

Klinkowski, M., & Walkowiak, K. (2016). On the complexity of routing and spectrum allocation in survivable elastic optical network with unicast and anycast traffic. International Workshop on Resilient Networks Design and Modeling (RNDM). Halmstad: IEEE. doi:10.1109/RNDM.2016.7608283.

Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61(1), 227–262. https://doi.org/10.1007/BF02098290.

Levin, L., Kowalski, D. R., & Segal, M. (2015). Message and time efficient multi-broadcast schemes. Theoretical Computer Science, 569, 13–23. https://doi.org/10.1016/j.tcs.2014.12.006.

Medina Cárdenas, Y., & Rico Bautista, D. (2008). Modelo de gestión de servicios para la universidad de Pamplona: ITIL. Scientia Et Technica, XIV (39), 314-319.

Medina Cárdenas, Y., & Rico Bautista, D. (2009). Modelo de gestión basado en el ciclo de vida del servicio de la Biblioteca de Infraestructura de Tecnologías de Información (ITIL). Revista Virtual Universidad Católica del Norte, (27), 1-21.

Medina, Y., Rico, D., & Areniz, Y. (2016). Modelo estratégico para la gestión tecnológica en la organización: plan táctico de la calidad (ITIL & ISO 20000). (I. T. Metropolitano, Ed.) Ocaña: Fondo Editorial ITM. doi:https://doi.org/10.22430/9789585414006.

Méndez, L., Rodriguez-Colina, E., & Medina, C. (2014). Toma de Decisiones Basadas en el Algoritmo de DIJKSTRA. Redes de Ingeniería, 4(2), 2013. Retrieved from http://revistas.udistrital.edu.co/ojs/index.php/REDES/article/view/6357/7872.

Parra, C., & Herrera, J. (2013). Aplicación de los sistemas de detección de intrusos y la tecnología de agentes en el monitoreo inteligente de redes de datos. Revista Colombiana de Tecnologías de Avanzada, 106-110. doi:https://doi.org/10.24054/16927257.v22.n22.2013.417.

Patiño, N., Moreno, M., & Toro, E. (2013). Modelamiento matemático del problema de ocupación de quirófanos. Revista Colombiana Tecnologías de Avanzada, 2(20), 43-49. doi:https://doi.org/10.24054/16927257.v20.n20.2012.187.

Rojas, M., & Sánchez, M. (2012). Arquitectura de software para el servicio de soporte de tecnología de información basada en servicios web. Revista Colombiana Tecnologías de Avanzada, 2(20), 144-150. doi:https://doi.org/10.24054/16927257.v20.n20.2012.201.

Rodriguéz Gálvez, M. D. (Enero de 2009). Problemas de Optimozación en Arboles Generadores. Trabajo de fin de carrera. Madrid.

Santos, L., & Flórez, A. (2013). Metodología para el análisis forense en linux. Revista Colombiana Tecnologías de Avanzada, 2(20), 90-96. doi:https://doi.org/10.24054/16927257.v20.n20.2012.194.

Siachalou, S., & Georgiadis, L. (2003). Efficient QoS routing. Computer Networks, 43(3), 351–367. https://doi.org/10.1016/S1389-1286(03)00286-X.

Skiena, S. (1982). The Algorithm Design Manual Second Edition. Department of Computer Science State University of New York at Stony Brook New York, USA.

Universidad de los Andes. (2016). Diseño y Análisis de algoritmos. DISC – Departamento de Ingeniería de Sistemas y Computación. Recuperado el 15 de Mayo de 2017, de https://cursos.virtual.uniandes.edu.co/isis1105/.

Vazirani, V. V. (2003). Approximation Algorithms. Berlin: Springer.

Williamson, D. P., & Shmoys, D. B. (2 de 2 de 2011). The Design of Approximation Algoritms. Cambridge: Cambridge University Press.

Yin, C., & Wang, H. (2010). Developed Dijkstra shortest path search algorithm and simulation. In 2010 International Conference on Computer Design and Applications, ICCDA 2010 (Vol. 1). https://doi.org/10.1109/ICCDA.2010.5541129.




DOI: https://doi.org/10.24054/16927257.v31.n31.2018.2780

Enlaces refback

  • No hay ningún enlace refback.

Comentarios sobre este artículo

Ver todos los comentarios