Tesis profesional presentada por Carolina Yolanda Castañeda Roldán

Maestría en Ciencias con Especialidad en Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales. Escuela de Ingeniería, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Dr. Fernando Antonio Aguilera Ramírez
Vocal y Director: Dr. Mauricio Javier Osorio Galindo
Secretario: Dra. María del Pilar Gómez Gil

Cholula, Puebla, México a 19 de mayo de 2000.

Resumen

Dada la importancia de los problemas NP-Completos y sabiendo que la solución de un problema que este considerado ser NP-Completo repercute en todos los demás problemas del mismo tipo, el problema del Agente Viajero (PAV) se seleccionó en este proyecto para su estudio por ser un problema clásico NP-Completo.

Se reunieron e implementaron técnicas para su solución y se hizo un estudio comparativo de las mismas. Dentro de las técnicas seleccionadas para su implementación se encuentran...

Resumen (archivo pdf, 13 kb).

Índice de contenido

Agradecimientos (archivo pdf, 19 kb)

Introducción (archivo pdf, 21 kb)

  • 1 Clases de complejidad en las ciencias computacionales
  • 2 Definición del problema
  • 3 Objetivo general

Capítulo 1. Marco teórico del PAV (archivo pdf, 101 kb)

  • 1.1 Teoría de grafos
  • 1.2 Np-completitud
  • 1.3 Problemas de decisión
  • 1.4 Problemas de optimización

Capítulo 2. Propiedades útiles para resolver el PAV (archivo pdf, 67 kb)

  • 2.1 Caminos y circuitos eulerianos y hamiltonianos
  • 2.2 Marco histórico del PAV
  • 2.3 PAV como un problema np-completo
  • 2.4 Optimización local para el PAV
  • 2.5 Problemas importantes np completos relacionados con el PAV
  • 2.6 Teoría para el análisis de resultados

Capítulo 3. Algoritmos exactos (archivo pdf, 90 kb)

  • 3.1 Fundamentos de los algoritmos exactos
  • 3.2 Funcionamiento de un algoritmo exacto
  • 3.3 Algoritmo retroceso generalizado
  • 3.4 Método búsqueda exhaustiva ingenua
  • 3.5 Método búsqueda ramificación y acotamiento ingenuo
  • 3.6 Método búsqueda una mejor ramificación y acotamiento

Capítulo 4. Algoritmos de aproximación (archivo pdf, 132 kb)

  • 4.1 Fundamentos de los algoritmos de aproximación.
  • 4.2 Fundamentos de los algoritmos genéticos
  • 4.3 Método dos optimal
  • 4.4 Método adaptación Prim
  • 4.5 Método híbrido dos optimal - Prim
  • 4.6 Redes neuronales artificiales

Capítulo 5. Comparación de algoritmos y análisis de resultados (archivo pdf, 112 kb)

  • 5.1 Comparación de los resultados de un algoritmo exacto contra algoritmos aproximados
  • 5.2 Comparación de los resultados de un algoritmo exacto
  • 5.3 PAV geométricos y asimétricos

Capítulo 6. Resultados de la simulación del caballo de ajedrez (archivo pdf, 32 kb)

  • 6.1 Definición del problema
  • 6.2 Simulación y resultados de los movimientos del caballo de ajedrez

Capítulo 7. Conclusiones (archivo pdf, 12 kb)

  • 7.1 Resultados
  • 7.2 Aportaciones
  • 7.3 Aplicaciones y extensiones
  • 7.4 Limitaciones

Referencias (archivo pdf, 14 kb)

Apéndice A. Interfaz gráfica (archivo pdf, 509 kb)

Apéndice B. Archivos con muestreos (archivo pdf, 8 kb)

Castañeda Roldán, C. Y. 2000. Estudio comparativo de diversos métodos de solución del problema del agente viajero (PAV). Tesis Maestría. Ciencias con Especialidad en Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2000.