PDF de programación - Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

1.

INTRODUCCIÓN

1.1. PRESENTACIÓN
1.2. ANÁLISIS DE ANTECEDENTES
1.3. OBJETIVOS
1.4. APLICACIÓN
1.5. PLANIFICACIÓN DEL TRABAJO

2. ANÁLISIS DE REQUERIMIENTOS

2.1. REQUERIMIENTOS
2.1.1. QUÉ OFRECE LA LIBRERÍA DE CAMINOS MÍNIMOS.
2.1.2. NECESIDAD DE UNA LIBRERÍA DE ESTE TIPO.
2.1.3. USO DE LA LIBRERÍA.
2.1.4. USUARIOS

3. EL PROBLEMA DEL CAMINO MÍNIMO

4

4
5
6
6
7

9

9
9
10
12
12

13

13
3.1. DEFINICIONES
3.2. MÉTODO GENERAL DEL PROBLEMA DEL CAMINO MÍNIMO (UN ORIGEN/MUCHOS DESTINOS) 15
16
3.2.1. ALGORITMO GENÉRICO DEL CAMINO MÍNIMO
17
3.3. IMPLEMENTACIONES DEL ALGORITMO GENÉRICO
17
3.3.1. MÉTODOS ETIQUETADORES (LABEL SETTING METHODS).
17
3.3.2. MÉTODOS CORRECTORES DE ETIQUETA (LABEL CORRECTING METHODS).
18
3.4. MÉTODOS ETIQUETADORES (DIJKSTRA)
19
3.4.1. TIEMPO DE EJECUCIÓN DEL ALGORITMO DE DIJKSTRA
20
3.4.2. EJEMPLO GRÁFICO DE EJECUCIÓN DEL ALGORITMO
21
3.5. OTRAS VERSIONES DEL ALGORITMO
21
3.5.1. ALGORITMO DE DIJKSTRA HACIA ATRÁS
21
3.5.2. ALGORITMO DE DIJKSTRA BIDIRECCIONAL
22
3.6. IMPLEMENTACIONES DEL ALGORITMO DE DIJKSTRA
22
3.6.1. IMPLEMENTACIÓN DE DIAL
24
3.6.2. IMPLEMENTACIONES CON COLAS DE PRIORIDAD
25
3.6.3. IMPLEMENTACIÓN CON HEAP BINARIO
25
3.6.4. IMPLEMENTACIÓN CON D-HEAP
25
3.6.5. IMPLEMENTACIÓN CON HEAP DE FIBONACCI
25
3.6.6. IMPLEMENTACIÓN CON RADIX HEAP
27
3.7. MÉTODOS CORRECTORES DE ETIQUETA
27
3.7.1. IMPLEMENTACIÓN CON “DEQUEUES”
28
3.8. RESUMEN Y RECAPITULACIÓN DE LOS ALGORITMOS
29
3.8.1. GRAFOS COMPLETOS. AUMENTANDO EL NÚMERO DE NODOS.
29
3.8.2. GRAFO COMPLETO PEQUEÑO. AUMENTANDO COSTE MÁXIMO DE ARISTA.
30
3.8.3. GRAFO COMPLETO GRANDE. AUMENTANDO COSTE MÁXIMO DE ARISTA.
30
3.8.4. GRAFO PEQUEÑO. DISMINUYENDO DENSIDAD DE ARISTAS.
30
3.8.5. GRAFO GRANDE. DISMINUYENDO DENSIDAD DE ARISTAS.
31
3.8.6. GRAFO DISPERSO PEQUEÑO. AUMENTANDO COSTE MÁXIMO DE ARISTA.
31
3.8.7. GRAFO DISPERSO GRANDE. AUMENTANDO COSTE MÁXIMO DE ARISTA.
32
3.8.8. RESUMEN

4. IMPLEMENTACIÓN

33

1

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

4.1. REPRESENTACIONES DE UN GRAFO
4.1.1. MATRIZ DE INCIDENCIAS NODO-ARISTA
4.1.2. MATRIZ DE ADYACENCIAS NODO-NODO
4.1.3. LISTAS DE ADYACENCIA
4.1.4. REPRESENTACIONES EN ESTRELLA
4.2. DISEÑO DE LA REPRESENTACIÓN DEL GRAFO
4.2.1. ELEMENTOS DEL GRAFO
EJEMPLO:
4.3. IMPLEMENTACIÓN DE LAS ESTRUCTURAS DE DATOS.

5. ESPECIFICACIÓN DEL SOFTWARE.

