Algoritmo para la minimización del recorrido de un turista por los sitios turísticos más importantes de Trujillo

UNIVERSIDAD NACIONAL DE TRUJILLO

Facultad de Ciencias Físicas y Matemáticas

Escuela Profesional de Informática[pic 1]

Algoritmo para la minimización del recorrido de un turista por los sitios turísticos más importantes de Trujillo

Trujillo - La Libertad

2022

Resumen

Para realizar este informe primero se identificó la problemática que existe en el turismo en la provincia de Trujillo, para lo cual mediante datos estadísticos pudimos diagnosticar una problemática que muchos de los turistas que llegan a Trujillo se ven con la problemática de no tener el tiempo necesario para visitar todos los lugares turísticos por la falta de desconocimiento de tener un recorrido armado. Para ello se desarrolló un algoritmo que les pueda dar la menor distancia para que ahorre tanto tiempo, así como para que puedan invertir más en turismo al poder visitar más puntos. Para ello el algoritmo requiere las distancias en entre las rutas ingresadas, también el punto desde el cual piensa iniciar, luego se calcula la ruta optima y también la distancia total (menor) que sería recorrida al seguirla. Como conclusión al ver los resultados y el tiempo de ejecución se pudo comprobar que a pesar de ser eficaz encontrando el menor recorrido, al ser un algoritmo de fuerza bruta no es eficiente especialmente para casos en los que se tiene muchos lugares turísticos, ya que el número de rutas estaría ligado a O(n!) lo cual nos da un número muy grande a medida que aumenta el n, es por ello que no se recomienda para una gran cantidad de datos. Como solución a la problemática si cumple ya que los turistas podrán tener una mejor ruta para aprovechar mejor su tiempo y dinero, aun así, se podría mejorar buscando una alternativa más eficiente.

Capítulo 1

Introducción

1. Realidad problemática

Durante el año 2018, según la Encuesta Trimestral de Turismo Interno, se estima que se realizaron alrededor de 2,7 millones de viajes por turismo interno con destino a la región La Libertad, lo que representa el 6,1% del total de viajes a nivel nacional, ocupando el puesto 6 del total de visitas por turismo interno. De aquellos viajes realizados el motivo principal de visita a la región La Libertad fue la visita de familiares y/o amigos (43,9%), seguido del motivo

de recreación (27,7%) y los negocios / motivos profesionales (17,5%). De estos datos podemos apreciar que muchos de los visitantes no vienen con el propósito de hacer turismo en la región la libertad y con ello su principal provincia de Trujillo, y si a esto le sumamos que a raíz de la pandemia el turismo a tenido unos descensos muy críticos por el confinamiento, entre otras causas.

1. Identificación del problema

El gran numero de visitas en Trujillo, no se da con el fin de conocer mas la ciudad y sus diferentes lugares turísticos, puesto que se da el caso de que muchos visitan la ciudad con el fin de visitar a sus familiares y/o amigos, y no cuentan con conocimiento sobre la distancia de los lugares turísticos a otros, y sin ese conocimiento no se podría realizar un cálculo aproximado del tiempo que les tomaría el poder realizar el recorrido turístico, y lo mismo ocurre con muchos turistas que visitan la ciudad por primera vez, y a veces por falta de conocimiento no terminan por disfrutar de todos los lugares recreativos y culturales que tiene por ofrecer la ciudad de Trujillo.

Capítulo 2

Problemas y metodología

1.  Planteamiento del problema

Ahora que el turismo se está normalizando, y muchas de las personas pueden comenzar hacer turismo interno, y con ello visitar la ciudad de Trujillo y sus múltiples lugares recreativos y culturas que tiene por ofrecer, por cual nos formulamos la siguiente incógnita: ¿Cuál sería la forma más optima de minimizar el recorrido turístico, y con ello poder aprovechar al máximo la estadía del turista en la ciudad de Trujillo?

1.  Método del trabajo

La problemática planteada se resolverá de la misma manera que el problema planteado y conocido como el “agente viajero”, en cual lo vamos a solucionar mediante el algoritmo de la fuerza bruta, para lo cual se van a intentar todas las permutaciones y ver cual de estas es la menor. El tiempo de ejecución es un factor polinómico de orden  la factorial del número es la cantidad lugares a recorrer.[pic 2]

Capítulo 3

Implementación y pruebas

1.  Algoritmo y su descripción

A continuación, presentamos la implantación del algoritmo representado mediante su seudocódigo, y con sus respectivos comentarios en las líneas de código mas resaltantes para poder comprender el proceso del funcionamiento del algoritmo desarrollado.

[pic 3]

[pic 4]

[pic 5]

[pic 6]

[pic 7][pic 8]

[pic 9]

[pic 10]

[pic 11]

[pic 12]

[pic 13]

1.  Explicación de la implementación y pruebas

La implementación del Algoritmo se realizó en el lenguaje de programación de alto nivel C++.

Los datos utilizados para las pruebas de diferentes escenarios fueron obtenidos en Google Maps, los cuales son las distancias entre diferentes lugares turísticos de Trujillo, siendo en total veinte lugares seleccionados, primero se realizará una prueba para buscar el recorrido menor en distancia para 5 lugares turísticos, luego para 10 y finalmente para 20.

Las principales funciones son:

int  RutaOptima              (void);

Función general que primero pide el nuevo de sitios turísticos en un intervalo validado de 5 ~ 20. Luego esta llama a las demás funciones para que realicen el trabajo de calcular la ruta optima.

void PedirCaminos            (Datos *);

Funcion que solicita al usuario ingresa todas las distancias en metros entre los nodos existentes, tomando en cuenta que la distancia de un nodo G[i] a G[j] es igual a la distancia de G[j] a G[i] y que las distancias de un nodo a si mismo es de cero.

void BuscarRutaOptima        (Datos *,int [20][2]);

Función que solicita el lugar turístico en el cual se desea iniciar el recorrido (el nodo a iniciar), con el cual luego calcula la ruta optima a partir de ese nodo, buscando las distancias mas cortas con otro nodo, orden que va guardando en una matriz de 2 columnas, la cual en la primera irán los números de nodos en orden optimo y en la segunda columna las distancias entre dichos nodos.

int  BuscarEnFila            (Datos *,int, int[20][2]);

Función que determina la menor valor (distancia) en una fila especifica de la matriz G[][]  y luego guarda dicha distancia y su índice de columna en la matriz r[][] llamando a otras 2 funciones más.

...