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-
@thurk-132 hace 1 segundo veamos, si la ficha inferior del dominó es la "A" doble, y la superior la "B" doble, siendo A y B valores enteros positivos o negativos indistintamente, ¿cuanto valdrá la suma de todos los puntos del dominó? Yo creé éste problema, y lo resolví sin boli ni papel en menos de 30 minutos, a ver si encuentras la fórmula
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.
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
@@warriorfc5261 No hay un camino marcado para algo así… esto depende de ti, de la motivación que tengas… de tus ganas de aprender a cómo si; y como no, afrontar ese u otro reto. No se… tal vez tendrías que encontrar tu propio camino... independientemente de este, sí que te recomendaría intentar disfrutar de cada idea que tengas, aunque luego acabe en un cajón, que no te importe aprender de los errores, pues sacar lecciones… te ayudará a crecer… como bien dijo Eduardo en su video del problema de las Mil Reinas: “…lo que vas aprenderás por el camino al intentarlo merece la pena…” y te puedo dar fe de ello. Y Si, prefieres una sugerencia, más concreta, porque no pruebas a intenta comenzar por responder tú mismo a esa pregunta: “¿Como abordaría yo (con los conocimientos que tengo…) este reto?”. Mucho ánimo :)
@@rudygonzalezlobo94 Mucho gusto, Rudy! :) Espero, al menos, que mi trabajo le permita ver un enfoque distinto (…más cercano a la Ingeniera Software) al habitual (Teoría de la Complejidad, Computación, Matemática…) y este, le motive a explorar nuevas ideas… y seguir así enriqueciendo nuestra pasión compartida. Un saludo, y mucho ánimo¡, Ricardo.
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
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.
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.
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.
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!
La verdad es que no terminé la carrera de ingeniería, donde llevaba optimizacion, pero aun sigo con la carrera de sociales y otra de humanidades, y después de pensar más flexivamente, también pienso que en muchos problemas lo mejor es utilizar métodos heurísticos, que métodos de optimizacion
@thurk-132 hace 1 segundo veamos, si la ficha inferior del dominó es la "A" doble, y la superior la "B" doble, siendo A y B valores enteros positivos o negativos indistintamente, ¿cuanto valdrá la suma de todos los puntos del dominó? Yo creé éste problema, y lo resolví sin boli ni papel en menos de 30 minutos, a ver si encuentras la fórmula
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.
Una pregunta. Si no se sabe cuál es la ruta óptima, cómo es posible calcular el factor de diferenciación entre el resultado del algoritmo y la óptima??
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.
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 !!!
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.
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.
Es interesante que el libro el arte de la guerra fuera derrotado por occidente qué no tenía libro del arte de la guerra occidental y 2 veces sometiera a China, me imagino que tendría muchas matemáticas y comportamiento social el de occidente a diferencia de oriente qué sólo le sirvió de manera local, por tanto una especie biológica inteligente y su galaxia qué fuera más occidentales qué occidente crearía un libro del arte de la guerra a nivel de galaxias y civilizaciónes tipo 4, 3, 2 y 1 para múltiples propósitos, ya me imagino los medio occidentales tengan el suyo antes o después de guerra contra otras galaxias y especies inteligentes biológicas, a diferencia de solo lo local, regional y de rancho en la tierra, sugerencia.
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
No lo has entendido, si para ir a la siguiente ciudad tienes que salir desde una ciudad por la que ya has pasado que es anterior a la última, tienes que retroceder sobre tus pasos y esa distancia deja de ser óptima. Tampoco escoger siempre la ciudad más cercana a la última te da el camino óptimo.
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
Hace 3 años empecé con una inversión de unos 15.000€ en criptomonedas, Forex y Bolsa, con la Sra. Kayla Tabitha Rodrigues gestionando mi cartera de inversiones, ahora tengo un valor de más de 500.000€. La inversión funciona si estás dispuesto a trabajar duro por ella.
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 😘
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
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
Técnicamente, este problema es informático por lo cual se usa la tecnología punta mas avanzada que existe imagina que el joven ba a la velocidad de la luz ya ahy debes reducir el tiempo aun llendo a la velocidad de la luz
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
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.
Responder por el Si o por el NO al problema P vs NP no es moco de pavo. Y aquí no admite margen de error ni dudas. Los expertos llevan años intentando demostrar y responder este problema. Tu dudas de que P = NP, pero yo más bien dudo que tu puedas decir tan laxamente que así sea. Mejor dejemos esas expresiones en manos de gente altamente calificada y no aventuremos nada... ni por el si ni por el no, ni un quizá, ni mares de dudas.
@@newemc2 gente menos altamente calificada,eso detesto de la academia,las matemáticas les pertenecen a todos,desde el mendigo mas humilde al hacker renegado con el mundo.Además tengo doctorado en matemáticas, hice mi tesis en geometría algebraica acerca de cuarticas regulares no lisas en característica tres.
@@CamiloDavidMoreiraDorado La matemática nos pertenece a todos pero respuestas correctas y verdaderas solo a un puñado. Me he cansado de leer tanta tonterías en internet porque es "gratis" para cualquier anónimo decir cualquier cosa sin fundamento ni evidencias debidamente estudiadas y analizadas y después hay muchos que en su ignorancia caen en las fake news y se comen todos los versos. Hubieras aclarado desde un comienzo que tienes un Ph en el tema desde un comienzo. Yo he estudiado Ing en Informática, y me atrae casi todo lo que sabe y huela a números. Y el tema de la complejidad de los algoritmos y el dilema P vs NP lo se bien, le reconozco que es un área nada fácil como seguramente sabes. Pero aún así por más que tenga conocimientos en el área, yo no me animo a decir algo al respecto. Trato de tener cuidado porque no se quien podrá leer estos comentarios, que pueden volverse en contra de uno.
@@newemc2 es cierto, ya recuerdo a uno que dice que demostró que los ceros no triviales de la función zeta de Riemann pertenecian a la recta critica y fue falso. Creo que el mismo Atiya hizo una demostración fraudulenta de la hipótesis de Riemann. Atiya era mi héroe, leí su libro de álgebra conmutativa e hice todos sus ejercicios, pero también hay fraudes con doctorado. Ya nadie tiene la autoridad para merecer las respuestas correctas, yo me desilusione de la academia con la guerra de ucrania, odie que le dieran la medalla fields a la matemática ucraniana Marina, no recuerdo el apellido, habían matemáticos rusos que merecían ese titulo y me pareció que la medalla fields se ha vuelto una premiacion política, como el nobel de la paz.
@@newemc2 El problema está mal planteado y por eso no se puede demostrar ni una cosa ni la contraria. Imagínate que me paso el tiempo necesario para resolver el problema con un algoritmo no óptimo y guardo en el disco todas las soluciones. Bueno, pues ahora existe un algoritmo que simplemente recoge del disco las soluciones previamente obtenidas. Con lo cual siempre va a existir un algoritmo que de la solución sin ningún coste computacional. Está claro que esto es hacer trampas, pero no hemos puesto en el planteamiento nada que restrinja esa posibilidad y por eso el problema está mal planteado.
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.
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
Lo mismo me pregunté, supongo que es algo cómo que la solución óptima es al menos tan grande como sumar las n distancias más pequeñas, y a partir de ahí vas acotando más y más la solución óptima
no porque waze busca distancia óptima entre dos puntos solamente, cuando usas paradas, calcula la ruta entre los subtramos.. el problema del viajero es encontrar la ruta óptima pasando por todas las ciudades sin un orden lógico como sería en el caso de waze
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?
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!
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: "th-cam.com/video/nPOQQp8CCls/w-d-xo.html"
Eduardo muy buenas de nuevo. No sé si lees todo lo que por aquí te comentan. Aún así tengo un " come come " en la cabeza que quería comentar.....por la posible respuesta que me podría dar por aquí...... Al grano , si la fuerza de la gravedad fuera 0 , teniendo en cuenta la presión que sufren los océanos por su propio peso , cuanto subiría el nivel del mar ?
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?
Disculpen, pero tomando el ejemplo que planteo de las ciudades y la ruta más óptima, no es esa la forma en la que funciona la electricidad? El flujo de electrones siempre encuentra el camino más óptimo, el que es más rápido a "tierra"
para el problema de las más de mil millones de estrellas la desviación respecto de la ruta óptima es de 0,0000X... cómo se sabe cuál es la ruta óptima??
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.
Mi pregunta es: ¿Cómo es que se puede verificar que una solución del problema del viajante sea la mejor en tiempo polinomial? No se me ocurre una mejor manera de comprobarla que compararla con el resto de soluciones. Pero eso no se puede hacer en tiempo polinomial. Si la solución no se puede verificar que sea correcta en tiempo polinomial entonces ni siquiera es NP.
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.
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-
@@pabloivanbustamanteidro3898 Sii, el centro metropolitano de sangre y tejidos me facilitó la información para alimentar el modelo
Si no es mucha indiscreción ¿Qué estudió usted?
@@frangarcia7190 estudie ingeniería civil industrial
Esta tu tesis subida en algún sitio? Sería interesantisimo leerla
@@eloycr14 Puedes buscarla en el repositorio de mi universidad (UTFSM) con mis dos apellidos
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!
@thurk-132
hace 1 segundo
veamos, si la ficha inferior del dominó es la "A" doble, y la superior la "B" doble, siendo A y B valores enteros positivos o negativos indistintamente, ¿cuanto valdrá la suma de todos los puntos del dominó? Yo creé éste problema, y lo resolví sin boli ni papel en menos de 30 minutos, a ver si encuentras la fórmula
Una duda, cuál sería el problema al intentar resolverlo con aplicaciones básicas de grafos?
Con dijkstra o algo del estilo
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.
Me quedo con esa última frase: "Si las matemáticas son poderosas, se dice y ya está". Gracias Eduardo.
una forma optimista de ver la vida
Se tenía que decir y se dijo
Como siempre este señor dando esa sabia cátedra que no se olvidará. Muchas gracias.
Que explicación tan bonita y sencilla... 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
Por dónde me recomendarías empezar para adentrarme al problema p=np?
Soy un ingeniero de Microsoft apasionado por este tipo de problemas y en general, ciencias de la computación. Muchas gracias por compartir el libro
@@warriorfc5261 No hay un camino marcado para algo así… esto depende de ti, de la motivación que tengas… de tus ganas de aprender a cómo si; y como no, afrontar ese u otro reto. No se… tal vez tendrías que encontrar tu propio camino... independientemente de este, sí que te recomendaría intentar disfrutar de cada idea que tengas, aunque luego acabe en un cajón, que no te importe aprender de los errores, pues sacar lecciones… te ayudará a crecer… como bien dijo Eduardo en su video del problema de las Mil Reinas: “…lo que vas aprenderás por el camino al intentarlo merece la pena…” y te puedo dar fe de ello. Y Si, prefieres una sugerencia, más concreta, porque no pruebas a intenta comenzar por responder tú mismo a esa pregunta: “¿Como abordaría yo (con los conocimientos que tengo…) este reto?”. Mucho ánimo :)
@@rudygonzalezlobo94 Mucho gusto, Rudy! :) Espero, al menos, que mi trabajo le permita ver un enfoque distinto (…más cercano a la Ingeniera Software) al habitual (Teoría de la Complejidad, Computación, Matemática…) y este, le motive a explorar nuevas ideas… y seguir así enriqueciendo nuestra pasión compartida. Un saludo, y mucho ánimo¡, Ricardo.
@@nanodijkstra muchas gracias por la respuesta
Me recuerda cuando programaba el diagrama de Dijkstra en Java 😀
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
fui a verte el otro dia en la UPV, en la etsid y me encantó 😁😁
cuánto te amo Eduardo Sáenz de Cabezón
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.
Tienes toda la razón
¡Muchas gracias por tu video profesor!
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.
Fascinante como siempre. Saludos
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
Igual es más agradable que cálculo
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.
Grande!!! Muy bueno! 🇦🇷
Me quede en la. Tablas de multiplicar!!
Muy bueno 🤝👏
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!
La verdad es que no terminé la carrera de ingeniería, donde llevaba optimizacion, pero aun sigo con la carrera de sociales y otra de humanidades, y después de pensar más flexivamente, también pienso que en muchos problemas lo mejor es utilizar métodos heurísticos, que métodos de optimizacion
@thurk-132
hace 1 segundo
veamos, si la ficha inferior del dominó es la "A" doble, y la superior la "B" doble, siendo A y B valores enteros positivos o negativos indistintamente, ¿cuanto valdrá la suma de todos los puntos del dominó? Yo creé éste problema, y lo resolví sin boli ni papel en menos de 30 minutos, a ver si encuentras la fórmula
Metaheuristicas no es lo mismo que heuristicas y para mi las metaheuristicas son la mejor opción
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.
Una pregunta. Si no se sabe cuál es la ruta óptima, cómo es posible calcular el factor de diferenciación entre el resultado del algoritmo y la óptima??
Justo entrego mi TFG sobre el problema del viajante en 9 días! Que casualidad.
Eduardo sigo tus videos, realmente excelentes!!! Necsitaríamos que nos explicaras con tu sabiduría la cinta de moebius...
Belleza de video, los algoritmos inspirados en la naturaleza son geniales, todo me recuerda a los tiempos de tesis en la U
Total, que el premio a los problemas del milenio se lo tienen que dar a... las Hormigas. jejeje. ¡Son unos bichitos geniales!
Sou brasileiro, parabéns pelo canal
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.
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.
Tremendo! Muy tierna la miniatura por cierto!!!
Excelente documental
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😊
Bonito reporte de este tema
Muchas gracias
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 !!!
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.
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.
Es interesante que el libro el arte de la guerra fuera derrotado por occidente qué no tenía libro del arte de la guerra occidental y 2 veces sometiera a China, me imagino que tendría muchas matemáticas y comportamiento social el de occidente a diferencia de oriente qué sólo le sirvió de manera local, por tanto una especie biológica inteligente y su galaxia qué fuera más occidentales qué occidente crearía un libro del arte de la guerra a nivel de galaxias y civilizaciónes tipo 4, 3, 2 y 1 para múltiples propósitos, ya me imagino los medio occidentales tengan el suyo antes o después de guerra contra otras galaxias y especies inteligentes biológicas, a diferencia de solo lo local, regional y de rancho en la tierra, sugerencia.
Muy bien explicado! fantastico video
Puedes hacer un vídeo de la transformada de Laplace, me parecen increíbles sus aplicaciones. Saludos
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
No lo has entendido, si para ir a la siguiente ciudad tienes que salir desde una ciudad por la que ya has pasado que es anterior a la última, tienes que retroceder sobre tus pasos y esa distancia deja de ser óptima. Tampoco escoger siempre la ciudad más cercana a la última te da el camino óptimo.
And...muito bonitassssss
Interesante como hay de aplicaciones para temas que son tan desconocidos para mi
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
Soy de Chile y no entendi tu referencia 😆
Soy de Colombia y no entendí a qué hace referencia esa frase. Conclusión: Nunca se debe generalizar.
En problemas de ruteo, para resolver el TSP la Open source routing machine usa contracciones jerárquicas.
En un curso de logística me tocó ese mismo ejercicio con 10 poblaciones... sudé tinta.😢
Muchas gracias por el video 👌
Y si la naturaleza se comporta como la función z en el plano complejo?
Muy interesante!!
Hace 3 años empecé con una inversión de unos 15.000€ en criptomonedas, Forex y Bolsa, con la Sra. Kayla Tabitha Rodrigues gestionando mi cartera de inversiones, ahora tengo un valor de más de 500.000€. La inversión funciona si estás dispuesto a trabajar duro por ella.
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 😘
Excelente
Mu bié mu bié! 👏🏻👏🏻👏🏻👍🏻🖖🏼😉
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.
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
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!
Supongo que si un algoritmo calcula muy bien el resultado para millones de estrellas, también lo hará bien cuando se trate de un problema real
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.
Pregunta, como saben los investigadores que cuando encuentran una solución aproximada se separa X de la optima, ¿Como saben cual es la optima?
Excelente video las matemáticas son maravillosas
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
Técnicamente, este problema es informático por lo cual se usa la tecnología punta mas avanzada que existe imagina que el joven ba a la velocidad de la luz ya ahy debes reducir el tiempo aun llendo a la velocidad de la luz
feliz cumpleaños 🎂
Como el agente viajero se aplica a los circuitos eléctricos?
Cómo pueden saber el error respecto de la óptima si la óptima no es calculable ?
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
Las curvas pronunciadas deben ser mínimas?
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.
Responder por el Si o por el NO al problema P vs NP no es moco de pavo. Y aquí no admite margen de error ni dudas. Los expertos llevan años intentando demostrar y responder este problema. Tu dudas de que P = NP, pero yo más bien dudo que tu puedas decir tan laxamente que así sea. Mejor dejemos esas expresiones en manos de gente altamente calificada y no aventuremos nada... ni por el si ni por el no, ni un quizá, ni mares de dudas.
@@newemc2 gente menos altamente calificada,eso detesto de la academia,las matemáticas les pertenecen a todos,desde el mendigo mas humilde al hacker renegado con el mundo.Además tengo doctorado en matemáticas, hice mi tesis en geometría algebraica acerca de cuarticas regulares no lisas en característica tres.
@@CamiloDavidMoreiraDorado La matemática nos pertenece a todos pero respuestas correctas y verdaderas solo a un puñado. Me he cansado de leer tanta tonterías en internet porque es "gratis" para cualquier anónimo decir cualquier cosa sin fundamento ni evidencias debidamente estudiadas y analizadas y después hay muchos que en su ignorancia caen en las fake news y se comen todos los versos. Hubieras aclarado desde un comienzo que tienes un Ph en el tema desde un comienzo. Yo he estudiado Ing en Informática, y me atrae casi todo lo que sabe y huela a números. Y el tema de la complejidad de los algoritmos y el dilema P vs NP lo se bien, le reconozco que es un área nada fácil como seguramente sabes. Pero aún así por más que tenga conocimientos en el área, yo no me animo a decir algo al respecto. Trato de tener cuidado porque no se quien podrá leer estos comentarios, que pueden volverse en contra de uno.
@@newemc2 es cierto, ya recuerdo a uno que dice que demostró que los ceros no triviales de la función zeta de Riemann pertenecian a la recta critica y fue falso. Creo que el mismo Atiya hizo una demostración fraudulenta de la hipótesis de Riemann. Atiya era mi héroe, leí su libro de álgebra conmutativa e hice todos sus ejercicios, pero también hay fraudes con doctorado. Ya nadie tiene la autoridad para merecer las respuestas correctas, yo me desilusione de la academia con la guerra de ucrania, odie que le dieran la medalla fields a la matemática ucraniana Marina, no recuerdo el apellido, habían matemáticos rusos que merecían ese titulo y me pareció que la medalla fields se ha vuelto una premiacion política, como el nobel de la paz.
@@newemc2 El problema está mal planteado y por eso no se puede demostrar ni una cosa ni la contraria. Imagínate que me paso el tiempo necesario para resolver el problema con un algoritmo no óptimo y guardo en el disco todas las soluciones. Bueno, pues ahora existe un algoritmo que simplemente recoge del disco las soluciones previamente obtenidas. Con lo cual siempre va a existir un algoritmo que de la solución sin ningún coste computacional. Está claro que esto es hacer trampas, pero no hemos puesto en el planteamiento nada que restrinja esa posibilidad y por eso el problema está mal planteado.
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.
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
Lo mismo me pregunté, supongo que es algo cómo que la solución óptima es al menos tan grande como sumar las n distancias más pequeñas, y a partir de ahí vas acotando más y más la solución óptima
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?
no porque waze busca distancia óptima entre dos puntos solamente, cuando usas paradas, calcula la ruta entre los subtramos.. el problema del viajero es encontrar la ruta óptima pasando por todas las ciudades sin un orden lógico como sería en el caso de waze
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?
Los algoritmos deberían ser eternos🤯
Resuelven problemas difíciles de abordar por la mente humana y facilitan la vida de una manera increíble🧐👀
Como se sabe cuánto mide la óptima?
Eres genial.
Me acabo de suscribir
🎶🎶🎶🎶 Las matemáticas son poderosas, las matemáticas tienen poder 🎶🎶🎶🎶
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?
¿Será algún cálculo probabilístico?
No lo sabes a ciencia cierta. Vas probando diferentes algoritmos con diferentes combinaciones y ves cuál te da un mejor valor.
Se estima una cota, no se sabe la exacta, por eso dice que se separa de la solución en un factor de X
Pero la cota es estimada, no? Es decir, que se cree que la separación es X pero podría ser 1000x?
impresionante
3:46 branch & bound para el que quiere investigar más
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!
¿Que parte de las matemáticas es eso? ¿Quizás programación lineal? gracias
Teoría de grafos, supongo
¿Por qué en el fondo a la izquierda aparece " e = π = 3"?
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: "th-cam.com/video/nPOQQp8CCls/w-d-xo.html"
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ú».*
Eduardo muy buenas de nuevo.
No sé si lees todo lo que por aquí te comentan.
Aún así tengo un " come come " en la cabeza que quería comentar.....por la posible respuesta que me podría dar por aquí......
Al grano , si la fuerza de la gravedad fuera 0 , teniendo en cuenta la presión que sufren los océanos por su propio peso , cuanto subiría el nivel del mar ?
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?
Hablamos más sobre los algoritmos genéticos por favor
Disculpen, pero tomando el ejemplo que planteo de las ciudades y la ruta más óptima, no es esa la forma en la que funciona la electricidad? El flujo de electrones siempre encuentra el camino más óptimo, el que es más rápido a "tierra"
Pero no necesariamente el más corto, sino el que ofrece menor resistencia.
@@manboto Gracias por la aclaratoria
¿Como se obtuvo la ruta optima para comparar con la solución del algoritmo en el caso de las estrellas?
No entiendo por qué este problema está en NP. Si tengo una solución, ¿cómo puedo entender rápidamente que es correcta?
Muy buen video. Estaría bien poner alguna referencia o el nombre de los proyectos de las rutas mencionados al final del video.
para el problema de las más de mil millones de estrellas la desviación respecto de la ruta óptima es de 0,0000X... cómo se sabe cuál es la ruta óptima??
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.
Mi pregunta es:
¿Cómo es que se puede verificar que una solución del problema del viajante sea la mejor en tiempo polinomial?
No se me ocurre una mejor manera de comprobarla que compararla con el resto de soluciones. Pero eso no se puede hacer en tiempo polinomial.
Si la solución no se puede verificar que sea correcta en tiempo polinomial entonces ni siquiera es NP.
Y yo que me quejo del servicio público de la ciudad. 🐒🐒🐒
que buena calidad de video tio
Me recuerda al descenso de gradiente. Con eso de la ia todo me va a eso
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.
Es increíble la capacidad analítica del ser humano, sí todos pudiéramos usarla en su máxima capacidad...
👏👏👏👏👏
Hay una estrategia que hacemos lo recordáis que utilizar vectores y matrices pero sería líneas rectas