Tarea Progromada 2 - Computabilidad Y Complejidad

# Tarea Progromada 2 - Computabilidad Y Complejidad ## Integrantes: - Kevin Barboza - B80934 - Maeva Murcia - C05399 - Emmanuel Zúñiga - B98729 ## Resumen de la solución Se implementaron algoritmos de Fuerza Bruta, Heuristica y Meta-Heuristicas (Algoritmo Genético). Mediante dichas aproximaciones se busca obtener una solución al trazado de las rutas de menor complejidad para el Dron. Es importante destacar que un dron puede pasar n cantidad de veces por la misma casilla (esto para efectos de facilitar la implementación). Por lo cual, es posible que hayan demasiadas soluciones y los tiempos de ejecución se extiendan. ## Ejecución En primer lugar, dentro de la carpeta Maps se encuentran los siguientes archivos: ``` - map1.txt - map2.txt - map3.txt - map4.txt - map5.txt ``` Los cuales corresponden a mapas de ejemplo para la simulación del problema. Posteriormente desde la consola se debe de ingresar el siguiente script para la ejecución del programa: ``` $ python3 main.py map#.txt ``` Donde `map#.txt` corresponde a alguno de los mapas de ejemplo de la carpeta Maps. Al ejecutar el programa se debe de mostrar el siguiente menú: ``` Maps/map1.txt Drone Route Optimizer ᕙ( •̀ ᗜ •́ )ᕗ Menu: 1. Execute by Brute Force 2. Execute by Heuristic 3. Execute by Meta-Heuristic (Genetic Algorithm) 4. Credits 5. Exit Select an option: ``` En dicho menú se puede escoger cual de las aproximaciones utilizar para la resolución del problema. Para la solución del problema utilizando Fuerza Bruta, dado que es posible que generen muchas soluciones, se debe de escoger una cantidad máxima de soluciones a generar. A medida que incrementa la cantidad de soluciones, incrementa la probabilidad de encontrar un valor bajo de complejidad, no obstante, el tiempo de ejecución incrementa considerablemente. Por ejemplo: ``` Drone Route Optimizer ᕙ( •̀ ᗜ •́ )ᕗ Menu: 1. Execute by Brute Force 2. Execute by Heuristic 3. Execute by Meta-Heuristic (Genetic Algorithm) 4. Credits 5. Exit Select an option: 1 Solving by Brute Force... (ﾐዋ ﻌ ዋﾐ)ﾉ Enter the maximum number of solutions to create: 1000 Creating solutions please wait... Looking for better solution, please wait... ``` Posteriormente, se le mostrará al usuario la mejor solució encontrada, en conjunto a otras estadisticas. El caso de resolución por Meta-Heuristica (Algoritmo Genético) es algo particular. Para simplificar la resolución del problema y evitar tiempos de espera muy largos, es posible establecer un limite de generaciones y el "Fitness Score" mínimo esperado; con este último, a menor sea valor "mejor" será la solución. Por ejemplo: ``` Maps/map1.txt Drone Route Optimizer ᕙ( •̀ ᗜ •́ )ᕗ Menu: 1. Execute by Brute Force 2. Execute by Heuristic 3. Execute by Meta-Heuristic (Genetic Algorithm) 4. Credits 5. Exit Select an option: 3 Solving by Genetic Algorithm... (•؎ •) Enter the limit of Generations to simulate: 100 Enter the minimum fitness score of the solution: 6 ``` Posteriormente, se mostrará al usuario la información sobre la ruta óptima encontrada, estadisticas y un trazado de la ruta en el mapa seleccionado para la simulación.