¿Es el PROBLEMA DEL VIAJANTE el más difícil del mundo? 

Este tema me llamo tanto la atención durante la universidad que terminé haciendo mi tesis sobre el mismo. Desarrolle un modelo de distribución de productos sanguíneos entre hospitales utilizando drones, fue todo un desafío-

Me recuerda cuando programaba el diagrama de Dijkstra en Java 😀

Hice mi Trabajo Fin de Máster sobre Teoría de Grafos y éste era uno de los problemas más desafiantes que planteaba. Lo disfruté muchísimo!

Me quedo con esa última frase: "Si las matemáticas son poderosas, se dice y ya está". Gracias Eduardo.

Yo también hice mi proyecto final de carrera sobre este tema (TSP) en USA (Ingeniería electrónica). Servía para drones de combate en campo de batalla y para coordinación de robots en la superficie de Marte. Todo mediante algoritmos genéticos. Ideé una variante abierta que, efectivamente, reducía mucho la complejidad. Mi objetivo era conseguir un buen resultado subóptimo muy rápido. Me encantó el tema.

Tuve un profesor que decía que no nos desgastáramos tanto en problemas de optimización porque seguramente no íbamos a encontrar la solución nunca. Proponía usar heurísticas, las cuales funcionaban, era eficientes y se resolvían en corto tiempo. Las heurísticas seguirán siendo poderosas por mucho más tiempo!

Que explicación tan bonita y sencilla... Muchas gracias 🇨🇴🇨🇴☕☕🤗🤗

Muchas gracias Profesor Eduardo. Muy claro y didáctico.

Recuerdo haber tratado este problema que lo llamabamos "El cartero chino" en matemática discreta en la universidad... El algoritmo era sencillo pero encontrar la solución más óptima era tremendamente difícil

Fascinante como siempre. Saludos

Grande!!! Muy bueno! 🇦🇷

¡Muchas gracias por tu video profesor!

Excelente documental

Muy bien explicado! fantastico video

Justo entrego mi TFG sobre el problema del viajante en 9 días! Que casualidad.

Como siempre este señor dando esa sabia cátedra que no se olvidará. Muchas gracias.

Eduardo, como siempre gran contenido, por favor, no dejes de inspirar¡¡ Ampliar para quienes tengan interés, que el problema del viajante es un problema de optimización (puesto que busca la ruta más corta), no es un problema de decisión puesto que no podemos responder con SI o NO a esa pregunta lo que hace que los teóricos de la computación lo ubiquen en la clase de problema NP-Hard. Esto hace que ese problema sea más difícil que su padre (NP-Complete), el problema Hamiltonian Circuit (HC) que consiste, informalmente, en responder si existe o no un tour en un mapa, independientemente de su coste. Es decir, que TSP es más difícil que HC, incluso a pesar de que HC estuviera en P (y por lo tanto P=NP) es posible que TSP nunca estuviera en P ¿o si?. Después de 3 años de investigación inspirado inicialmente por los videos de nuestro amigo Eduardo, puedo decir que otro camino para abordar el diseño de algoritmos es el uso de estructuras de datos que basadas en abstracciones exponenciales (por ejemplo: buscar una estructura de datos que contenga en un espacio polinómico todas las posibles rutas optimas del problema TSP). Con este enfoque, tal y como explico en mi libro P vs NP - Abstracciones Exponenciales, se podría diseñar un algoritmo para HC - O(A^8) y para TSP - O(B * N^15) donde B es Km óptimos luego pseudopolinomico. Metodología que también he podido aplicar a 3SAT y al problema de las Mil Reinas. Obviamente, hay que ser muy prudentes y rigurosos con estos temas… y más si cabe con el escepticismo generalizado instalado en nuestra ciencia al respecto de P vs NP, así que bueno… si eres lo suficientemente valiente, temerario, de profundizar en el reto P vs NP y te animas a abrir tu mente a una metodología disruptiva entonces te gustará mi libro. (GooglePlay Books - E2Z0LJEMD78ND - Cupón gratis para los primeros valientes…) play.google.com/redeem?code=E2Z0LJEMD78ND

Bonito reporte de este tema

Tremendo! Muy tierna la miniatura por cierto!!!

fui a verte el otro dia en la UPV, en la etsid y me encantó 😁😁

Muy interesante!!

Muchas gracias por el video 👌

Si algún algoritmo tuviera la opción: "nena no te peines en la cama", los viajantes no se van a atrasar. Los Latinoamericanos entenderán la referencia. Saludos Eduardo, tus vídeos son espectaculares. Saludos desde Chile

Me quede en la. Tablas de multiplicar!! Muy bueno 🤝👏

Muchas gracias

Eduardo sigo tus videos, realmente excelentes!!! Necsitaríamos que nos explicaras con tu sabiduría la cinta de moebius...

And...muito bonitassssss

cuánto te amo Eduardo Sáenz de Cabezón

Sou brasileiro, parabéns pelo canal

Aunque uno puede buscar las fuentes, sería práctico si hubiese en la descripción enlace a los artículos mencionados, por ejemplo el de ruta entre estrellas. También me parece que falta mencionar algoritmos clásicos de búsqueda de ruta más corta como Dijkstra.

De chico jugaba al Ruta Nacionales, en el que tenías que pasar por distintas ciudades de Argentina (entre 10 y 15, dependiendo de la cantidad de jugadores). Y el desafío era justamente encontrar la ruta más corta u óptima. Después jugaba un poco la suerte de los dados y otros factores, pero lo esencial era encontrar la ruta más corta.

Excelente

Cuando vi Grafos en la universidad lo sentí como un tema tan fácil y llevadero que nunca imaginé que tuviese tanto factor complejo. Buen vídeo

Eres genial. Me acabo de suscribir

Justamente tengo en mi carrera (Ing Informática) una asignatura llamada Estructuras de Datos no Lineales en la que vemos grafos, aquí vemos esos problemas, muy guay !!!

Interesante como hay de aplicaciones para temas que son tan desconocidos para mi

En problemas de ruteo, para resolver el TSP la Open source routing machine usa contracciones jerárquicas.

Puedes hacer un vídeo de la transformada de Laplace, me parecen increíbles sus aplicaciones. Saludos

Belleza de video, los algoritmos inspirados en la naturaleza son geniales, todo me recuerda a los tiempos de tesis en la U

En un curso de logística me tocó ese mismo ejercicio con 10 poblaciones... sudé tinta.😢

feliz cumpleaños 🎂

Total, que el premio a los problemas del milenio se lo tienen que dar a... las Hormigas. jejeje. ¡Son unos bichitos geniales!

Excelente video las matemáticas son maravillosas

Te comento... pq está relacionado en tanto en cuanto encontrar alternativas de coste muchísimo menor.. para usos famosos. Gödel, en su demostración de incompletitud, usa potencias de números primos para transformar frases lógicas de primer orden (espero decirlo bien) en números naturales. Crea una biyección Lo importante es que para esa biyección, la función inversa (Dado el número natural, hallar la expresión lógica) tiene un coste elevadísimo. También me he fijado, que por ejemplo, los polinomios de Cantor se usan para otro tipo de biyecciones, etc... Yo, sin querer, pq me enteré de todo esto luego, diseñé no una fórmula general, pero si una técnica general para desarrollar dichas fórmulas, cuya aplicación es muy variada (MUY VARIADA, como por ejemplo los casos de los polinomios de Cantor, y las expresiones de Gödel, entre otras)... cuyo coste inverso y directo siempre es muy bajo comparado con la descomposición en números primos Básicamente, encontré una versión más general de los polinomios de Cantor, que encima es una alternativa excelente, en cuanto a coste computacional, para ciertas biyecciones famosas. Como mi acceso a la información es restringido, solo sé que Gödel no conocía mi sistema. O... que por no complicar la demostración, usó un sistema más simple para su biyección... pero sigo leyendo a matemáticos diferenciando casos, así que no creo que se hayan dado cuenta que tienen un patrón común El truco no es mejorar la descomposición en números primos.. PERO, el problema donde se usan, tiene alternativas, soluciones más optimas computacionalmente. Con una diferencia brutal. si te sirve de ejemplo, una vez probé un número natural creado a lo cachanchán de unas 300 000 cifras, en mi laptop con un i7 7XXX, ejecutando en mononucleo, y tardaba una horita o menos en dar la respuesta inversa.

