Ejem Programación Dinámica

PROGRAMACIÓN DINÁMICA - ALGORITMOS AVANZADOS

Network

----------------------------------

Profesor Guía: --------------
Ayudante Laboratorio: -----------
Laboratorio Algoritmos Avanzados

TABLA DE CONTENIDO
CAPÍTULO 1. INTRODUCCIÓN 2
CAPÍTULO 2. ANÁLISIS 4
2.1 EXPLICACIÓN DE LA SOLUCIÓN 4
2.1.1 Explicación de la idea de solución 4
2.1.2 Explicación del proceso mentalinvolucrado 5
2.1.3 Estrategia encontrada 6
2.1.4 Pseudocódigo 7
2.2 INDICACIÓN DEL MÉTODO 13
2.2.1 Explicación del método a utilizar 13
2.2.2 Relación entre solución encontrada y método pedido 14
2.3 TRAZA 15
2.3.1 Explicación y Desarrollo de la traza 15
2.4 DESCRIPCIÓN DE LA IMPLEMENTACIÓN 18
2.4.1 Explicación del lenguaje utilizado 18
2.4.2 Fundamentación de la estructura de datos elegida 182.4.3 Explicación de la implementación 19
2.5 ANÁLISIS TEMPORAL 20
2.5.1 Análisis temporal del comportamiento y obtención del Orden 20
2.5.4 Conclusiones 21
2.6 FUNDAMENTACIÓN DE LA EFICIENCIA 21
2.6.1 Proposición de mejora 22
CAPÍTULO 3 - CONCLUSIÓN 22
ANEXO 23
Manual de usuario: 23
Requerimientos mínimos: 23
Manual de ejecución: 23

CAPÍTULO 1. INTRODUCCIÓN

Dentro de la ampliagama de problemas, es posible clasificarlos en tres grandes conjuntos tipo, estos son: problemas de decisión, problemas de localización y problemas de optimización. Este último, consta básicamente en buscar la solución más eficiente a un problema dado.
En esta ocasión, el problema de optimización tomará mayor preponderancia en este laboratorio, ya que el objetivo no es una búsqueda exhaustiva deuna solución, sino que se busca de alguna forma no repetir pasos o combinaciones, de tal manera que se reduzca el tiempo de búsqueda.
Es por esto, que se le ha solicitado al autor, que utilice el método de “Programación dinámica” (P.D.) para resolver el problema llamado “Network” entregado en horarios de ayudantía.
Este tipo de algoritmo, consta básicamente en preponderar tres enfoques enparticular al momento de planificar un modelo que resuelva el problema dado mediante pasos secuenciales estructurados.
En primer lugar, es necesario desmenuzar el problema en sub-problemas superpuestos, de tal manera que sea más fácil resolver un conjunto de problemas de baja dificultad, a resolver un solo problema de dificultad elevada. Es por esto, que se dice que casi todo problema (no se menciona“todo”, para no caer en falacia) que se pueda resolver mediante el método de división y conquista, es posible resolverlo mediante P.D.
En segundo lugar, hay que tener en cuenta subestructuras óptimas para un desarrollo modular.
Y por último, tomar en cuenta la “memoización” para no repetir cálculos o procedimientos previamente procesados en pos de agilizar el tiempo de ejecución.

CAPÍTULO 2.ANÁLISIS

2.1 EXPLICACIÓN DE LA SOLUCIÓN

2.1.1 Explicación de la idea de solución

El escenario consiste básicamente, en que una Compañía de Líneas de Teléfonos (CLT)ha establecido una red de líneas telefónicas bidireccionales en donde cada teléfono está conectado a otro mediante un “cable” por el cual es posible realizar una comunicación entre teléfonos, ya sea de forma directa (adyacente) opor un recorrido de líneas telefónicas atravesando otros teléfonos. Cada teléfono tiene como atributo un numero entero de 1 hasta N (N<100) en donde este número es único en su tipo.
El problema, consiste básicamente en que cada lugar en donde se sitúa un teléfono, de vez en cuando se corta el suministro eléctrico. Por lo tanto, dependiendo de la estructura de la red telefónica, haycircunstancias en donde no es posible realizar una comunicación entre dos lugares a causa de la falla eléctrica en dicho lugar, dado que para que la conexión entre estos dos lugares se realice, es estrictamente necesaria de la infalibilidad del lugar dado. A este lugar, se le denomina local “crítico”.
Dado lo anterior, se le ha solicitado al autor, que desarrolle un algoritmo utilizando programación...