5.1. MODELO CONCEPTUAL.
5.1.1. INTRODUCCIÓN.
5.1.2 APARICIÓN DE NUEVOS ALGORITMOS
5.1.3. HERRAMIENTA DE ESPECIFICACIÓN Y DISEÑO
5.1.4. DIAGRAMA DE CLASES
5.1.5. CLASES DEL DOMINIO
5.1.6. CASOS DE USO
5.1.7. DIAGRAMA DE SECUENCIA
5.1.4. PSEUDO CÓDIGO DE LAS OPERACIONES
GRAFO
CAMMIN
DIJKSTRA
5.2. HERRAMIENTAS Y BASE TEÓRICA
5.2.1 PROGRAMACIÓN ORIENTADA A OBJETOS
5.2.2. C++

6. MANUAL DE USO

6.1 INTRODUCCIÓN
6.2. PROCEDIMIENTO PARA EJECUTAR UN ALGORITMO DE LA LIBRERÍA
6. 2. 1. UNIDIRECCIONAL:
6. 2. 2. BIDIRECCIONAL:
6. 3. CREACIÓN DEL GRAFO
6.4. CLASES Y MÉTODOS PÚBLICOS
6.4.1. GRAFO
6.4.2. CAMMIN

7. RESULTADOS

7.1. PREPARATIVOS
7.2. RESULTADOS:
7.3 ANÁLISIS DE LOS RESULTADOS
7.3.1. GRAFOS COMPLETOS.
CONCLUSIONES
7.3.2. GRAFO COMPLETO PEQUEÑO. AUMENTANDO COSTE MÁXIMO DE ARISTA.
7.3.3. GRAFO COMPLETO GRANDE. AUMENTANDO COSTE MÁXIMO DE ARISTA.
7.3.4. GRAFO PEQUEÑO. DISMINUYENDO DENSIDAD DE ARISTAS.
7.3.5. GRAFO GRANDE. DISMINUYENDO DENSIDAD DE ARISTAS.
7.3.6. GRAFO DISPERSO PEQUEÑO. AUMENTANDO COSTE MÁXIMO DE ARISTA.
7.3.7. GRAFO DISPERSO GRANDE. AUMENTANDO COSTE MÁXIMO DE ARISTA.

2

35
35
36
37
38
39
39
40
42

43

43
43
45
45
46
48
49
49
51
51
53
54
57
57
58

59

59
60
62
62
63
64
64
66

67

67
69
72
72
73
73
74
74
75
76
77

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

7.4. PRIMERAS CONCLUSIONES
7.5. TABLA CONSEJO SOBRE UTILIZACIÓN DE LOS ALGORITMOS SEGÚN PARÁMETROS DE GRAFO
DE ENTRADA.

78

79

7. APLICACIÓN.

7.1. INTRODUCCIÓN
7.2 DESCRIPCIÓN DEL PROBLEMA.
7.3 APLICACIÓN REAL
7.4 ANÁLISIS DE LA APLICACIÓN
7.5. CÓMO SUSTITUIR EL CÓDIGO
7.6 SUSTITUCIÓN DEL CÓDIGO
7.6.1. CREACIÓN DEL GRAFO.
7.6.2. NODOS ORIGEN Y DESTINO DEL PROBLEMA
7.6.3. EJECUCIÓN DEL ALGORITMO
7.7. RESULTADOS

8. APÉNDICE

8.1. ESTRUCTURAS DE DATOS
8.2. D-HEAPS
8.2.1. DEFINICIÓN Y PROPIEDADES DE UN D-HEAP
8.2.2. ALMACENAMIENTO DE UN D-HEAP.
8.2.3. PROPIEDAD ORDEN DEL HEAP
8.2.4. INTERCAMBIO
8.2.5. RECUPERAR EL ORDEN DEL HEAP
8.2.6. OPERACIONES DEL HEAP
8.3. HEAPS DE FIBONACCI
8.3.1. PROPIEDADES
8.3.2. DEFINICIÓN Y ALMACENAMIENTO DE UN HEAP DE FIBONACCI
8.3.3. UNIENDO Y CORTANDO
8.3.4. INVARIANTES
8.3.5. RESTAURANDO EL INVARIANTE 2
8.3.6. RESTAURANDO EL INVARIANTE 3
8.3.7. OPERACIONES

9. BALANCES Y CONCLUSIONES

9.1. COMPARACIÓN TIEMPO ESTIMADO CON TIEMPO REAL
9.2. BALANCE ECONÓMICO
9.3. CONCLUSIONES
9.4. LÍNEAS ABIERTAS