Mu bié mu bié! 👏🏻👏🏻👏🏻👍🏻🖖🏼😉

4:45 Cuando hiciste la pregunta ¿funciona? ¿hay ejemplos útiles? pensé inmediatamente en un uso muy práctico para la solución del problema del viajante, ese uso sería encontrar la ruta más corta dentro del supermercado. Si lo piensan en el supermercado uno va a comprar diversas cosas y al estar buscando los productos uno a uno acabas caminando demasiado, sería bueno que se pudiese encontrar una ruta más corta para recorrerlo.

Buen video y muy útil em la vida diaria, como calcular los tubos de alimentación de las fábricas desalinizadoras, pues calcularon el tubo sumergido en el mar, océano o costa a 20 metros de profundidad, por lo que al aumentar el nivel del mar por el deshielo de los polos, entonces la profundidad aumentará y por tanto, peso y presión atmosférico del agua por la subida del nivel del mar, así entonces es habría que prever rutas, tuberías, caminos del agua a futuro previendo y para cada etapa de la subida del nivel del mar, evitando maniobras, costos por errores o reajustes, previendo también peso del agua carbonatada y más ácida para tuberías y muchas cosas que pensar sugerencia.

impresionante

que buena calidad de video tio

Guapísimo, siempre me ha interesado el estudio de los problemas no computables. Lo explica con tanta pasión y detalle que es simplemente hermoso.

Eso me sirve mucho. Necesito optimizar el uso de unos equipos y primero hicimos una optimización por modelación Montecarlo y ahora estamos intentando otra por modelos dinámicos utilizando el software SIMIO ¿Dónde puedo buscar más información?

La solucion a este problema es: Que al final el viajante se muere en su casa pensando la ruta y no viaja. 😂😂😂. Gran contenido Eduardo! Gracias😊

Si se conocen todas las distancias entre las dinstintas "ciudades", no se podria empezar por una aleatoriamente y luego vas escogiendo conectar con la que estas mas cerca, quando llevas dos, buscas qual de las dos tiene una tercera ciudad mas proxima, y así succesivamente

Me recuerda al descenso de gradiente. Con eso de la ia todo me va a eso

6:02 Eduardo, me llama mucho la atención la afición que existe por decir muchas veces "cero cero cero..." para indicar un número pequeño, o "nueve nueve nueve..." para indicar "casi siempre". ¿No sería mucho más pedagógico indicar el orden de magnitud de forma más comprensible? En el caso que nos ocupa: 1 parte entre 135mil, o 7 partes por millón.

Del creador de «tus amigos ligan más que tú» (ese fue el lema del vídeo anterior), llega… *«los ordenadores viajan más que tú».*

qué buen vídeo! me ha encantado una duda, cómo calculan lo máximo que pueden estar equivocados de la ruta óptima? me refiero por ejemplo al ejemplo final de las estrellas

Y si la naturaleza se comporta como la función z en el plano complejo?

Como el agente viajero se aplica a los circuitos eléctricos?

Hola Eduardo. Tengo 79 años. Me interesa sobremanera conocer el algoritmo Concorde ¿podría suministrarme datos de dónde puedo conseguir información del mismo?. Me explico: soy ingeniero industrial de la rama Organización. El proyecto fin de carrera, aconsejado por la cátedra de Investigación Operativa que elegí fue "El Problema del Viajante", en el que programaba en Basic las distintas posibilidades de abordar el problema: Programación lineal o dinámica, métodos "Branch & Bound", etc... Y el método exacto que se valoraba mejor (en aquellos tiempos) era el algoritmo de Shen Lin, en el que el problema de 50 ciudades USA con la IBM de la cátedra (no recuerdo la versión de la máquina) tardaba 20 minutos en obtener la solución. Como acabo de tener conocimiento de tu existencia y la labor que realizas de expandir el conocimiento matemático de una forma amena, no puedo por menos de dirigirme a tí. Muchas gracias de antemano.

Las curvas pronunciadas deben ser mínimas?

Para empezar gracias por tus vídeos, son un gran medio para aprender y disfrutar de las matemáticas. Dicho esto no sé que te parecerá este vídeo pero creo que la aportación del moho mucilaginoso podría aportar mucho en este problema: "ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-nPOQQp8CCls.html"

Como se sabe cuánto mide la óptima?

Hablamos más sobre los algoritmos genéticos por favor

Si empezamos desde una ciudad, y trazamos una línea recta hacia la ciudad más cercana por la que no hayamos pasado, y repetimos ese proceso hasta recorrer todas la ciudades ¿no sería una buena solución? aunque sea aproximada. Todavía no hice las matemáticas necesarias, pero pronto voy a hacerlas.

Eso lo hemos hecho todos con el mapa del metro. Y realmente es tremenda la cantidad de opciones disponibles. Si además hay que ir por estaciones accesibles (por ejemplo) o evitar zonas en obras, se complica aún más. Muy buen video.

Y los romanos, trataban las rutas más cortas así con menor pendiente para por ejemplo hacer túneles para pasar el agua acueductos para salvar las alturas o simplemente conectar las distintas villas romanas

👏👏👏👏👏

Hola! ¿La ruta entre estrellas, es un cálculo a modo de ejercicio teórico; o tiene una aplicación real? Gracias!

¿Como se obtuvo la ruta optima para comparar con la solución del algoritmo en el caso de las estrellas?

Te hago dos preguntas tardias para ver si haces un nuevo video: a) cuantas dimensiones geometricas tiene un libro considerando tambien su contenido? b) cuanto es realmente larga una frontera o una linea de costa?

Cómo pueden saber el error respecto de la óptima si la óptima no es calculable ?

Mmm, en un viaje de turismo intentas siempre ir a lo más proximo a continuacion y muchas veces el transporte tampoco va en linia recta.hay carreteras y direcciones prohibidas.

Aquí hay que separar la teoría de lo práctico, porque si fuera por ejemplo a pie tal vez no haya diferencia pero agrega el factor distancia real corta ,si vas en un vehículo, tienes que tomar en cuenta los sentidos de las calles y en ese punto aveces el punto más corto no es el ideal para trazar una ruta para optimizar el viaje

🎶🎶🎶🎶 Las matemáticas son poderosas, las matemáticas tienen poder 🎶🎶🎶🎶

Los algoritmos genéticos son impresionantes, se puede aplicar a cualquier problema

brutal

3:46 branch & bound para el que quiere investigar más

Pregunta, como saben los investigadores que cuando encuentran una solución aproximada se separa X de la optima, ¿Como saben cual es la optima?

Me encantan tus videos, (y eso que de estudiante odiaba las matemáticas 😂), no obstante en este problema falta una variable muy importante y es esta: si la persona que crea la ruta, (osea yo) es copiloto, además de la más corta, creara la ruta con el paisaje más bonito en la ventanilla derecha. Esto es siempre subjetivo, pero real como la vida misma. El verano pasado realicé una ruta de 11.600 km, teniendo muy encuenta que fuera la mas corta, y con el menor consumo de combustible y peajes, además de la más bonita. Me llevo mucho tiempo metida en Google maps, ademas de rutas Michelin. Seguro que aplicando formulas matemáticas habría sido mas eficiente, aunque dudo que más satisfactoria. Gracias por comunicar con tanta pasión las matemáticas 😘

y si tomamos un planteo inverso? es decir, con una cantidad de kilometros disponible quiero recorrer la mayor cantidad de ciudades, entonces el enfoque del problema cambbia pero el resultado es esencialmente el mismo, podria decir que en una nave espacial puedo acercarme de forma esferica a estrellas a 200 UA y de ahi digo bueno, tomare un recorrido que sea lo mas parecido a una linea recta en la suma de todos los pequeños recorridos que hago, es decir que la suma vectorial de los mismos tenga el menor angulo posible, quizas me estoy flipando pero me suena que es un metodo mas eficiente

me pregunto si se habrá considerado, en el asunto de trazar rutas entre estrellas... la posibilidad de utilizar el empuje gravitacional de esas estrellas del camino, para acelerar la velocidad... TAREA PARA LA CASA!

A ver en que año se resuelve el próximo problema del milenio

Lo importante no es encontrar la ruta mas corta sino la más rápida. Como hace un GPS. Porque es más importante la velocidad que la distancia a la hora de optimizar los recursos (gasolina, tiempo) tomando la solución mas eficiente. Edito: Además de que no en todas las opciones hay las mismas cuestas o tráfico.

Hola... se puede decir que Waze (app para ir de un punto a otro en un auto) resuelve este tipo de problemática de buena u optima forma?

Hay una estrategia que hacemos lo recordáis que utilizar vectores y matrices pero sería líneas rectas

Y yo que me quejo del servicio público de la ciudad. 🐒🐒🐒

Los japoneses descubrieron que los hongos pueden encontrar el camino más corto en el menor tiempo. Me encanta tu canal y ya tienes otro suscriptor

Entre los informáticos se suele decir que las matemáticas no son necesarias. La verdad es que la diferencia entre un O(1) y un O(n^2) en un algoritmo como calcular un número de la secuencia de Fibonacci esta en saber un poquito de matemáticas. Y ese es solo un ejemplo por el que los matemáticos son necesarios para refrescar la informática.

jajajajajajaaj me mata el "e = pi = 3 escrito en la pizarra"

Recuerdo que fue mi primer reto de la Universidad, diseñar un programa en C para resolver el problema. Unos semestres me lo volví a encontrar en uno de los temas introductorios de "Inteligencia Artificial"(veíamos lo clásico, nada que ver con el boom del año 2023). En esa ocasión decidí hacer un método de inundación optimizado. Se seleccionaba el origen y el destino en un mapa ya establecido con las rutas ponderadas, entonces se enviaban "viajeros virtuales" todos tenían de información el origen, el destino, el valor acumulado de ponderación y su ruta. Se generaba un viajero por cada comunicación que tuviese cada nodo. Ej. A -> B : A -> C : A -> D, etc. El ciclo de viaje, tenía una condición al momento de llegar a un nodo, pues este solo recibiría al de menor ponderación. de tal forma que siempre se quedaba con la ruta más corta entre ese nodo y el origen. Una vez se llegara al destino, este debería descartar todo viajero cuya ponderación superase el de este viajero que llegó. El único problema era la memoria y la administración de la lista de rutas activas, sugerí en su momento, usar una especie de tolerancia con respecto al viajero que tuviese más ciudades visitadas y menos valor acumulado, pero tuve que abandonarlo.

¿Que parte de las matemáticas es eso? ¿Quizás programación lineal? gracias

Y . cómo elige un líder una población n?

Las matemáticas son fascinantes.

Muy interesante, Edu! En los algortimos aproximados cómo sabes cuánto se separa la solución de la óptima si ésta no la conoces?

Breve!

Muy buen video. Estaría bien poner alguna referencia o el nombre de los proyectos de las rutas mencionados al final del video.

un número como 11111111(periódico: infinitos números 1) es mayor, menor o igual que un número 99999999 (con infinitos 9)?

Dudo que P sea igual a NP pero quiero leer acerca del algoritmo Concord, estoy trabajando en teoría de Grupos, quiero encontrar una Categoria desde la cual pueda producir todos los grupos simples, estoy pensando en la categoría de grafos, mas exactamente la categoría de categorias finitas. De allí construir un lenguaje para navegar por los grupos.

¿Por qué en el fondo a la izquierda aparece " e = π = 3"?