Heurística (informática)

En optimización matemática e informática , la heurística (del griego εὑρίσκω eurísko , «encuentro, descubro» ^{[ 1 ]} ) es una técnica diseñada para resolver problemas con mayor rapidez cuando los métodos clásicos son demasiado lentos para encontrar una solución exacta o aproximada, o cuando no logran encontrar ninguna solución exacta en un espacio de búsqueda . Esto se consigue sacrificando la optimalidad, la completitud, la exactitud o la precisión a cambio de velocidad. En cierto modo, puede considerarse un atajo.

Una función heurística , también llamada simplemente heurística , es una función que clasifica las alternativas en los algoritmos de búsqueda en cada paso de ramificación basándose en la información disponible para decidir qué rama seguir. Por ejemplo, puede aproximar la solución exacta. ^{[ 2 ]}

Definición y motivación

El objetivo de una heurística es encontrar una solución en un plazo razonable que sea suficientemente buena para resolver el problema en cuestión. Esta solución puede no ser la mejor de todas las posibles, o simplemente aproximarse a la solución exacta. Sin embargo, sigue siendo valiosa porque encontrarla no requiere un tiempo excesivamente largo.

Las heurísticas pueden producir resultados por sí solas, o pueden utilizarse junto con algoritmos de optimización para mejorar su eficiencia (por ejemplo, pueden utilizarse para generar buenos valores iniciales).

Los resultados sobre la NP-dificultad en la informática teórica hacen que las heurísticas sean la única opción viable para una variedad de problemas de optimización complejos que deben resolverse de forma rutinaria en aplicaciones del mundo real.

Las heurísticas son la base de todo el campo de la inteligencia artificial y la simulación computacional del pensamiento, ya que pueden utilizarse en situaciones donde no existen algoritmos conocidos . ^{[ 3 ]}

Ejemplos

Problema más sencillo

Una forma de lograr la mejora en el rendimiento computacional que se espera de una heurística consiste en resolver un problema más simple cuya solución sea también una solución al problema inicial.

El problema del viajante

Jon Bentley describe un ejemplo de aproximación para resolver el problema del viajante (TSP):

"Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen?"

para seleccionar el orden de dibujo usando un trazador de pluma . Se sabe que el TSP es NP-difícil, por lo que encontrar una solución óptima incluso para un problema de tamaño moderado es difícil. En cambio, el algoritmo voraz puede usarse para dar una buena solución, aunque no óptima (es una aproximación a la respuesta óptima), en un tiempo razonablemente corto. La heurística del algoritmo voraz consiste en elegir el mejor siguiente paso en ese momento, independientemente de si eso impide (o incluso imposibilita) buenos pasos posteriores. Es una heurística en el sentido de que la práctica indica que es una solución suficientemente buena, mientras que la teoría indica que hay mejores soluciones (e incluso indica cuánto mejores, en algunos casos). ^{[ 4 ]}

Buscar

Otro ejemplo de cómo una heurística acelera un algoritmo se da en ciertos problemas de búsqueda. Inicialmente, la heurística prueba todas las posibilidades en cada paso, como en el algoritmo de búsqueda en todo el espacio. Pero puede detener la búsqueda en cualquier momento si la posibilidad actual es peor que la mejor solución encontrada. En este tipo de problemas, se puede usar una heurística para probar primero las buenas opciones, de modo que se puedan eliminar las malas rutas cuanto antes (véase poda alfa-beta ). En el caso de algoritmos de búsqueda primero el mejor , como la búsqueda A* , la heurística mejora la convergencia del algoritmo manteniendo su corrección siempre que sea admisible .

Newell y Simon: hipótesis de búsqueda heurística

En su discurso de aceptación del Premio Turing , Allen Newell y Herbert A. Simon analizan la hipótesis de la búsqueda heurística: un sistema de símbolos físicos genera y modifica repetidamente estructuras de símbolos conocidas hasta que la estructura resultante coincide con la solución. Cada paso depende del anterior, por lo que la búsqueda heurística aprende qué caminos seguir y cuáles descartar, midiendo la proximidad del paso actual a la solución. Por lo tanto, algunas posibilidades nunca se generarán, ya que se considera que tienen menos probabilidades de completar la solución.

