If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Usar heurísticas

Los problemas más difíciles en ciencias de la computación son aquellos que corren en tiempo superpolinomial y duplican el número de pasos requeridos cada vez que el tamaño de la entrada aumenta, ¡o aún más que el doble! Las computadoras pueden ser capaces de resolver esos problemas para entradas de tamaño muy pequeño, pero muy pronto llegan al punto donde su solución puede tomar meses o años de tiempo de cómputo.
Los científicos de computación usan un enfoque diferente para resolver esos problemas difíciles: en vez de tratar de encontrar la solución perfecta, tratan de encontrar una solución aproximada. Una respuesta buena es mejor que ninguna respuesta.
Una forma de encontrar respuestas aproximadas a un problema es usar una heurística, una técnica que guía a un algoritmo a encontrar buenas opciones. Cuando un algoritmo usa una heurística, ya no necesita buscar de manera exhaustiva todas las soluciones posibles, y por tanto puede encontrar soluciones aproximadas mas rápido. Una heuristica es un atajo que sacrifica exactitud y completez.
Para entender mejor las heurísticas, recorramos juntos uno de los más famosos problemas difíciles en ciencias de la computación.

El problema del vendedor viajero

El problema del vendedor viajero (TSP) hace la siguiente pregunta:
"Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visite cada ciudad exactamente una vez, y regrese a la ciudad de origen?"
Por ejemplo, este diagrama muestra el recorrido más corto entre 46 ciudades alemanas:
46 puntos etiquetados como ciudades alemanas; una línea pasa por los puntos, exactamente una vez por cada uno de ellos.
El problema TSP lo enfrentaron originalmente los vendedores viajeros, pero en realidad es relevante a muchas áreas: enrutar datos en una red, fabricar microchips, observar localizaciones con un telescopio, y aún secuenciar DNA. En todos estos casos, queremos una solución que encuentre un camino eficiente entre multiples localidades.

El enfoque de fuerza bruta

TSP es un problema combinatorio, y eso es lo que lo hace tan difícil. La única manera para que una computadora pueda encontrar la solución óptima es usar el "enfoque de fuerza bruta": ensayar todos los posibles caminos entre ciudades, medir la distancia de cada camino, y escoger el camino con la distancia más corta.
La siguiente visualización genera cuatro ciudades aleatorias, calcula los caminos posibles, y resalta el camino óptimo. Haga clic sobre los caminos para ver las posibilidades que encuentra, o comience de nuevo para ensayar con otro conjunto de ciudades.
¿Observas que siempre genera dos caminos óptimos? Los caminos se ven iguales, pero están en orden inverso. Técnicamente, ambos son soluciones óptimas, y un vendedor podría escoger un camino más corto que el otro por razones no relacionadas con distancia.
A la computadora no le toma mucho tiempo generar los caminos posibles para 4 ciudades—menos de un décimo de milisegundo en mi máquina. Es bastante rápida aún para 5 ciudades, 6 ciudades, y 7 ciudades; puedes ensayarlas por tí mismo si confías en tu computadora. Pero el tiempo de ejecución crece exponencialmente, así que unos pocos milisegundos se convierten rápido en unos cuantos segundos.
Esta es una tabla de tiempos de ejecución para 4 a 11 ciudades en mi máquina:
CiudadesCaminosMilisegundos
460.1
5240.3
61200.8
77203
8504010
94032050
10362880520
1136288005770
¿Notas el salto de 520 a 5770 al final? Fué ahí que decidí tenerle lástima a mi pobre portátil y no ir más alto.
A esa velocidad la computadora necesitaría alrededor de 253 milisegundos para calcular los caminos para las 46 ciudades alemanas del diagrama anterior. Eso es alrededor de 642 años, que es mucho más que el tiempo que ha existido el universo. Por supuesto, hay computadoras mucho más poderosas que mi portátil, pero aun una supercomputadora 200,000 veces más poderosa requeriría 337 años.
Así que ¿cómo fue calculado arriba ese camino de 46 ciudades? ¡Con una heurística, por supuesto!

Desarrollo de una heurística

Una manera de encontrar una heurística, es considerar como tú mismo enfocarías el problema. A los humanos no nos gusta desperdiciar esfuerzo innecesario para resolver problemas, así que a menudo encontramos atajos que nos llevan a una solución suficientemente buena,.
La visualización que sigue muestra 5 ciudades aleatorias. Propón un camino más corto haciendo click en las ciudades, comenzando con la siguiente ciudad a visitar desde A. Cuando termines, encuentra cómo se compara tu camino con el camino óptimo.
¿Cómo se comparó tu camino con el camino óptimo? Que heurísticas usaste para decidir el orden en el cual visitar las ciudades? ¿Podría la computadora usar la misma heurística?
No todas las heurísticas son iguales, pero todas ellas nos pueden dar ideas sobre diferentes formas de guiar la computadora a encontrar mas rápido una buena solución.

