¿Qué algoritmos han cambiado tu forma de pensar sobre todo?

Divide y conquista algoritmos

Si, por ejemplo, estoy buscando mis gafas de sol en mi casa, romperé todo el espacio de donde podrían estar en dos, como el primer y segundo piso de mi casa. Luego, divida recursivamente cada uno de ellos en dos, sala de estar y cocina, y dormitorio 1 y dormitorio 2. Repetiré esto y realizaré una búsqueda binaria a escalas progresivamente más pequeñas hasta que los encuentre.

En mi búsqueda emplearé un enfoque de barrido y poda y algunas heurísticas básicas de sentido común para limitar el número de lugares que necesito buscar.

Ese es un ideal abstracto y el mundo real a menudo no es adecuado para ese tipo de cosas. Sería más como un árbol kd de lado lop, pero entiendes mi punto 😉

El conocimiento de esos algoritmos y ese tipo de pensamiento me hace más sistemático en mi enfoque, no solo en la búsqueda de cosas, sino también en otras áreas.

Desafortunadamente, mi novia es invariablemente mejor para encontrar cosas. Si bien todavía estoy atrapada en mi recursión mental, averiguando si las gafas de sol pueden caber en una pulgada cúbica, ya las ha encontrado en la parte superior de mi cabeza.

Algoritmos aleatorizados

Esto sin duda te hace cambiar de opinión. La idea muy simple de probar soluciones al azar y conservar la mejor es muy poderosa, cuanto más tiempo la dejes funcionar, mejor será tu solución y la mejor parte es que no tienes idea de cómo resolver el problema y no tienes pensar en ello

Ilustraré esto con el famoso problema de Monty-Hall:

“Hay tres puertas, una contiene un premio, el concursante tiene que elegir una puerta, luego el anfitrión elegirá una de las dos puertas restantes y mostrará que el premio no está allí. Después de esto, el concursante debe decidir si mantiene su selección original o si cambia a la puerta cerrada restante. ¿Cuál es la mejor estrategia? ¿Guardar o cambiar?

Por supuesto, existe una solución analítica para este problema, pero si no sabe por dónde empezar, simplemente puede simular el problema. Usted escribe un programa que coloca el premio al azar detrás de una de las tres puertas, elige una puerta al azar, luego abre al azar una puerta que no contiene el premio, luego calcula cuántas veces está el premio en la puerta que seleccionó originalmente o otro, dividir esto por el total de intentos le da la mejor estrategia.

Escribir un programa de este tipo lleva probablemente 2 minutos y en cualquier computadora promedio se pueden ejecutar millones de simulaciones en muy poco tiempo, el resultado será muy preciso, incluso puede decir cuál es la probabilidad de ganar de cada estrategia.

Creo que cuando te das cuenta de que puedes resolver un problema complejo sin hacer casi nada, solo conociendo la programación básica, tu forma de pensar cambia.

Esto lleva a algoritmos que son más inteligentes, como el alpinismo y el recocido simulado, donde comienza con una solución aleatoria y propone un cambio aceptando el cambio o no dependiendo de las probabilidades. Esta “metaheurística” es una fábrica de algoritmos, puede resolver muchos problemas de optimización sin siquiera pensar en el problema que solo tiene que comenzar con una solución y aprender a proponer una diferente, lo que se llama un cambio local.

Los algoritmos aleatorios, la heurística y la metaheurística son capaces de trabajar en grandes instancias de problemas de NP, la idea clave es encontrar la mejor solución posible para el tiempo que queremos dedicar al problema, una ecuación muy simple de inclinación al valor.

Para mí, nada es mejor que aprender algo en su campo que tendrá un impacto global en usted, como, como dijo, cambiar todo simplemente descubriendo un algoritmo.

El primero, más lo llamaría un meta-algoritmo son los sistemas de múltiples agentes.

La idea general es crear agentes (como en Matrix, a la derecha) que evolucionan en un entorno . Los agentes obtienen percepciones del entorno (es decir, un tipo de sentidos ) y pueden actuar. Fácil verdad?

Ahora escribirá el algoritmo del agente y verá cómo se comporta. Lo que es alucinante es que puede ser extremadamente difícil predecir lo que sucederá, incluso cuando el algoritmo del agente es extremadamente simple.

A menudo se compara con la colonia de hormigas. De hecho, una hormiga, tomar aparte, es un ser realmente simple. Ha sido ampliamente estudiado y se puede entender fácilmente. Pero, y la colonia de hormigas es mucho, mucho, mucho más compleja. Está bien organizado y, en general, es inteligente (grupos sociales, control de flujo de aire, protección contra inundaciones, etc.).

El concepto detrás de esto se llama Emergencia:

En filosofía, teoría de sistemas, ciencia y arte, la emergencia es un fenómeno por el cual las entidades más grandes surgen a través de interacciones entre entidades más pequeñas o más simples, de modo que las entidades más grandes exhiben propiedades que las entidades más pequeñas / más simples no exhiben.

De un meta-algoritmo de simulación descubrí este concepto, que encuentro intrínsecamente fascinante.

Para ir más allá, tenga en cuenta que incluso hay algoritmos de optimización de colonias de hormigas que muestran que la simulación de hormigas puede encontrar soluciones óptimas a problemas difíciles en la teoría computacional, como el famoso problema del vendedor ambulante.

