Optimizacion de sistemas ii

Recorrido óptimo de los nodos en una red

ÍNDICE

1.- Caminos y circuitos hamiltonianos y su optimización …... 4
1.1- Introducción, caminos y circuitos hamiltonianos ……………..… 4 1.2- Métodos para determinar caminos y circuitos hamiltonianos …………………..…………..… 11
1.2.1- Caminos hamiltonianos de un grafo ...............……………..….… 23
1.2.1.1- Ayudas para identificar grafos hamiltonianos ……....…23 1.2.1.2- Método para encontrar todos los caminos hamiltonianos de un grafo ……………….….… 25
1.2.1.2.1- Determinación de caminos elementales ……...…. 25 Multiplicación de matrices ………….……….... 26 Multiplicación latina de matrices …………...… 27 Matrices utilizadas, multiplicación latina sobre ellas y obtención de caminos elementales .....… 28 1.2.1.2.2- Determinar todos los caminos hamiltonianos(algoritmo de Kaufmann y Malgrange) …...…... 31

1.2.1.3- Optimización de los caminos hamiltonianos ……....…. 37

1.2.2- Cálculo de los circuitos hamiltonianos y su optimización ….. 38

1.3- Ejemplo completo ……………………………………………………. 40 1.4- Estructuración del programa ………………………………....……. 49
1.4.1- Soporte de datos ……………………………………….……….. 49

Página 1

Recorrido óptimo de los nodos en una red1.4.2- Desarrollo del algoritmo del proyecto en pseudocódigo …………………………..…..… 57

1.5- Interface gráfica ………………………………………………………. 98

2.- Árboles de recubrimiento mínimo ……….……..….…... 103
2.1- Introducción, árboles de recubrimiento mínimo ……..……... 104 2.2.- Implementación del proyecto en seudocódigo ....................... 125
2.2.1.- Elementos comunes a los algoritmos de Kruskal y de Prim………………………………………….. 129 2.2.2.- Implementación del algoritmo de Kruskal ........................... 133
2.2.2.2- Lógica y desarrollo de la implementación general del algoritmo de forma automática sin intervención del usuario ............................................. 135 2.2.2.3.- Implementación del algoritmo a través de la intervención del usuario seleccionando aristas sobre un grafo...................................................... 160

2.2.3.- Implementación del algoritmo de Kruskal con todas las soluciones (solución automática) ................... 180
2.2.3.1.- Situaciones posibles, algoritmo general y estructuras de datos ........................................ 181 2.2.3.2.- Solución para el grupo de aristas con el mismo valor .............................................. 193 2.2.3.3.-Solución completa tratando todas las aristas del grafo ............................................... 257 2.2.3.4.- Modificaciones del programa para resolver situaciones con demasiadas soluciones ……….…...…. 273

2.2.4.- Implementación del algoritmo de Prim .............................. 302
Página 2

Recorrido óptimo de los nodos en una red
2.2.4.1.- Lógica y desarrollo de laimplementación general del algoritmo de forma automática sin intervención del usuario ......................................... 304 2.2.4.2.- Implementación del algoritmo a través de la intervención del usuario seleccionando aristas sobre un grafo ................................................... 326

2.2.5.- Implementación del algoritmo de Prim con todas las soluciones (solución automática)................. 351
2.2.5.1.- Proceso general y soportes de datos ............................ 352 2.2.5.2.- Organigrama, variables y pseudocódigo ..................... 361

2.3.- Optimización de la aplicación para los algoritmos que calculan todas las soluciones .......................................... 396 2.4.- Método para resolver excesivas soluciones óptimas .... Bibliografía…………………………………………………………….. Conclusiones ………………………………………….………………… Apéndice A: Ejemplos de caminos y circuitos hamiltonianos calculando paso a paso las matrices intermedias …………….. Apéndice B: Notación, Símbolos y Abreviaciones ………..….. Apéndice C: Traducción de la aplicación al inglés …………... Apéndice D: Ayuda dentro de la aplicación …………………....

Página 3

Introducción, caminos y circuitos hamiltonianos...