10. BIBLIOGRAFÍA

10.1. LIBROS
10.2. ARTÍCULOS EN REVISTAS
10.3. DE INTERNET:
10.4. DE LA APLICACIÓN DE PROTECCIÓN DE DATOS



3

82

82
82
82
83
86
87
87
88
89
90

92

92
92
92
93
94
94
94
95
96
96
96
97
98
98
99
100

101

101
102
103
104

105

105
105
106
107

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

1. Introducción



1.1. Presentación

Este proyecto tiene como objetivo desarrollar una librería cuyo contenido serán diferentes
versiones de algoritmos que solucionan el problema de encontrar el camino mínimo entre nodos de
una red o grafo de forma eficiente.


Una vez implementada, se empleará en una aplicación real de protección de datos estadísticos en la
que se ejecutan numerosos subproblemas que no son más que búsquedas de caminos mínimos en
redes. Dicha aplicación dispone ya de un módulo básico que implementa una única versión del
algoritmo básico de Dijkstra. Una vez creada la librería, se sustituirá ésta por el módulo existente, lo
que permitirá evaluar diferentes variantes del algoritmo, minimizando así los tiempos de espera de
cada subproblema y, como resultado, el de toda la aplicación.


El proyecto se compone de varias partes:

Básicamente, la librería consistirá en diferentes implementaciones del conocido algoritmo de
Dijkstra más otros, llamados correctores de etiqueta, que pueden ser más idóneos y mejorar el tiempo
de cálculo para ciertos tipos de redes o topologías de éstas.



Además, cada implementación tendrá dos variantes: la original, que encuentra dado un nodo
origen todos los caminos mínimos al resto de nodos de la red y una versión que encuentra el camino
mínimo entre dos nodos dados origen y destino. Ésta última versión de buscar el camino mínimo entre
dos nodos es la que verdaderamente necesita la aplicación real y es por ello de su existencia en el
proyecto.


Para el algoritmo de Dijkstra, las versiones difieren entre sí en el uso de distintas estructuras de
datos internas durante su ejecución, que ayudan a reducir el tiempo de cálculo, aunque a priori, y para
un cierto tipo de red, no es fácil intuir qué versión será la más beneficiosa. Es decir, cada tipo de
implementación no es una mejora de otra, sino una forma diferente de intentar aumentar la eficiencia.

4

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

1.2. Análisis de antecedentes

Por extraño que parezca en un principio, no existe ninguna biblioteca o aplicación que reúna las

características deseadas en este proyecto.


Normalmente, en las librerías existentes especializadas en problemas con grafos o redes, se puede
encontrar como mucho uno o dos algoritmos para la resolución de los caminos mínimos. En concreto,
el algoritmo básico de Dijkstra y una mejora eficiente usando d-heaps.


Estos algoritmos son más que suficientes para aplicaciones que necesiten aplicarlos unas pocas
veces o que la ejecución de los mismos no sea una parte esencial del total del programa. El problema
surge cuando en la aplicación la mayor parte del tiempo se dedica a buscar caminos mínimos y, por
tanto, es crucial la eficiencia de este tipo de algoritmos.


Posiblemente, y con muchos esfuerzo (temporal o económico) se podrán encontrar otras
versiones, pero con interficies distintas o incluso lenguajes de programación diferentes. De todas
formas, después de una búsqueda intensiva no se han encontrado más de tres algoritmos
implementados. El resto, únicamente aparece en literatura.


Afortunadamente, sí que existe bastante documentación con propuestas de algoritmos, ya sea en

forma de libros especializados en grafos y redes o en revistas científicas e informáticas.

5

Desarrollo de una librería para caminos mínimos. Aplicación a un problema de protección de datos.

1.3. Objetivos


- Diseñar una biblioteca que contenga distintas versiones de algoritmos que resuelven el problema

del camino mínimo en redes.


- Sencillez de uso de los algoritmos. El usuario debería nada más que proporcionar los mínimos

datos en un tipo de formato predeterminado y elegir la versión del algoritmo a ejecutar.


- Capacidad de detectar anomalías y comunicarlas al agente externo que ejecute las funciones de la

biblioteca.


- Máxima eficiencia temporal y espacial, aunque si es necesario se sacrificará el segundo a favor del

primero.


-

Implementar las estructuras de datos que emplearán las distintas versiones de los algoritmos, de
forma lo más eficiente posible (d-heaps, fibonnaci-heaps, colas circulares...).


- Una vez se tengan dichas estructuras, implementar las versiones de los al