Problema Agente Viajero PDF

Preview

Summary

INFORMECURSO DE MATEMÁTICA COMPUTACIONAL – SISección: CCTema: Problema Agente ViajeroIntegrantes:-Adrian Benavente Febres u-Alexander Talledo Carranza u-Sebastian Poma Del Campo u20201a-Dyland Saldaña Del Rosario u-Nilton Torres Rojas uMarzo 2021ÍNDICEI. IntroducciónII. Fundamento Teórico2. Algoritm...

Description

INFORME

CURSO DE MATEMÁTICA COMPUTACIONAL – SI400 Sección: CC42

Tema: Problema Agente Viajero

Integrantes: -Adrian Benavente Febres u202010157 -Alexander Talledo Carranza u201712187 -Sebastian Poma Del Campo u20201a085 -Dyland Saldaña Del Rosario u201920461 -Nilton Torres Rojas u201924058

Marzo 2021

ÍNDICE I.

Introducción

II.

Fundamento Teórico 2.1. Algoritmo base

III.

Ejemplos

IV.

Fuentes

Introducción: El problema del agente viajero(TSP) es un problema que pertenece a la matemática computacional, se usa mayormente en las aplicaciones para optimizar sus recursos. Entre los diferentes campos donde se ha utilizado es el de determinar y diseñar rutas para los vehículos en las aplicaciones como Google Maps. Consiste en buscar el camino más corto posible para ir de un lugar a otro por todas las ciudades y regresar a la misma del inicio. Además que los costos de viajar de la ciudad de A hacia la ciudad B deben de ser el mismo valor de viajar a la ciudad B hacia la ciudad A. Para el desarrollo del problema debemos tener en cuenta los nodos que son los puntos de intersección, las distancias entre cada uno de ellos y el objetivo. En este documento aclararemos información respecto al problema viajero, además que como parte del trabajo desarrollaremos el algoritmo de solución y crearemos el programa donde se podrá ver gráficamente cómo funciona el desarrollo del problema El propósito de este informe es programar el desarrollo del problema agente viajero.. El TSP se puede realizar en cualquier situación que necesite seleccionar nodos en cierto orden para reducir los costos, algunos ejemplos que utilizan el algoritmo son: 1. Control de Semáforos. Ubicar el número de semáforos (nodos), distancia entre cada semáforo, tiempo que se necesita en promedio para llegar hacia otro semáforo , entre otras variables. 2. Reparto de productos. Mejorar una ruta de entrega para seguir la más corta 3. Aplicaciones de navegación. Intentan encontrar el camino más óptimo para llevarte a tu destino 4. Robótica.- Resolver problemas de fabricación para minimizar el número de desplazamientos al llevar a cabo una serie de perforaciones en un circuito impreso.

Fundamento teórico: Este problema está basado en la teoría de grafos, según esta teoría los vértices, en este caso las ciudades, están unidos por un camino. Los tipos de grafos son: Dirigidos: en este tipo de grafo las aristas tienen un sentido definido. No dirigidos: en este tipo de grafo los vértices no tienen sentido definido es decir con las aristas bidireccionales.

La primera solución para resolver el problema del Agente viajero se realizó en 1954, cuando George Dantzig, Ray Fulkerson y Selmer Johnson publicaron la descripción de un método de solución del PAV(problema del Agente Viajero o sus siglas en inglés TSP- Travel Salesman Problem) con el título de ‘’Solutions of a large scale travelling salesman problem’’, soluciones de gran escala para el problema del agente viajero) para la resolución de una instancia de 49 ciudades donde un agente viajero aspira a visitar una gran cantidad de ciudades, asignándoles un importe para visitar ciudades contiguas( distancia de traslado entre dos ciudades). Para esta solución se proponen 2 condiciones: retornar a la misma ciudad de la cual partió y no repetir poblaciones con el objetivo de encontrar un camino con el menor importe posible.

Algoritmo base: -Definir el número de nodos, su posición y el costo por cada arista(i,j) donde i=ciudad 1 y -j=ciudad 2 -Elegir el nodo inicial i -Hacer -Si el nodo más cercano no se ha visitado -Visitar nodo j -Actualizar lista de nodos visitados -Costo_total = costo_total + costoij -Nodo i = nodo j -Hasta haber visitado todos los nodos

Una de las formas más directas de resolver el problema sería realizar permutaciones este siendo hecho en base del número de soluciones posibles pero este proceso se vuelve inutil mientras el número de soluciones sea mayor. Otro proceso es la técnica Branch and Bound (Ramificación y Acotamiento o Poda), está siendo una técnica para detectar en que ramificación la ruta ya no es óptima para “podar” este camino.

Donde: • G(x) es la función de estimación del algoritmo. • P es el vector permutación.

Ejemplos

imagen 1. Un ciudadano quiere realizar un viaje en un bus de Cruz del Sur, pero solo tienen estas rutas desde Lima hasta Madre De Dios para poder ver a su familia en Semana Santa. Después de una semana regresar a su hogar qué camino será el más corto para él.

Deberá ir de Lima a Ica luego a Ayacucho después a Apurímac después a Cuzco y así llegar a Madre de Dios Lima+Ica+Ayacucho+Apurímac+Cusco+Madre de Dios 310+312+ 157 + 134 +233=1146km Nodos

Lima

Ica

Ayacucho

Apurimac

Cusco

Madre de Dios

Lima

0

1

0

0

0

0

Ica

0

0

1

0

0

0

Ayacucho

0

0

0

1

0

0

Apurimac

0

0

0

0

1

0

Cusco

0

0

0

0