Un método heurístico puede lograr su objetivo mediante el uso de árboles de búsqueda. Sin embargo, en lugar de generar todas las posibles ramas de solución, una heurística selecciona las ramas con mayor probabilidad de producir resultados que otras. Es selectiva en cada punto de decisión, eligiendo las ramas con mayor probabilidad de generar soluciones. ^{[ 5 ]}

Algoritmos heurísticos comunes en IA

Las heurísticas son fundamentales para muchos algoritmos de búsqueda informada y técnicas de optimización para IA: ^{[ 6 ]}

Algoritmo de búsqueda A* El algoritmo de búsqueda A* es una de las técnicas de búsqueda heurística más populares debido a su capacidad para encontrar soluciones óptimas de manera eficiente. A* combina tanto el costo real del camino como la estimación heurística del costo restante para alcanzar el objetivo.

Búsqueda voraz primero en amplitud : Este algoritmo expande el nodo más cercano al objetivo basándose únicamente en la función heurística (h(n)), sin considerar el costo del camino recorrido hasta el momento. Es rápido, pero no garantiza una solución óptima.
Ascenso de colina : Un algoritmo de búsqueda local que se mueve iterativamente desde el estado actual a un estado vecino mejor. Es sencillo de implementar, pero puede quedarse atascado en óptimos locales (soluciones subóptimas que son mejores que sus vecinos inmediatos, pero no la mejor en general). Se utiliza una función objetivo (como un gradiente para espacios continuos) para determinar la dirección.
Recocido Simulado : El recocido simulado es una técnica de búsqueda heurística que explora el espacio de búsqueda aceptando ocasionalmente soluciones peores para evitar quedarse atascado en máximos locales. Inspirado en el proceso de recocido en metalurgia, este algoritmo reduce gradualmente la probabilidad de aceptar soluciones peores a medida que avanza la búsqueda. Al permitir la exploración de soluciones subóptimas, el recocido simulado puede escapar de los máximos locales y encontrar una mejor solución global. Se utiliza comúnmente en problemas de optimización donde el espacio de búsqueda es grande y complejo.
Algoritmos genéticos : Estos se inspiran en la selección natural y utilizan procesos como la selección, el cruce y la mutación para desarrollar una población de soluciones candidatas a lo largo de generaciones.
Optimización por colonia de hormigas : un método de inteligencia colectiva inspirado en la forma en que las hormigas encuentran caminos hacia las fuentes de alimento, utilizando "feromonas" artificiales para guiar la búsqueda.

Software antivirus

El software antivirus suele utilizar reglas heurísticas para detectar virus y otros tipos de malware . El análisis heurístico busca patrones de código o comportamiento comunes a una clase o familia de virus, con diferentes conjuntos de reglas para cada virus. Si se detecta que un archivo o proceso en ejecución contiene patrones de código coincidentes o realiza dichas actividades, el antivirus deduce que el archivo está infectado. La principal ventaja del análisis heurístico basado en el comportamiento reside en su capacidad para detectar virus polimórficos (automodificables/mutantes) altamente aleatorios, que no se detectan fácilmente con métodos de análisis de cadenas más sencillos. El análisis heurístico tiene el potencial de detectar futuros virus sin necesidad de que estos sean detectados previamente en otro lugar, enviados al desarrollador del antivirus, analizados y que se proporcione una actualización de detección a los usuarios del antivirus.

Escollos

Algunas heurísticas se basan en una sólida teoría; se derivan de ella de forma descendente o se obtienen a partir de datos experimentales o del mundo real. Otras son simplemente reglas prácticas basadas en la observación o la experiencia, sin ningún fundamento teórico. Estas últimas son más propensas a errores.

Cuando se reutiliza una heurística en diversos contextos porque se ha visto que "funciona" en un contexto, sin que se haya demostrado matemáticamente que cumple con un conjunto determinado de requisitos, es posible que el conjunto de datos actual no represente necesariamente los conjuntos de datos futuros (véase: sobreajuste ) y que las supuestas "soluciones" resulten ser similares al ruido.

