A Look at Algorithm BEPtoPNST

Autor: García-Ojeda, Juan C.
Rok vydání: 2020
Předmět:
Zdroj: Revista Ingenierías Universidad de Medellín, Volume: 20, Issue: 39, Pages: 115-128, Published: 28 JUN 2022
ISSN: 2248-4094
1692-3324
DOI: 10.22395/rium.v20n39a7
Popis: This work analyzes the computational complexity of algorithm BEPtoPNS T which transforms a building-evacuation problem (BEP) into a time-expanded, process-network synthesis (PNS T ) problem. The solution of the latter is achieved by resorting to the P-graph method which exploits the combinatorial nature of a BEP. Unlike other approaches, the P-graph method provides not only the optimal solution (best evacuation route as a function of egress time), but also the best n sub-optimal solutions. For the complexity analysis, a generic processor, and a Random-access machine (RAM) model were deployed as well as a mathematical model to calculate the number and cost of the operations performed. It was observed that algorithm BEPtoPNS T exhibits an asymptotic complexity of order O ( T | A | (| N | -k)). When solving a BEP, however, the total complexity grows exponentially with order O (T | A | (| N | -k)) + O (2 h )) in the worst case; where h represents the total number of operating units specified in the corresponding PNS T problem. Nevertheless, the computational complexity can be reduced significantly when the P-graph method is deployed. Resumen El presente trabajo estudia y analiza la complejidad computacional, en el peor de los casos, del algoritmo BEPtoPNS T . El objetivo de BEPtoPNS T 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, PNS T ), los cuales se solucionan por medio del método P-graph. La relevancia de analizar el algoritmo BEPtoPNS T se sustenta en el hecho que el método P-graph explota la naturaleza combinatoria de un BEP luego de ser transformado en un PNS T . 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; característica que a la fecha no ofrecen otros métodos de optimización. Para el análisis del algoritmo BEPtoNPS T , 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 (2 N )), en el peor de los casos.
Databáze: OpenAIRE
Externí odkaz: