inventario
Páginas: 10 (2273 palabras)
Publicado: 23 de octubre de 2013
Heurística
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 ejecutarazonablemente 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í, estasinstancias 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ística en la IA
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 paradeterminar 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 elprocesamiento del lenguaje basado en reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada para referirse a las reglas.
En IA, se emplean heurísticas en dos casos
Un problema puede no contar con solución exacta debido a ambigüedades inherentes en el problema o datos disponibles.
Ej: Diagnóstico médico
Ej: Visión
Un problema puede tener solución exacta, pero el costocomputacional por encontrarla puede ser prohibitivo
Ej: Problema del agente viajero
Ej: Problema de coloración
Ej: Juego de ajedrez
Funciones heurística:
En una función heurística no solo existe el deseo de encontrar una solución sino también encontrar el camino más corto a una meta.
Denotada 11(n):
h(n) = coste estimado del camino más barato desde el nodo n a un nodo objetivo.Por ejernplo, en Rumanía podríamos estimar el coste del camino rnas barato desde Arad a Bucarest con Ia distancia en línea recta desde Arad a Bucarest.
Las funciones heurísticas son la forma más común de transmitir el conocimiento adicional del problema al algoritmo de búsqueda.
h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
Como era de esperar, ninguna sobrestima el coste solución verdadero, que es26.
El efecto de la precisión heurística en el rendimiento
Una manera de caracterizar la calidad de una heurística es el b* factor de ramificación eficaz. Si el numero total de nodos generados por A* para un problema particular es N, y la profundidad de la solución es d, entonces b* es el factor de ramificación que un árbol uniforme de profundidad d debería tener para contener N+1 nodos.
N + 1= 1 + b* + (b*) + … + (b*) ˆ d
Funciones heurísticas admisibles
Se denomina a la función heurística que encuentra el camino más corto a una meta siempre que exista.
La heurística es admisible porque la solución óptima en el problema original es, por definición, también una solución en el problema relajado y por lo tanto debe ser al menos tan cara como la solución optima en el problemarelajado.
Un problema con la generación de nuevas funciones heurísticas es que a menudo se falla al conseguir una heurística . Cuando no se encuentra la mejor heurística se puede utilizar la mejor de todas combinando dichas funciones como se muestra a continuación:
h = máx. {h1(n),….hn(n)}
A un problema con menos restricciones en las acciones se le llama problema relajado.
El costo de una...
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 ejecutarazonablemente 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í, estasinstancias 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ística en la IA
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 paradeterminar 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 elprocesamiento del lenguaje basado en reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada para referirse a las reglas.
En IA, se emplean heurísticas en dos casos
Un problema puede no contar con solución exacta debido a ambigüedades inherentes en el problema o datos disponibles.
Ej: Diagnóstico médico
Ej: Visión
Un problema puede tener solución exacta, pero el costocomputacional por encontrarla puede ser prohibitivo
Ej: Problema del agente viajero
Ej: Problema de coloración
Ej: Juego de ajedrez
Funciones heurística:
En una función heurística no solo existe el deseo de encontrar una solución sino también encontrar el camino más corto a una meta.
Denotada 11(n):
h(n) = coste estimado del camino más barato desde el nodo n a un nodo objetivo.Por ejernplo, en Rumanía podríamos estimar el coste del camino rnas barato desde Arad a Bucarest con Ia distancia en línea recta desde Arad a Bucarest.
Las funciones heurísticas son la forma más común de transmitir el conocimiento adicional del problema al algoritmo de búsqueda.
h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
Como era de esperar, ninguna sobrestima el coste solución verdadero, que es26.
El efecto de la precisión heurística en el rendimiento
Una manera de caracterizar la calidad de una heurística es el b* factor de ramificación eficaz. Si el numero total de nodos generados por A* para un problema particular es N, y la profundidad de la solución es d, entonces b* es el factor de ramificación que un árbol uniforme de profundidad d debería tener para contener N+1 nodos.
N + 1= 1 + b* + (b*) + … + (b*) ˆ d
Funciones heurísticas admisibles
Se denomina a la función heurística que encuentra el camino más corto a una meta siempre que exista.
La heurística es admisible porque la solución óptima en el problema original es, por definición, también una solución en el problema relajado y por lo tanto debe ser al menos tan cara como la solución optima en el problemarelajado.
Un problema con la generación de nuevas funciones heurísticas es que a menudo se falla al conseguir una heurística . Cuando no se encuentra la mejor heurística se puede utilizar la mejor de todas combinando dichas funciones como se muestra a continuación:
h = máx. {h1(n),….hn(n)}
A un problema con menos restricciones en las acciones se le llama problema relajado.
El costo de una...
Leer documento completo
Regístrate para leer el documento completo.