Heurística (informática)


Heurística (informática)
Este artículo trata sobre la heurística en todas las ramas de informática. Para la heurística en los antivirus, véase Heurística en antivirus.

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas. Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.

A menudo, pueden encontrarse instancias concretas del problema donde la heurística producirá resultados muy malos o se ejecutará muy lentamente. Aun así, estas instancias concretas pueden ser ignoradas porque no deberían ocurrir nunca en la práctica por ser de origen teórico. Por tanto, el uso de heurísticas es muy común en el mundo real.

Heurísticas para encontrar el camino más corto

Para problemas de búsqueda del camino más corto el término tiene un significado más específico. En este caso una heurística es una función matemática, h(n) definida en los nodos de un árbol de búsqueda , que sirve como una estimación del coste del camino más económico de un nodo dado hasta el nodo objetivo. Las heurísticas se usan en los algoritmos de búsqueda informada como la búsqueda egoísta. La búsqueda egoísta escogerá el nodo que tiene el valor más bajo en la función heurística. A* expandirá los nodos que tienen el valor más bajo para g(n) + h(n), donde g(n) es el coste (exacto) del camino desde el estado inicial al nodo actual. Cuando h(n) es admisible, esto es si h(n) nunca sobrestima los costes de encontrar el objetivo; A* es probablemente óptimo.

Un problema clásico que usa heurísticas es el puzzle-n. Contar el número de casillas mal colocadas y encontrar la suma de la distancia Manhattan entre cada bloque y su posición al objetivo son heurísticas usadas a menudo para este problema.

Efecto de las heurísticas en el rendimiento computacional

En cualquier problema de búsqueda donde hay b opciones en cada nodo y una profundidad d al nodo objetivo, un algoritmo de búsqueda ingenuo deberá buscar potencialmente entre bd nodos antes de encontrar la solución. Las heurísticas mejoran la eficiencia de los algoritmos de búsqueda reduciendo el factor de ramificación de b a (idealmente) una constante b * .

Aunque cualquier heurística admisible devolverá una respuesta óptima, una heurística que devuelve un factor de ramificación más bajo es computacionalmente más eficiente para el problema en particular. Puede demostrarse que una heurística h2(n) es mejor que otra h1(n), si h2(n) domina h1(n), esto quiere decir que h1(n) < h2(n) para todo n.

Heurísticas en la inteligencia artificial

Muchos algoritmos en la inteligencia artificial son heurísticos por naturaleza, o usan reglas heurísticas. Un ejemplo reciente es SpamAssassin que usa una amplia variedad de reglas heurísticas para determinar cuando un correo electrónico es spam. Cualquiera de las reglas usadas de forma independiente pueden llevar a errores de clasificación, pero cuando se unen múltiples reglas heurísticas, la solución es más robusta y creíble. Esto se llama alta credibilidad en el reconocimiento de patrones (extraído de las estadísticas en las que se basa). Cuando se usa la palabra heurística en el procesamiento del lenguaje basado en reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada para referirse a las reglas.


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Heurística — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Heuristica de la representatividad — Este artículo está huérfano, pues pocos o ningún artículo enlazan aquí. Por favor, introduce enlaces hacia esta página desde otros artículos relac …   Wikipedia Español

  • Heurística (desambiguación) — El término heurística puede hacer referencia a: En general, se denomina heurística a la capacidad de un sistema para realizar de forma inmediata innovaciones positivas para sus fines. La heurística aplicada a la informática. La heurística en… …   Wikipedia Español

  • Heurística en antivirus — En los productos antivirus se conoce como heurística a las técnicas que emplean para reconocer códigos maliciosos (virus, gusanos, troyanos, etc.) que no se encuentren en su base de datos (ya sea porque son nuevos, o por no ser muy divulgados).… …   Wikipedia Español

  • Falso positivo (informática) — Saltar a navegación, búsqueda Un falso positivo para un antivirus, se refiere a la detección de un archivo como virus (o alguna otra clase de malware) por parte de un antivirus, cuando en realidad no es ningún virus o malware. Estos errores… …   Wikipedia Español

  • Wikiproyecto:Informática — Atajo PR:IPR:I Está página es un Wikiproyecto, un área …   Wikipedia Español

  • Instituto de Automática e Informática Industrial — El Instituto de Automática e Informática Industrial (Instituto ai2), perteneciente a la Universitat Politècnica de València (UPV) (Universidad Politécnica de Valencia, en castellano) es una estructura de investigación cuyas áreas de actuación son …   Wikipedia Español

  • Lista (informática) — En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos… …   Wikipedia Español

  • Algoritmo de eliminación de variables — El algoritmo de eliminación de variables es un algoritmo de adquisición de conocimiento probabilístico a partir de una red bayesiana. Dada una red bayesiana y una serie de valores observados para ciertas variables, denominadas de evidencia, se… …   Wikipedia Español

  • Sistema de detección de intrusos — Un sistema de detección de intrusos (o IDS de sus siglas en inglés Intrusion Detection System) es un programa usado para detectar accesos no autorizados a un computador o a una red. Estos accesos pueden ser ataques de habilidosos hackers, o de… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.