¿Es el PROBLEMA DEL VIAJANTE el más difícil del mundo?
ฝัง
- เผยแพร่เมื่อ 24 ส.ค. 2024
- El problema del viajante trata de encontrar el camino más corto que recorra un conjunto de ciudades. Se ha dicho de él que es el problema computacional más difícil del mundo. ¿Es eso cierto?
PROBLEMA P-NP
• ¿Qué es eso del proble...
¡Suscríbete al canal!
Sigue a Eduardo Sáenz de Cabezón:
En Twitter:
/ edusadeci
En Instagram:
/ eduardosdc
En Facebook:
DerivandoTH-cam
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
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
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 recuerda cuando programaba el diagrama de Dijkstra en Java 😀
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
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
Como siempre este señor dando esa sabia cátedra que no se olvidará. Muchas gracias.
Justo entrego mi TFG sobre el problema del viajante en 9 días! Que casualidad.
Que explicación tan bonita y sencilla... Muchas gracias 🇨🇴🇨🇴☕☕🤗🤗
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.
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
Sou brasileiro, parabéns pelo canal
fui a verte el otro dia en la UPV, en la etsid y me encantó 😁😁
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
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.
Fascinante como siempre. Saludos
Total, que el premio a los problemas del milenio se lo tienen que dar a... las Hormigas. jejeje. ¡Son unos bichitos geniales!
Muchas gracias Profesor Eduardo. Muy claro y didáctico.
¡Muchas gracias por tu video profesor!
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
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.
And...muito bonitassssss
cuánto te amo Eduardo Sáenz de Cabezón
En un curso de logística me tocó ese mismo ejercicio con 10 poblaciones... sudé tinta.😢
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😊
Me quede en la. Tablas de multiplicar!!
Muy bueno 🤝👏
Interesante como hay de aplicaciones para temas que son tan desconocidos para mi
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.
En problemas de ruteo, para resolver el TSP la Open source routing machine usa contracciones jerárquicas.
Vamos a suponer que sean pueblos indígenas y hay que buscar la ruta más corta entre dos pueblos. El problema del viajante sería perderse.
Grande!!! Muy bueno! 🇦🇷
Belleza de video, los algoritmos inspirados en la naturaleza son geniales, todo me recuerda a los tiempos de tesis en la U
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.
Puedes hacer un vídeo de la transformada de Laplace, me parecen increíbles sus aplicaciones. Saludos
Bonito reporte de este tema
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 !!!
Excelente documental
🎶🎶🎶🎶 Las matemáticas son poderosas, las matemáticas tienen poder 🎶🎶🎶🎶
3:46 branch & bound para el que quiere investigar más
feliz cumpleaños 🎂
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.
Muchas gracias
Mu bié mu bié! 👏🏻👏🏻👏🏻👍🏻🖖🏼😉
Eduardo sigo tus videos, realmente excelentes!!! Necsitaríamos que nos explicaras con tu sabiduría la cinta de moebius...
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
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.
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.
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.
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.
Y yo que me quejo del servicio público de la ciudad. 🐒🐒🐒
Muy bien explicado! fantastico video
Pregunta, como saben los investigadores que cuando encuentran una solución aproximada se separa X de la optima, ¿Como saben cual es la optima?
Tremendo! Muy tierna la miniatura por cierto!!!
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
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?
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
Hablamos más sobre los algoritmos genéticos por favor
Y si la naturaleza se comporta como la función z en el plano complejo?
Hay una estrategia que hacemos lo recordáis que utilizar vectores y matrices pero sería líneas rectas
Muy interesante!!
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🧐👀
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.
Intentarlo fue parte del aprendizaje
Los algoritmos genéticos son impresionantes, se puede aplicar a cualquier problema
Todavía no hemos llegado a Marte y los matemáticos promocionando el turismo estelar. Asombroso. Ja, ja.
Me interesaría saber cuánto tarda la luz en hacer la ruta completa.
Eres genial.
Me acabo de suscribir
Excelente
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"
Muchas gracias por el video 👌
Cómo pueden saber el error respecto de la óptima si la óptima no es calculable ?
Como el agente viajero se aplica a los circuitos eléctricos?
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!
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
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.
Me recuerda al descenso de gradiente. Con eso de la ia todo me va a eso
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 video las matemáticas son maravillosas
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.
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.
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ú».*
Es increíble la capacidad analítica del ser humano, sí todos pudiéramos usarla en su máxima capacidad...
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.
No entiendo por qué este problema está en NP. Si tengo una solución, ¿cómo puedo entender rápidamente que es correcta?
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.
NP COMPLETITUUUUUUUUD!!!!!
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
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 ?
Es el problema rodar un programa para calcular la mejor disposición de muchos objetos, número astronómico de combinaciones en lo que se llama leiaute de proceso
Lo mejor es usar un supercomputador
A ver en que año se resuelve el próximo problema del milenio
Breve!
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?
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?
jajajajajajaaj me mata el "e = pi = 3 escrito en la pizarra"
¡Hombre!: Las hormigas son como el burro. Para encontrar el mejor camino, mejor usar un burro que un ingeniero de caminos, canales y puentes.
En el tema de logística si tengo experiencia. A pesar de lo que dicten las matemáticas es mejor trazar el camino siguiendo otros parámetros antes del camino más corto. Eso disminuye los costes y optimiza el transporte.
Un saludo, Edu, y no te me enfades
Si entiendo bien, quieren encontrar la ruta más corta para hallar la ruta más corta
Teoría de grafos. Lo hice para un viajero que debía ir entre ciudades con peajes entre unas de ellas y se debía calcular la ruta en la que se pagara menos peaje y gastará menos gasolina .
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
un número como 11111111(periódico: infinitos números 1) es mayor, menor o igual que un número 99999999 (con infinitos 9)?
impresionante