martes, 2 de junio de 2015
MÉTODOS HEURISTICOS
MÉTODOS HEURISTICOS
Métodos de escalada
Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese momento. Se dividen en dos grupos: Los métodos irrevocables, que no preven la vuelta a un lugar del espacio de estados si el camino resulta inadecuado. Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos que el camino elegido no es el más adecuado.
La escalada simple.
Primero el mejor.
Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
Búsqueda avara
Una estrategia simple consiste en reducir al mínimo el costo estimado para lograr una meta. Aunque es posible estimar el costo que implica llegar a una meta desde un estado determinado, no es posible hacerlo con precisión. La función que se utiliza para calcular tales estimados de costo se conoce como función heurística.
A la búsqueda que utiliza una función heurística para escoger qué nodo se expandirá es denominada “búsqueda avara”.
La búsqueda avara y la preferente por profundidad se asemejan por su indicación a utilizar una sola ruta hasta llegar a la meta, pero se atorarán cuando se topen con un callejón sin salida. Esta búsqueda no es óptima y es incompleta.
http://www.angelfire.com/ia3/aisite/bus_heuristica.htm
Métodos de escalada
Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese momento. Se dividen en dos grupos: Los métodos irrevocables, que no preven la vuelta a un lugar del espacio de estados si el camino resulta inadecuado. Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos que el camino elegido no es el más adecuado.
En este método, en el momento es que se encuentra un estado E que es más favorable que el que se está expandiendo, dicho estado E es devuelto sin generar el resto de estados hijos.
La escalada por la máxima pendiente.
En este caso, se generan todos los hijos de un estado, se calculan sus valores heurísticos y se determina uno de los estados de mejor valor heurístico; se compara dicho valor con el de el estado expandido y si es mejor, se devuelve ese estado como expansión.
Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
Búsqueda avara
Una estrategia simple consiste en reducir al mínimo el costo estimado para lograr una meta. Aunque es posible estimar el costo que implica llegar a una meta desde un estado determinado, no es posible hacerlo con precisión. La función que se utiliza para calcular tales estimados de costo se conoce como función heurística.
A la búsqueda que utiliza una función heurística para escoger qué nodo se expandirá es denominada “búsqueda avara”.
La búsqueda avara y la preferente por profundidad se asemejan por su indicación a utilizar una sola ruta hasta llegar a la meta, pero se atorarán cuando se topen con un callejón sin salida. Esta búsqueda no es óptima y es incompleta.
http://www.angelfire.com/ia3/aisite/bus_heuristica.htm
CARACTERÍSTICAS DE LA BÚSQUEDA HEURISTICA
Ø
Supone la existencia de una función de
evaluación que debe medir la distancia estimada al (a un) objetivo (h(n))
Ø
Esta función de evaluación se utiliza para guiar
el proceso haciendo que en cada momento se seleccione el estado o las
operaciones más prometedores
Ø
No siempre se garantiza encontrar una solución
(de existir ésta)
Ø
No siempre se garantiza encontrar la solución
más próxima (la que se encuentra a una distancia, número de operación menor)
Ø
Existen múltiples algoritmos
¿QUE ES LA BÚSQUEDA HEURISTICA?
Búsqueda Heurística
¿QUE ES LA BÚSQUEDA HEURISTICA?
Los métodos de búsqueda heurísticas (del griego heuriskein, que significa encontrar) están orientados a reducir la cantidad de búsqueda requerida para encontrar una solución. Cuando un problema es presentado como un árbol de búsqueda el enfoque heurístico intenta reducir el tamaño del árbol cortando nodos pocos prometedores. Estos métodos se llaman métodos fuertes porque ellos son más poderosos que los estudiados hasta aquí al incorporar conocimiento heurístico o heurística. Hay una contradicción entre generalidad y potencia en el sentido que los métodos débiles son esencialmente aplicables universalmente mientras que los fuertes son menos universales en su aplicabilidad y el conocimiento o heurística usada en un problema dado puede no ser totalmente aplicable o ser inaplicable en otro dominio o tarea.
Feigenbaum y Feldman definen la heurística como sigue: "Una heurística es una regla para engañar, simplificar o para cualquier otra clase de ardid el cual limita drásticamente la búsqueda de soluciones en grandes espacios de estados". En esencia una heurística es simplemente un conjunto de reglas que evalúan la posibilidad de que una búsqueda va en la dirección correcta. Generalmente los métodos de búsqueda heurísticas se basan en maximizar o minimizar algunos aspectos del problema.
Un ejemplo sencillo de heurística es el siguiente:
Un hombre se encuentra en una extensa llanura y tiene sed, en ese momento ha llegado a una pequeña elevación que es la única en esa región y se sube a ella. Desde la elevación el hombre observa el cuadro siguiente:
NORTE: vegetación verde y movimiento de animales
SUR: vegetación amarilla
ESTE: vegetación amarilla
OESTE: vegetación verde
Evidentemente la vegetación verde es un indicio de que hay humedad, luego es muy probable que exista agua en la superficie o subterránea. El movimiento de animales puede indicar que ellos se dirigen allí a beber, lo cual sugiere que el agua está en la superficie. Esta información le dice al hombre que debe dirigirse al norte, constituye una heurística.
La Heurística no garantiza que siempre se tome la dirección de la búsqueda correcta, por eso este enfoque no es óptimo sino suficientemente bueno. Frecuentemente son mejores los métodos heurísticos que los métodos de búsquedas a ciegas. Las desventajas y limitaciones principales de la heurística son:
La flexibilidad inherente de los métodos heurísticos pueden conducir a errores o a manipulaciones fraudulentas.
Ciertas heurísticas se pueden contradecir al aplicarse al mismo problema, lo cual genera confusión y hacen perder credibilidad a los métodos heurísticos.
Soluciones óptimas no son identificadas. Las mejoras locales determinadas por las heurísticas pueden cortar el camino a soluciones mejores por la falta de una perspectiva global. La brecha entre la solución óptima y una generada por heurística puede ser grande.
http://www.monografias.com/trabajos75/busqueda-heuristica/busqueda-heuristica.shtml#ixzz3bxSlAwbO
Suscribirse a:
Entradas (Atom)