Una mirada al algoritmo BEPtoPNST

Resumen

El presente trabajo estudia y analiza la complejidad computacional, en el peor de los casos, del algoritmo BEPtoPNST. El objetivo de BEPtoPNST es transformar problemas de rutas de evacuación en edificios (Building--Evacuation Problems, BEP) en problemas de síntesis de redes procesos de tiempo extendido (Time-Extended, Process-Network Synthesis, PNST), los cuales se solucionan por medio del método P-graph. La relevancia de analizar el algoritmo BEPtoPNST se sustenta en el hecho que el método P-graph explota la naturaleza combinatoria de un BEP luego de ser transformado en un PNST. El método P-graph no sólo provee la solución óptima (mejor ruta de evacuación en función del tiempo de egreso), sino que también provee las mejores n soluciones subóptimas; caracte-rística que a la fecha no ofrecen otros métodos de optimización. Para el análisis del algoritmo BEPtoNPST, se consideró un procesador genérico, el modelo Random-access machine, RAM, así como un modelo matemático para calcular el número de operaciones ejecutadas y sus costos, resultando en una complejidad asintótica de orden O ( T | A | (| N | –k)). Sin embargo, la complejidad total del proceso, incluyendo el método P-graph, crece de manera exponencial,es decir, O (T | A | (| N | –k)) + O (2N )), en el peor de los casos.