La heurística del vecino más cercano

Una heurística común para TSP es el "vecino más cercano": la computadora siempre elige la ciudad más cercana que no ha sido visitada, como la siguiente ciudad en el camino.
Ensáyala en la visualización que sigue. Ahora que estamos usando una heurística, la puedes ensayar con muchas más ciudades que antes. Aún 46 ciudades apenas toman unos pocos milisegundos en mi máquina.
Impresionante, ¿verdad? Sin una heurística, podríamos haber esperado hasta la muerte del universo para encontrar una solución perfecta. Ahora, gracias a una simple heurística, podemos ver resultados casi instantáneamente.
Pero recuerda, una heurística solo produce una solución aproximada. Para esta heurística en particular, la solución será, en promedio, alrededor de 25% más larga que el camino más corto. Aún más, hay veces que la heurística del vecino más cercano produce la peor ruta.
Los científicos de computación han encontrado docenas de otras heurísticas para TSP, incluyendo "optimización de hormigueros", una heurística inspirada por la forma en que las hormigas depositan feromonas a lo largo de un camino. Para cada heurística, se analiza que tan cerca está de encontrar la solución perfecta, cuánto tiempo toma, y qué tan frecuentemente ocurre el peor caso.

Heurísticas en todos lados

Hay muchos problemas además de TSP que se benefician de heurísticas.
Aqui hay algunos:
Problema de la mochila: tienes una mochila y un conjunto de objetos de varios tipos, cada uno con peso y valor. ¿Cuántos objetos de cada tipo puedes empacar en la mochila, de manera que el peso total no exceda un límite y que se maximice el valor total? Este tipo de problema se presenta de muchas formas en diferentes industrias, como en asesoría financiera para seleccionar inversiones en un portafolio, o en fábricas para encontrar la manera óptima de cortar materia prima. Una heurística es ordenar por razón valor/peso cuando se selecciona el siguiente objeto a empacar.
Un gráfico con una mochila y 4 cajas. La mochila está etiquetada con 15 kg. La caja 1 está etiquetada con 12 kg, $4. La caja 2 está etiquetada con 2 kg, $2. La caja 3 está etiquetada con 4 kg, $10.
Un problema de mochila sencillo con peso total de 15kg y 4 tipos de objetos.
Jugar juegos: para que una computadora le gane a un humano en un juego (o al menos pierda respetablemente), debe escoger la jugada con la mayor probabilidad de ganar. Para verdaderamente predecir el triunfo, la computadora tiene que calcular el árbol completo del juego, desde la jugada actual hasta una final, anticipando todas las jugadas que el humano pueda responder. Para el sencillo juego de Tic-Tac-Toe, eso es 362,880 situaciones posibles, pero para un juego más sofisticado como ajedrez, ¡eso es 10120 situaciones! Afortunadamente, las heurísticas como "minimax" ayudan a podar el árbol de posibilidades.
Un diagrama de árbol con tres niveles. El primer nivel muestra un tablero vacío de Tic-Tac-Toe. El segundo nivel muestra tres tableros de Tic-Tac-Toe con una X en un sitio diferente en cada uno. El tercer nivel muestra 12 tableros de Tic-Tac-Toe con una O en un sitio en cada uno también.
Un juego parcial de Tic-Tac-Toe.
Ubicación de instalaciones: imagina una cadena de supermercados con 20 tiendas en un estado y que quiere construir 5 bodegas para entregar comida a los supermercados. Su objetivo es minimizar costos y maximizar la velocidad de entrega. El problema de ubicación de instalaciones es encontrar la localización óptima para esas 5 bodegas. Este mismo problema lo enfrentan las aplicaciones web que quieren distribuir sus servidores backend para responder rápidamente a solicitudes de los usuarios. Las heurísticas como "búsqueda local" ayudan a reducir la variedad de ubicaciones posibles.
Un diagrama de dos partes. La primera parte muestra 20 puntos azules distribuidos en un espacio rectangular. La segunda parte muestra 5 puntos rosados entremezclados con esos puntos, con flechas que conectan cada punto rosado a puntos azules.
20 localizaciones y una posible solución con 5 instalaciones.
Todos éstos son problemas combinatorios, donde para encontrar la respuesta óptima, una computadora necesitaría buscar un número exponencialmente creciente de combinaciones. Los problemas combinatorios son bastante comunes en el mundo real, así que tanto las empresas como los científicos de computación se preocupan mucho de encontrar heurísticas que den las mejores soluciones aproximadas.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el área de preguntas abajo!

¿Quieres unirte a la conversación?

¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.