0

1

Madre de Dios

0

0

0

0

0

0

2) Un turista ruso quiere viajar en camioneta desde la ciudad de Lima a Piura, se necesita la trayectoria más corta. Primero debe dirigirse a la ciudad de Ancash, luego deberá ir hacia La Libertad, después tendrá que ir hacia Lambayeque y por último llegará a Piura.(Visualizar imagen 1) Matriz de adyacencia

Nodos

Lima

Ancash

La Libertad

Lambayeque

Piura

Lima

0

1

0

0

0

Ancash

0

0

1

0

0

La Libertad

0

0

0

1

0

Lambayeque

0

0

0

0

1

Piura

0

0

0

0

0

Distancia Total: 420+295+385+194=1294 Km En conclusión el camino mas optimo para el turista es de 1294 Km partiendo de Lima hacia Piura.

3)Un ciudadano de nacionalidad china reside en el departamento de Arequipa pero decide realizar un viaje hasta Madre de Dios pero debe pasar obligatoriamente por Apurímac.Se desea obtener el camino más corto.(Visualizar la imagen 1) Arequipa->A Punto de inicio Apurímac-> B Cusco->C Puno->D Madre de Dios->E Punto final

Matriz de adyacencia

Nodos

A

B

C

D

E

A

0

1

0

0

0

B

0

0

1

0

0

C

0

0

0

0

1

D

1

0

0

0

0

E

0

0

0

1

0

Suma para encontrar la menor distancia en KM = (311+134+233+461+310)km = 1449km En conclusión para que el ciudadano chino tenga que realizar un recorrido de ida y vuelta tendría que pasar primero por Apurímac luego Cusco,Madre de dios, Puno y luego regresar a Arequipa y la menor distancia obtenida es 1449 km.

Un turista norteamericano, desea iniciar el recorrido por Loreto, San Martín, Ucayali ,Madre de Dios y finalmente por Puno.Después de realizar su viaje desea regresar a Loreto para pasar unos días . Matriz adyacente Nodo

Loreto

San Martín

Huánuco

Pasco

Junin

Loreto

0

1

0

0

0

San Martín

0

0

1

0

0

Huánuco

0

0

0

1

0

Pasco

0

0

0

0

1

Junín

0

0

0

0

0

Distancia Total: 345 + 305 +132 +101 = 792 Km. En conclusión para que el turista pueda visitar todas las ciudades que se planteó debe recorrer un total de 792 Km.

Resultados: los resultados de nuestro código resuelve la incógnita del problema del agente viajero,

calculando entre todas las distintas formas de ejecutar nuestro viaje a través de todos los distintos departamentos que visitaremos. Y mostrándonos la mejor forma de viajar por todos los departamentos, y que esta termina siendo la más corta.

Conclusiones: ●

●

● ●

●

Nuestro proyecto nos ha dejado apreciar, que este problema no solo representa el camino más corto visitando todos los lugares, sino también todos los distintos posibles viajes que podemos hacer a través de todos los lugares. Hacer un proyecto sobre este problema no es nada sencillo, se tiene varias ideas sobre cómo crear un programa sobre este problema, y requiere mucha prueba y error para hallar el buen camino. Este proyecto requiere búsqueda para las distintas alternativas en la que se puede hace este mismo problema y encontrar la mas sencilla para poder trabajarla. El proyecto se nos dificulto al momento de implementar un algoritmo específico para hallar el camino más corto, pero con la investigación del grupo logramos hallar la solución. El resultado final de nuestro proyecto logra hallar el camino mas corto mediante el programa desarrollado

●

Palabras claves -Nodo o vértice:Punto es referido en este ejercicio a las ciudades que está conectado con las demás -Árbol no dirigido: Es la cerradura simétrica de un árbol. Las líneas de la gráfica de un árbol no dirigido X corresponde a las aristas no dirigidas de X. -Optimización: Capacidad de realizar o resolver alguna tarea de la manera más eficiente posible o en la mayoría de casos, haciendo uso de la menor cantidad de recursos. -Inteligencia Artificial (IA): Serie de tecnologías que nos sirven para emular descripciones o capacidades exclusivas del intelecto humano -Algoritmo:Serie de pasos y operaciones sistemáticas que permite realizar un cálculo y resolver uno o varios problemas

Fuentes: REAL ACADEMIA ESPAÑOLA: Diccionario de la lengua española, 23.ª ed., [versión 23.4 en línea]. [Consulta 3 de abril del 2021]. Gestión.(2018). ¿Qué es la inteligencia artificial y para qué sirve?. Gestión. Recuperado el 1 de abril de 2021, de https://gestion.pe/tecnologia/inteligencia-artificial-historia-origenfunciona-aplicaciones-categorias-tipos-riesgos-nnda-nnlt-249002-noticia/ Alfaro, Rubí.(2014). Problema del agente viajero. Slideshare. Recuperado el 29 de marzo de

2021, de https://es.slideshare.net/rubialfaromostacero/problema-del-agente-viajeromonografia Fuentes, A. (2021). Problema del agente viajero. Recuperado el 1 abril 2021, de https://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html

Mendoza, J. (2017). TRAVELING SALESMAN PROBLEM (TSP) Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para resolver el Problema del Agente Viajero. Recuperado el 2 Abril 2021, de https://repositorio.unan.edu.ni/8779/1/11129.pdf (2017). Problema del agente viajero. Ingeciencia, 1(2), 57-65. Consultado de http://editorial.ucentral.edu.co/ojs_uc/index.php/Ingeciencia/article/view/310 [Consulta 3 de abril del 2021]...