El Problema del Viatjant de Comerç plantea la siguiente cuestión: dado un conjunto de ciudades que un viajero debe visitar, ¿en qué orden debe hacer las visitas y por qué carreteras debe pasar para minimizar la longitud total del recorrido? Este problema es conocido por ser NP-Completo, lo que significa que no existe un algoritmo polinómico conocido para resolverlo de manera eficiente.
En este proyecto, se aplicarán diferentes metodologías algorítmicas para abordar el Problema del Viatjant de Comerç en C++:
-
Greedy: Se utilizará una estrategia voraz para seleccionar en cada paso la ciudad más cercana disponible, con la esperanza de obtener una solución aceptable.
-
Backtracking: Se explorarán todas las posibles combinaciones de ciudades en un orden específico y se retrocederá cuando sea necesario para encontrar la solución óptima.
-
Branch & Bound: Se aplicará una técnica de exploración exhaustiva, dividiendo el problema en subproblemas y utilizando cotas para evitar la exploración innecesaria de ciertos caminos.
-
Algoritmos Probabilísticos: Se emplearán algoritmos basados en probabilidades para buscar soluciones aproximadas al problema.
Cada metodología algorítmica mencionada se implementará en C++.