| Título: | Estudio comparativo de diversos métodos de solución del problema del agente viajero (PAV) |
| Autores: | Castañeda Roldán, Carolina Yolanda |
| Fecha: | 2000-05-19 |
| Publicador: | Universidad de las Américas Puebla |
| Fuente: |
Ver documento |
| Tipo: |
Electronic Thesis or Dissertation Tesis |
| Tema: |
Ciencias con Especialidad en Ingeniería en Sistemas Computacionales Computer algorithms Real-time programming |
| Descripción: | 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 tres métodos exactos como son : "Búsqueda Exhaustiva Ingenua (Naive Search Exhaustive)", "Ramificación y Acotamiento Ingenuo (Naive Branch and Bound)" y el de "Una Mejor Ramificación y Acotamiento (A Better Branch and Bound)". Los métodos aproximados seleccionados fueron : "Dos Optimal", "Adaptación Prim", "Híbrido Dos Optimal-Prim" y el de "Red Neuronal de Hopfield". Se adaptó el Método Prim que es para árboles abarcadores minimales de manera que pudiera trabajar para la solución del PAV llamándolo Adaptación Prim. Este obtuvo excelentes resultados en velocidad de respuesta con respecto a los demás aproximados. Se hibridó el Método Dos-Opt con Adaptación Prim y el promedio del Error Relativo Aproximado se redujo, lo que significa que vale la pena híbridar métodos para poder obtener métodos que proporcionen mejores resultados en exactitud. Con respecto a la Red Neuronal de Hopfield se mejoró la salida de la misma, porque en ocasiones producía nodos repetidos, es decir rutas no válidas. Por lo que ahora toda ruta que arroja este método es una ruta válida. Palabras clave: Análisis y Diseño de Algoritmos |
| Idioma: | Español |
1 Casa de Retiro para el Adulto Mayor "Nuevo Encuentro" ubicada en San Miguel de Allende, Guanajuato por Sáenz de Miera Cuatlayol, Fernando | 6 Estrategias conceptuales de diseño urbano ante una crisis de recursos energéticos en el Distrito Federal por Gómez Machuca, Trinidad de los Ángeles,Juárez Díazbarriga, Miguel Ángel |
2 Centro de Diseño Textil y Moda por Serapio Lara, Génesis Raquel | 7 The Ownable City: Urban Strategies That Promote Identity por Ramírez Stege, Alexandra |
3 Proyecto de rehabilitación paisajística del Parque Alameda Rafael Murillo Vidal por Jiménez Vega, Abigail Eugenia | 8 Rediseño del espacio residual en Periférico Ecológico del Municipio de Puebla por Casas Garza, José Carlos |
4 La Parroquia Urbana por Vidal Ramos, Hector Alcides | 9 Casa - Habitación en Ocuituco, Morelos por Lifshitz Medina, Yuliette |
5 Asia Town + Casa Asia Puebla por Nájera Rendón, Daniel | 10 |