En optimización matemática e informática , la heurística (del griego εὑρίσκω "encuentro, descubro") es una técnica diseñada para resolver problemas más rápidamente cuando los métodos clásicos son demasiado lentos para encontrar una solución exacta o aproximada, o cuando los métodos clásicos no logran encontrar ninguna. Solución exacta en un espacio de búsqueda . Esto se logra intercambiando optimización, integridad, exactitud o precisión por 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 bifurcación en función de la información disponible para decidir qué rama seguir. Por ejemplo, puede aproximarse a la solución exacta. [1]
El objetivo de una heurística es producir una solución en un plazo de tiempo razonable que sea lo suficientemente buena para resolver el problema en cuestión. Es posible que esta solución no sea la mejor de todas las soluciones a este problema o que simplemente se aproxime a la solución exacta. Pero sigue siendo valioso porque encontrarlo no requiere un tiempo prohibitivamente largo.
Las heurísticas pueden producir resultados por sí mismas o pueden usarse junto con algoritmos de optimización para mejorar su eficiencia (por ejemplo, pueden usarse para generar buenos valores semilla).
Los resultados sobre la dureza NP en informática teórica hacen de la heurística 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 del pensamiento por computadora, ya que pueden usarse en situaciones en las que no existen algoritmos conocidos . [2]
Los criterios de compensación para decidir si se utiliza una heurística para resolver un problema determinado incluyen los siguientes:
En algunos casos, puede resultar difícil decidir si la solución encontrada por la heurística es suficientemente buena porque la teoría subyacente a la heurística no es muy elaborada.
Una forma de lograr la ganancia de rendimiento computacional esperada de una heurística consiste en resolver un problema más simple cuya solución sea también una solución al problema inicial.
Jon Bentley describe un ejemplo de aproximación para resolver el problema del viajante (TSP):
para seleccionar el orden a dibujar usando un trazador de lápiz . Se sabe que TSP es NP-duro , por lo que es difícil encontrar una solución óptima incluso para un problema de tamaño moderado. En cambio, el algoritmo codicioso se puede utilizar para dar una solución buena pero no óptima (es una aproximación a la respuesta óptima) en un período de tiempo razonablemente corto. La heurística del algoritmo codicioso dice que se debe elegir el siguiente mejor paso en ese momento, independientemente de si eso impide (o incluso imposibilita) dar buenos pasos más adelante. 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). [3]
Otro ejemplo de heurística que hace que un algoritmo sea más rápido ocurre en ciertos problemas de búsqueda. Inicialmente, la heurística prueba todas las posibilidades en cada paso, como el algoritmo de búsqueda de espacio completo. Pero puede detener la búsqueda en cualquier momento si la posibilidad actual ya es peor que la mejor solución ya encontrada. En tales problemas de búsqueda, se puede utilizar una heurística para probar buenas opciones primero, de modo que los malos caminos puedan eliminarse tempranamente (ver poda alfa-beta ). En el caso de los algoritmos de búsqueda "mejor primero" , como la búsqueda A* , la heurística mejora la convergencia del algoritmo manteniendo su corrección siempre que la heurística sea admisible .
In their Turing Award acceptance speech, Allen Newell and Herbert A. Simon discuss the heuristic search hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure. Each following step depends upon the step before it, thus the heuristic search learns what avenues to pursue and which ones to disregard by measuring how close the current step is to the solution. Therefore, some possibilities will never be generated as they are measured to be less likely to complete the solution.
A heuristic method can accomplish its task by using search trees. However, instead of generating all possible solution branches, a heuristic selects branches more likely to produce outcomes than other branches. It is selective at each decision point, picking branches that are more likely to produce solutions.[4]
Antivirus software often uses heuristic rules for detecting viruses and other forms of malware. Heuristic scanning looks for code and/or behavioral patterns common to a class or family of viruses, with different sets of rules for different viruses. If a file or executing process is found to contain matching code patterns and/or to be performing that set of activities, then the scanner infers that the file is infected. The most advanced part of behavior-based heuristic scanning is that it can work against highly randomized self-modifying/mutating (polymorphic) viruses that cannot be easily detected by simpler string scanning methods. Heuristic scanning has the potential to detect future viruses without requiring the virus to be first detected somewhere else, submitted to the virus scanner developer, analyzed, and a detection update for the scanner provided to the scanner's users.
Some heuristics have a strong underlying theory; they are either derived in a top-down manner from the theory or are arrived at based on either experimental or real world data. Others are just rules of thumb based on real-world observation or experience without even a glimpse of theory. The latter are exposed to a larger number of pitfalls.
When a heuristic is reused in various contexts because it has been seen to "work" in one context, without having been mathematically proven to meet a given set of requirements, it is possible that the current data set does not necessarily represent future data sets (see: overfitting) and that purported "solutions" turn out to be akin to noise.
Se puede realizar un análisis estadístico cuando se emplean 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 mochila , es necesario comprobar que la heurística es admisible . Dada una función heurística destinada a aproximar la verdadera distancia óptima al nodo objetivo en un gráfico dirigido que contiene un total de nodos o vértices etiquetados , "admisible" significa aproximadamente que la heurística subestima el costo para el objetivo o formalmente el de todos los lugares .
Si una heurística no es admisible, es posible que nunca encuentre el objetivo, ya sea terminando en un callejón sin salida del gráfico o saltando de un lado a otro entre dos nodos y dónde .
La palabra "heurística" se empezó a utilizar a principios del siglo XIX. Se forma de forma irregular a partir de la palabra griega heuriskein , que significa "encontrar". [5]
![{\displaystyle {i,g}\en [0,1,...,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21bac8fa995fcd566b257fa43410273f8c839b71)
