Sistemas distribuidos y Paralelos

Universidad Autónoma de Nuevo León[pic 1][pic 2]

Facultad de Ingeniería Mecánica y Eléctrica

Sistemas distribuidos y Paralelos

Proyecto TSP

M.C Carlos Adrian

Equipo:

David Zamarrón Najar 1586835

Jose Eduardo  Sanchez  Sustaita  1637574

Carolina Guillen Tijerina 1627852

Antonio Fabián Vazquez Leal 1619268

Eleazar Vicente Ruelas Vazquez 1614633

Fecha:

25 de Septiembre del 2017

Índice

Agente Viajero:        3

Objetivo:        3

Justificación:        4

Metodología Seleccionada:        4

Lenguaje:        4

Modelado de problemas:        4

Grafos de dependencia        5

Análisis de los resultados a forma lineal        7

Análisis de los resultados a forma paralela        8

Comparación de ambos gráficos comparativos y conclusiones        9

Conclusiones        10

Bibliografía        11

Agente Viajero:

El problema del agente viajero o TSP por sus siglas en inglés es uno de los problemas más famosos y complejos de las ciencias computacionales y ha sido abordado por varias ramas de la ingeniería y por distintas razones, su principal aplicación es la de rutear desde distintas perspectivas, ya sea un proceso que lleva una secuencia específica o una distribución lógica en donde intervienen los transportes, y buscan la mejor ruta disponible con los mejores precios y la menor distancias.

Objetivo: 

Encontrar una ruta completa en donde conecte todas las ciudades deseadas dependiendo del cliente con los costos más bajos y abarcando las mayores distancias en donde el usuario volverá a su punto de partida.

Justificación:

El sistema de transporte que el estudio presenta ya que muchos usuarios/clientes no sabe que el país cuenta con algunos lugares en donde puede viajar en corto tiempo en donde nuestra misión principal el optimizar el costo mediante al viaje seleccionado dentro del país (México) y mostrara las alternativas más completas.

Metodología Seleccionada:

• El método más básico es el conocido con el nombre de fuerza bruta, que consiste en el cálculo de todos los posibles recorridos, lo cual se hace extremadamente ineficiente y casi que se imposibilita en redes de gran tamaño.
• Método heurístico que se han desarrollado por la complejidad en el cálculo de soluciones óptimas en redes robustas, es por ello que existen métodos como el vecino más cercano, la inserción más barata y el doble sentido.
• Algoritmos que proporcionan soluciones óptimas, como el método de branch and bound (ramificación y poda), que trabaja el problema como un algoritmo de asignación y lo resuelve por medio del método simplex.

Nosotros utilizaremos el método básico ya que por cuestiones que son gran cantidad de nodos y tiempos será muy largo la elaboración.

Lenguaje:

Java

Modelado de problemas:

El programa “Agente viajero” serviría simplemente para darle un aproximado a los turistas o viajeros en cuanto tiempo tardaría en viajar a los lugares que el desee, teniendo en cuenta el dinero que lleva consigo mismo y también el tiempo que se le dio para viajar, teniendo en mente el tiempo de espera por vuelos.

Por el momento se utilizó el territorio nacional (México) para hacer el programa ya que por el momento será una base para después ir internacionalizando  

...