Resumen

Evaluar la fiabilidad de una red de flujo multiestado (MFN) es un problema NP difícil. El diagrama de decisión binario ordenado (OBDD) o sus variantes, como el diagrama de decisión multivaluado (MDD), son estructuras de datos compactas y eficientes adecuadas para tratar problemas a gran escala. En este trabajo se proponen dos algoritmos simbólicos para evaluar la fiabilidad de los MFN, MFN_OBDD y MFN_MDD. En los algoritmos, se definen varias funciones operativas para podar los diagramas de decisión generados. De este modo, el espacio de estados de las combinaciones de capacidad se comprime aún más y la complejidad operativa de los diagramas de decisión se reduce aún más. Al mismo tiempo, se llevan a cabo las pruebas teóricas y los análisis de complejidad correspondientes. Los resultados experimentales muestran lo siguiente (1) En comparación con el algoritmo de descomposición existente, los algoritmos propuestos ocupan menos espacio de memoria y menos bucles. (2) El número de nodos y el número de variables del MDD generado en el algoritmo MFN_MDD son mucho menores que los del OBDD construido en el algoritmo MFN_OBDD. (3) En dos casos con el mismo número de arcos, los algoritmos propuestos son más adecuados para calcular la fiabilidad de redes dispersas.

• Materias:Análisis Matemático Matemáticas Algebra Ingeniería Lógica matemática
• Subjects:Mathematical Analysis mathematics Algebra Engineering Mathematical logic
• Palabras claves:Fiabilidad; red de flujo multiestado (MFN); diagrama de decisión binario ordenado (OBDD); diagrama de decisión multivaluado (MDD); algoritmos; redes dispersas.
• Keywords:Reliability; Multistate Flow Network (MFN); Ordered binary decision diagram (OBDD); multivalued decision diagram (MDD); algorithms; sparse networks