Además, como una apertura que no es realmente un sistema de múltiples agentes, sino que conlleva el concepto de emergencia, permítanme presentarles el Juego de la vida de Conway. John Horton Conway escribió, en 1970, algunas reglas muy simples de “evolución” que son, en cada paso de tiempo, para cada célula del medio ambiente:

  1. Cualquier célula viva con menos de dos vecinos vivos muere, como si fuera causada por la subpoblación.
  2. Cualquier célula viva con dos o tres vecinos vivos vive hasta la próxima generación.
  3. Cualquier célula viva con más de tres vecinos vivos muere, como por sobrepoblación.
  4. Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva, como por reproducción.

(Aquí hay una simulación: Juego de vida de John Conway)

Esas reglas son bastante simples, pero de hecho, el juego es bastante complejo de estudiar. Se ha realizado un trabajo muy interesante para estudiar cómo se comporta el juego, cómo podemos predecir cuánto tiempo un ambiente tendrá células vivas dados los patrones iniciales; qué patrones son estables; que son periódicos, etc … De nuevo, simple pero fascinante, me encanta.

Es posible que mi foto de perfil esté, de hecho, relacionada con ese juego 🙂

Hem, quería hablar sobre otro pero ya no tengo tiempo, lo haré un poco más tarde 😉

PD: no dudes ni un segundo en sugerir ediciones, no soy inglés nativo (como habrás notado), así que a veces suena bien en mi cabeza, ¡pero no en la tuya!

Tierra

Es un algoritmo evolutivo en el que los genes corresponden a programas de código de bytes que se ejecutan en una máquina virtual, dentro de un único espacio de direcciones.

Los programas hacen copias de sí mismos, que están sujetos a mutaciones. También pueden sobrescribir otras instancias, matándolos así.

Esto pone en marcha un proceso evolutivo que es en muchos aspectos similar a la evolución real.

Los algoritmos evolutivos se usan para muchas cosas, pero Tierra fue un ejemplo muy temprano con algunas (para mí) propiedades alucinantes:

  • A diferencia de casi todos los otros EA, no tiene una función explícita de aptitud. El programa no repara lo que hace que un gen tenga éxito; Esto se determina implícitamente a medida que lleva a cabo su estrategia, al igual que la vida biológica. El comportamiento de los otros programas influirá en su efectividad.
  • La eficiencia del programa está vinculada a la cantidad de recursos reales que utiliza. Los programas más rápidos y pequeños tienen una ventaja evolutiva.

Mire bien a Tierra, si cree que las computadoras no pueden desarrollar soluciones creativas a los problemas, o que el orden no puede surgir de la aleatoriedad.

Algoritmos basados ​​en paralelo.

Históricamente, uno quería modificar los datos en su lugar, porque eso era mucho más rápido que copiar datos cada vez. También significaba, por lo general, que se usaba menos memoria total, lo que se consideraba un desperdicio y lento. Y esto a menudo sigue siendo un buen enfoque para una aplicación de subproceso único.

Cuando la computación paralela se volvió asequible, y luego la corriente principal, las prioridades se volvieron de su lado. Las ventajas de la concurrencia en algún punto accesible superarán rápidamente la copia de datos. Adhiérase a ese estilo, y las referencias inteligentes pueden hacer garantías inmutables al hacer copias reales. El estado inmutable de los datos le permite al compilador hacer diferentes suposiciones y varias optimizaciones que benefician enormemente la concurrencia. Además, descomplica los mecanismos de bloqueo de mutex de datos evitándolos por completo.

Como tal, ciertos comportamientos que fueron subóptimos a horribles en las técnicas de programación tradicionales se convierten en el diseño óptimo para arquitecturas que soportan paralelismo.

La lección se convierte en: la arquitectura de la máquina y los datos procesados ​​se convierten en factores importantes sobre cómo abordar una solución eficaz.

En el futuro, los algoritmos serán obsoletos. En su lugar, le preguntaremos a una red neuronal, sin saber nunca cómo llegó a la respuesta más rápida y correcta. Entonces para responder a tu pregunta; El último algoritmo.

Desearía poder recordar el primer algoritmo que codifiqué desde cero. Si tuviera que adivinar, probablemente fue el algoritmo de dibujo y actualización de Lights Out para TI-82.

Otro candidato puede haber sido el primer algoritmo matemático que estudié seriamente para comprender, aunque nunca implementé, ni entendí completamente en ese momento por qué funcionó: el método simplex para la optimización de LP.

El punto es que no son los detalles de un algoritmo particular lo que cambió mi forma de pensar, sino más bien la idea de pensar en la resolución de problemas en términos de algoritmos. La “forma algorítmica de pensar” ha infectado mi visión de todo lo matemático. Claro, puede sistematizar su perspectiva de otras cosas complejas en el mundo, pero para las matemáticas, ahora, todo lo que aprendí ahora lo pienso en términos de proceso, invariantes, corrección y complejidad computacional.

¿Todo? No puedo pensar en uno.

Recientemente utilicé una variación del problema del matrimonio estable para hacer la selección de habitaciones para nueve personas. Nos dio una forma limpia y flexible de realizar subastas a doble ciego. Pensamos más cuidadosamente sobre la selección de habitaciones y todos estaban contentos con los arreglos de habitación / precio.