Comparing Algorithms: A* vs Dijkstra, in the city's map.
Vložit
- čas přidán 23. 07. 2024
- I was out here bored in vacations making some animations comparing Dijkstra's algorithm with A* on Buenos Aires City's map (that's how programmers have fun) and they turned out so cool I decided to convert them into a CZcams video. It's not a deep rigurous analysis or anything like that, it's simply satisfying to watch :p
If you're interested in the frame-generating code here's the repo:
github.com/santifiorino/maps_...
Contact / Socials:
hoo.be/santifiorino
----------------------------------------------------
00:00 Intro
01:32 A*
02:11 Dijkstra
03:10 Comparison
05:27 Second Experiment
06:52 More simulations
----------------------------------------------------
The visual style is strongly based (stolen) from this video:
• A* (A-Star) Pathfindin... - Věda a technologie
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
Es algo super importante.
En emergencias usamos 2 algoritmos de búsqueda al mismo tiempo. Yo personalmente siempre uso avenidas. Mas anchas y mejor estado de la calzada.
Algún día en esos algoritmos podrán añadir el estado de la calzada, cantidad de semáforos, cruces y "bolardos" (bultos en la carretera xq no corran los coches).. etc.. pero sobretodo el estado de la calzada y catalogar las carreteras segun su calzada.
Si desarrollas un software que además de los algoritmos cuantifique mas variables te aras de oro.
En todos los servicios de emergencia de Europa usan los mismos de google que son una mierda y te cobran un ojo de la cara por comprar los y actualizar los.
Eso de los algoritmos de navegación (y el estado de la calzada) es el negocio del próximo siglo.
Hoy en día servicios como Google Maps usan la información que tienen de los usuarios y el gobierno (ubicación, semáforos, alertas de tráfico, etc.) para adaptar sus caminos y estimar con mayor precisión la velocidad promedio que tendría un auto en cada cuadra en tiempo real, y por tanto encontrar el camino más rápido en ese momento. Por eso mismo a veces nos sugiere otros caminos que veces anteriores, aunque tengamos el mismo origen y destino. Google Maps es gratis, pero porque el "producto" sos vos. Si nos ponemos a pensar, Google realmente es una empresa de publicidad, que usa tus datos para vender más anuncios
@@fede9003 Justo, Google mete esos parámetros ocultos por medio de la velocidad de los usuarios. Funciona genial para el usuario común. Pero el problema para los servicios de emergencias es que ellos pueden hacer lo que quieran con los límites de velocidad y pueden navegar en el tráfico; así que no es muy útil usar google maps o similares.
no te conozco, no se de programacion, no se de algoritmos y no se como llegue aca, pero fue un videazo bien explicado y entretenido, te felicito
Se entiende mejor este vídeo que 4 meses de clase en una asignatura de la universidad. Tremendo!
🇨🇱
06:50 simplemente por el placer visual ‼️
Gran video, felicitaciones, y gracias.
Saludos de 🇨🇱
¡Buenísimo video! No conocía esa librería, pero ahora va a tocar revisarla. Saludos desde México
Muy buen vídeo, no he revisado a fondo, pero A* suena como una buena elección para procesar una malla de navegación (navigation mesh) para videojuegos, no es la ruta más óptima, pero el número de iteraciones y la calidad de respuesta es muy razonable, además eso explicaría porque en algunas ocasiones en videojuegos los enemigos toman rutas no tan evidentes a nuestros ojos, como pequeños desvíos en lugar de ir directamente a nosotros el jugador
Es justamente la razon por la que Unity usa A* en su integración de NavMeshes
generalmente es así, se utiliza el algoritmo A*.
De hecho A* será óptimo si eres capaz de dar una heurística h la cual sea óptima es decir el coste verdadero que hay esta h* en problemas sencillos es facil de calcular sin embargo conforme se complica el problema suele ser complicado conseguir que tu h sea h* osea la óptima, esto implica que sobreestimemos el valor de algunos nodos y por lo tanto escojamos otros dándonos un camino no óptimo.
pense lo mismo!!
Excelente contenido Santiago, me suscribo y ojala publiques más! Abrazo
Che, muy buen video
Muy interesante y muy bien explicado. Y me encantó todo el laburo de edición que le pusiste, te quedo de lujo, excelente música ademas.
Muchas gracias, Santiago. Nos ayudas a entender procesos que se ejecutan ocultos a nuestros ojos, en las aplicaciones que usamos cotidianamente. Espero que dispongas de tiempo para seguir subiendo vídeos tan didácticos, que consiguen entender de un modo sencillo, procesos que suelen ser bastante complicados.
Gran video amigo. Creo que es una chulada como has desarrollado el ejemplo. Saludos
videazo hermano
Excelente video, este tipo de contenido deberían darlo en las universidades (refiriéndome a los ejemplos visuales/prácticos), ¡muchas gracias!
Excelente video y me encanta este tipo de contenido, sos un crack
Que gran video, disfrute de ver ambos algoritmos en animación. Adicional a ello, la explicación q diste fue muy buena
Hola Santiago, te felicito por tu manera de explicar temas complejos. Como ex estudiante de Ingenieria en Computación es muy facil engancharse con la belleza de los algoritmos y mas si son complejos, una de mis materias preferidas de la universidad ( Y hay otro monton de algoritmos de camino mas corto por explorar 🙂). Gracias por el video, saludos.
Muy buen video... y menos mal que fue improvisado! je je, simplemente brillante!, ganaste un subscriptor
Loco... esto es un video de putisima madre! me encantan este tipo de cosas matemáticas y más si las mezclas con programación. Te seguía en tik tok pero no aca, ahora me voy a chusmear el resto del canal. Gracias por tremendo video!
"video de putisima madre" jajajaja
I'll be trying to fit that expression into portuguese, somehow
@@Gustavo-ok7jwjaja
muy muy bueno, no te das una idea lo bien que me viene para resolver un problema de mejora de una red de tránsito. Mil gracias!!!
por vos me anoté a cs y voy a empezar este año con el primer año de la carrera! muy bueno el video y te vi en el recital de usted
aguante usted 🫵
éxitos estimado! no le afloje
Suerte. Yo ya voy en mi 3er año. Y ya estoy muerto aunque la verdad en este momento de mi vida universitaria puedo decir que ya se lo suficiente como para ejercer como practicante.
cs?
@@loo6942 Computer Science, asi se le llama a la carrera de informatica donde te enseñan una mezcla de desarrollo de software, ciber seguridad y Ciencia de Datos
Felicitaciones por sus reflexiones, no son para nada superficiales, siempre puedes aplicar/descubrir algún algoritmo para prácticamente cualquier fenómeno. Espero ansioso un nuevo video. (Pienso en la aplicación para vehículos de emergencia de alguna manera) muchos saludos desde Chile.
Excelente material! Me saco el sombrero! Gracias
Que bueno que haya este tipo de contenido y encima en español, buen video bro 👍
Que gran contenido, apuntate un nuevo seguidor. Saludos parcero!
Tremendo laburo! Muy buen video!
esto es genial! muy bonito, vaya trabajo!
Me pongo de pie por este buen trabajo, gracias por compartir tu talento
En estos 8 minutos aprendí demasiado, ya conocía el algoritmo de Dijkstra gracias al CCNA de cisco pero no había interiorizado bien la aplicación de este algoritmo en otras áreas que no fueran redes. Excelente video.
Muy bien video hay un potencial increible en este canal
simplemente maravilloso 🚀🌟!
Muy buen video, se explica de manera maravillosa todo el ejemplo que mostro.
La ultima vez que vi un video tuyo recuerdo que tenias mas de 100 mil subs o quiza me equivoque (efecto manuela), muchas gracias por el video y difundir estos temas
no ajajjs, en otro video digo que 100k es mi objetivo, capaz te lo confundiste con eso, pero ahora toy en el pico de subs del canal. gracias :)
Increíble vídeo. Muchas gracias por el aporte; ahora le toca a uno experimentar :3
increíble! me suscribo!
Que video mas excelente, sos un capo
No llevaba ni un minuto del video y ya me subscribí. Interesantísimo el tema
Me vienen recuerdos de algoritmos 3, sos un genio. Un abrazo y fuerza.
Qué gusto ver videos así!
Me hiciste recordar que existe el algoritmo A*😅
Muy buen video crack!
Genial, muy buen video.
Estaria fino ver que pasa tomando en cuenta los pesos del contador.
¡Buenísimo! Voy a usar tus animaciones para mis clases.
Que buen experimento y conclusiones. Estos algoritmos los vimos en la facultad y son super interesantes.
¡Excelente video! La explicación de las diferencias entre ambos es fabulosa, mucho mejor que de un libro.
Maestro gran video
Hermoso video. 😮
Muy bueno, hacia años no veía estos algoritmos. Es bueno recordar que existen 😁.
Saludos
me encanto! gran video gran aporte
Entre a ver su canal y al ver su banner directamente me fui al botón de suscribirme... Un grande sin duda
Alto laburo de video,esta increíble
Muy buen video!! nuevo sub! 🤠
Como me emocionan tus videos 😎
Genial aportación y una docencia brillante...de 10
tremendo, gracias!
Amazing visuals. Thank you for sharing!
que video tan interesante, muchas gracias por compartir
Que bueno amigo!
desconocía está librería, definitivamente es una buena herramienta para algún trabajo de tesis a futuro, muchas gracias
Muy buen video! Saludos desde Brasil
Un 10 de video. Felicidades.
contenido sublime! estas loco
Excelente brodi
suscrito!, simplemente increible!
Te extrañeeee muy buen videoooo
Excelente video
Demasiado bueno el video❤
Faaaaa buen video, buena comparacion
Muy bonito Santiago, y sí se presta para reflexión filosófica, pero qué te digo siempre atravesada por la lógica del sistema social. Con esto último me refiero a que si bien solemos tomar decisiones que "maximizan" el placer en el corto plazo, también es el sistema social concreto en el que nos reproducimos que contribuye a decidir una cosa por la otra. Hablando de otra cosa, pero de lo mismo, es por eso que valoramos tanto (en este sistema reitero) todos los "bienes" y "servicios" que reducen los costos de transacción (dicho de otro modo, los que nos "evitan la fatiga") y vaya tal vez al final todo se reduzca a las leyes de la termodinámica. Bueno aquí ya me puse filosófico yo. En fin, suscrito y muy genial tu animación. Saludos!!!
Hace ocho meses fué la última vez que vi un video tuyo, y apenas escuché tu voz te reconocí xd
poderoso ese video, gracias por compartirlo.
Tu video es una obra de arte 🤌
Muy bonito tu video. Gracias
No sé nada de programación. Tu video me resulta hermoso, desde los gráficos, las "animaciones", hasta tu locución. Hiciste algo por placer, y quedó artístico.
Caí en este video por ser un administrador adicto al OSPF. Muy bueno ! Gracias me re sirve !
muy buen video compa
fantastico amigo, faltan youtubers de ciencia argentinos, segui metiendole
Sos muy bueno explicando lógica algorítmica 🤓📚
Excelente!
tenes un potencial zarpado de convertirte en el sebastian lague que habla español (espero que lo consideres un cumplido), me encantaría ver mucho más contenido como éste
Gracias! Obvio que lo tomo como un cumplido, Seb es de mis principales fuentes de inspiración para mi contenido! Mi prox. vídeo va a ser sobre motores de ajedrez, 100% inspirado por su vídeo del tema, aunque tomé un enfoque distinto para la programación así que va a tener mi propio toque (además de las explicaciones, obvio :p)
Crack!
Es tan geniales las animaciones, seria genial poder replicarlas
Que genial que genial grx 😊
Le di me gusta al primer minuto, excelente!
Veo que se podría aplicar a diseño de redes de fibra óptica también, pero no se como 😅
Muy buen video
Te veo en la facu y me da cosa saludarte videazo
sabes estudio arquitectura y esto es sumamente util. por lo menos en lo que sufri en el pregrado era en los planos de lotes que se hacen a blanco y negro, siempre tuve que hacer toda a mano, no se si te llegue a interesar ver como se puede hacer ahi. un saludo
Buenisimo
Muy buen video, lo usaré para enseñar Dijkstra en la universidad (con créditos naturalmente)
Estuvo increible
tremendo el segundo experimento voy a intentarlo como proyecto para mi clase de analisis de algoritmos
Excelente video entretenido de ver a las 2 AM xD
Nunca entendí como hacer para poder sacar datos de python y graficarlos pero bueno supongo que eso es parte del análisis de datos cuando resubas el código lo voy a mirar a ver si aprendo algo nuevo.
Saludos
Gracias! Justo recién actualicé la descripción, ya está el código disponible :)
Qué buen video O_O
Gracias capo :*
Órale amigo, muchas gracias por tu video me recordó a cuando estudiaba en la universidad y hacía pruebas con ambos algoritmos al igual con bases de datos espaciales, me gustó mucho como explicas y demuestras el funcionamiento real del algoritmo para que muchos colegas y amantes de la ciencia entiendan con más detalle la magia de ambos algoritmos (siempre he dicho no hay uno mejor que otro sino que debes saber cuál elegir conforme a tus necesidades), a hasta que el algoritmo de CZcams me dio algo interesante y no solo culos 🤭😂
Siplemente genial.
Espectacular! No sabes lo que me beneficia la librería que mencionas de Python que genera los grafos
Estaría buenísimo un vídeo sobre ajedrez y minimax, explicas muy bien la verdad
Gracias! El vídeo de ajedrez y minimax es exactamente lo que tenía planificado para el próximo vídeo, de hecho ya lo empecé a programar ajjaja, que bueno saber que es algo que les gustaría ver. Spoiler: Quiero invitar a alguien al canal para que me responda dos o tres preguntas en ese vídeo pero es bastante ambicioso, veremos :)
Brutal
Que maravilla de video like y suscribir
arte visual!
un espectáculo!