INTRODUCCIÓN
El presente trabajo de investigación tiene como objetivo descubrir diferentes soluciones para el famoso y codiciado problema del vendedor viajero, más conocido por su nombre en original en inglés Traveling Salesman Problem o TSP. Este problema responde a la siguiente pregunta: “...dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?...” (Wikipedia).
Tomando en cuenta este enunciado y lo que se requiere, se nos encomendó implementarlo con los algoritmos estudiados hasta la primera mitad del ciclo. Estos incluyen Fuerza bruta, Backtracking, BFS, DFS, Dijkstra.
Para nuestros propósitos, nos hemos enfocado en 3 de estos. En el primer capítulo se abordará el algoritmo de Fuerza Bruta, en el segundo abordaremos Backtracking y finalmente en el tercero veremos Dijkstra. En cada uno de ellos se ha considerado los puntos importantes requeridos en este proyecto, como lo son marco teórico, algoritmo, complejidad e implementación.
Finalmente, nuestras motivaciones para realizar este proyecto han sido, primero entender y desglosar este tipo de problemas NP para poder descifrar una posible solución, segundo, poner en práctica los conocimientos adquiridos en clase, tercero, comprobar que el trabajo en equipo en época de pandemia, ha sido un éxito, cuarto y finalmente, seguir avanzando en nuestra travesía hacia futuros ingenieros de software que desarrollan todos las tareas que se les piden implementar con éxito.
INTEGRANTES:
Gamarra Sebastián
Hernández Nicolás
Litano Joel
Nuñez Sergio