Se puede realizar un análisis estadístico al emplear heurísticas para estimar la probabilidad de resultados incorrectos. Para utilizar una heurística para resolver un problema de búsqueda o un problema de la mochila , es necesario comprobar que la heurística sea admisible . Dada una función heurística ${\ Displaystyle h (v_ {i}, v_ {g})}$ destinado a aproximar la distancia óptima real $d^{\star }(v_{i},v_{g})$ al nodo de destino $v_{g}$ en un grafo dirigido $G$ que contiene $n$ nodos o vértices totales etiquetados $v_{0},v_{1},\cdots,v_{n}$ , "admisible" significa aproximadamente que la heurística subestima el costo para el objetivo o formalmente que $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ a pesar de $(v_{i},v_{g})$ dónde ${i,g}\in [0,1,...,n]$ .

Si una heurística no es admisible, puede que nunca encuentre el objetivo, ya sea porque termina en un callejón sin salida del gráfico. $G$ o saltando de un nodo a otro $v_{i}$ y $v_{j}$ dónde ${i,j}\neq g$ .

Etimología

La palabra «heurística» comenzó a usarse a principios del siglo XIX. Se forma de manera irregular a partir de la palabra griega heuriskein , que significa «encontrar». ^{[ 7 ]}

Véase también

Heurística constructiva
Metaheurística : Métodos para controlar y ajustar algoritmos heurísticos básicos, generalmente mediante el uso de memoria y aprendizaje.
Mateheurística : Algoritmos de optimización realizados mediante la interoperabilidad de técnicas metaheurísticas y de programación matemática (PM).
Optimización de búsqueda reactiva: Métodos que utilizan principios de aprendizaje automático en línea para el autoajuste de heurísticas.

Referencias

↑ "Heurística" . 7 de abril de 2025.
↑ Pearl, Judea (1984). Heurísticas: estrategias de búsqueda inteligentes para la resolución de problemas informáticos . Estados Unidos: Addison-Wesley Pub. Co., Inc., Reading, MA. pág. 3. OSTI 5127296 .
↑ Apter, Michael J. (1970). La simulación por ordenador del comportamiento . Londres: Hutchinson & Co. pág. 83. ISBN 9781351021005.
↑ Jon Louis Bentley (1982). Writing Efficient Programs . Prentice Hall. p. 11 .
↑ Allen Newell y Herbert A. Simon (1976). "La informática como investigación empírica: símbolos y búsqueda" (PDF) . Comm. ACM . 19 (3): 113– 126. doi : 10.1145/360018.360022 . S2CID 5581562 .
↑ "Búsqueda local" . CS 188: Introducción a la inteligencia artificial . Universidad de California, Berkeley . Consultado el 19 de enero de 2026 .
↑ "Definición de heurística en inglés" . Oxford University Press. Archivado del original el 23 de octubre de 2016. Consultado el 22 de octubre de 2016 .

[1] "Heurística" . 7 de abril de 2025.

[2] Pearl, Judea (1984). Heurísticas: estrategias de búsqueda inteligentes para la resolución de problemas informáticos . Estados Unidos: Addison-Wesley Pub. Co., Inc., Reading, MA. pág. 3. OSTI 5127296 .

[3] Apter, Michael J. (1970). La simulación por ordenador del comportamiento . Londres: Hutchinson & Co. pág. 83. ISBN 9781351021005.

[4] Jon Louis Bentley (1982). Writing Efficient Programs . Prentice Hall. p. 11 .

[5] Allen Newell y Herbert A. Simon (1976). "La informática como investigación empírica: símbolos y búsqueda" (PDF) . Comm. ACM . 19 (3): 113– 126. doi : 10.1145/360018.360022 . S2CID 5581562 .

[6] "Búsqueda local" . CS 188: Introducción a la inteligencia artificial . Universidad de California, Berkeley . Consultado el 19 de enero de 2026 .

[7] "Definición de heurística en inglés" . Oxford University Press. Archivado del original el 23 de octubre de 2016. Consultado el 22 de octubre de 2016 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]