Unidad 2 - Búsqueda y planificacion Flashcards
Búsqueda primero mejor, en qué consiste.
La búsqueda del primero mejor combina las ventajas que presentan tanto la búsqueda primero en anchura como la primero en profundidad. La búsqueda primero en profundidad permite encontrar una solución sin tener que expandirse completamente por todas las ramas. La búsqueda primero en anchura presenta la ventaja de que no queda atrapada en callejones sin salida. Una forma de combinar ambas ventajas consiste en seguir un único camino cada vez, y cambiarlo cuando alguna ruta parezca más prometedora que la que se está siguiendo en ese momento.
Lo normal es que el funcionamiento se parezca a de búsqueda primero en profundidad, pero si no se encuentra una solución, la rama puede ser menos prometedora que otras que se habían ignorado, en cuyo caso se comienza a explorar la nueva rama que ahora es más prometedora. Sin embargo la rama vieja no se olvida, Su último nodo se almacena, ya que la búsqueda puede volver a él si los nuevos nodos no son buenos.
Diferencias entre la búsqueda primero mejor y la escalada.
El procedimiento del primero mejor es muy similar al de escalada por la máxima pendiente, excepto en 2 aspectos. En el método de escalada, al seleccionar un movimiento todos los demás se abandonan y nunca pueden volver a ser considerados. En el método de búsqueda del primero mejor, se sigue seleccionando un movimiento, pero todos los demás se mantienen de forma que pueden visitarse si el camino que se ha seleccionado llega a ser menos prometedor. Además, se selecciona el mejor estado disponible, aun si este estado tiene un valor menor que el del que se estaba explorando. Esto contrasta con método de escalada, donde el proceso se detiene si no encuentra un estado mejor que el actual.
Análisis de medios y fines
El proceso de análisis de medios y fines se centra en la detección de diferencias entre el estado actual y el estado objetivo.
Una vez que se ha aislado una diferencia, debe encontrarse un operador que pueda reducirla. Es posible que tal operador no pueda aplicarse, se crea el sub-problema que consiste en alcanzar un estado en que pueda aplicarse dicho operador. Este tipo de encadenamiento hacia atrás recibe el nombre de realización de sub-objetivos para un operador.
Sin embargo, es posible que el operador no produzca exactamente el estado objetivo que se desea. En este caso, se tiene un segundo sub-problema que consiste en llegar desde ese estado hasta un objetivo. Pero si se ha elegido correctamente la diferencia y el operador es realmente eficaz al reducir la diferencia, estos 2 sub-problemas serán más fáciles de resolver que el problema original.
El análisis de medios y fines puede entonces aplicarse recursivamente. A las diferencias se les asignan niveles de prioridad. Las diferencias de prioridad mayor deben considerarse antes.
Qué es un sistema reactivo
La idea de los sistemas reactivos consiste en evitar planificar totalmente y, en lugar de eso, utilizar la situación observable como pista a la que simplemente reaccionar.
Un sistema reactivo debe tener acceso a algún tipo de base de conocimiento que describa las acciones que deben realizarse bajo ciertas circunstancias. Elige sólo una acción cada vez, no anticipa y selecciona una secuencia completa de acciones. (Ej.: el termostato).
Escalada, Escala Simple y por máxima pendiente. Qué diferencias tienen. Qué problemas tiene la escalada.
- Escalada: Es una variante del de generación y prueba. En este existe realimentación a partir del procedimiento de prueba que se usa para ayudar al generador a decidir por cuál dirección debe moverse en el espacio de búsqueda. En el de generación y prueba original, la función de prueba responde solo un si o un no, por lo tanto se puede ampliar mediante una función heurística que proporcione una estimación de lo cercano que se encuentra un estado al estado objetivo. Se utiliza cuando se dispone de una buena función heurística para evaluar los estados, pero cuando no se dispone de otro tipo de conocimiento provechoso. Su algoritmo sería avanzar de a un paso y valorar. Si no es mejor, volver atrás y buscar otro.
- Escalada Simple: Se evalúa el estado inicial, si también es el estado objetivo, devolverlo y terminar, si nó continuar con el estado inicial como estado actual. Repetir esto hasta que se encuentre una solución o hasta que no queden nuevos operadores que aplicar al estado actual.
La diferencia entre este y el de escalada consiste en el uso de una función de evaluación como una forma de introducir conocimiento específico de la tarea realizada en el proceso de control. Con este algoritmo se hace la pregunta “¿Es un estado mejor que el otro?”
3.Escalada por la máxima pendiente: es una variación de escalada simple que consiste en considerar todos los posibles movimientos a partir del estado actual y elegir el mejor de ellos como el nuevo estado. A diferencia del método básico, donde el primer estado que parece mejor que el actual se selecciona como el estado actual.
Evalúa el estado inicial, si también es el estado objetivo, se devuelve y termina, caso contrario se continúa con el actual.Repetir esto hasta que se encuentre una solución o hasta que una iteración completa no produzca un cambio en el estado actual
Tanto la escalada básica como la de máxima pendiente pueden no encontrar una solución y en cambio encontrar un estado del que no sea posible generar nuevos estados mejores que él. Esto ocurre cuando el programa se topa con un máximo local (estado mejor que todos sus vecinos), una meseta (área en que todos los estados vecinos poseen el mismo valor) o una cresta (área del espacio de búsqueda más alta que las áreas circundantes).
Reducción de problemas
A veces es posible convertir metas difíciles en una o más submetas más fáciles de lograr. Cada submeta, a su vez, puede dividirse aún más finamente en una o más submetas de nivel inferior. De esta manera se reconocen las metas y se las convierte en submetas apropiadas.
La idea clave del método de Reducción de problemas es explorar un árbol de metas.
Los nodos representan metas y las ramas indican la forma en que se pueden lograr las metas, mediante la solución de una o más submetas. Los hijos de cada nodo corresponden a submetas inmediatas; cada padre de nodo corresponde a la supremacía inmediata. El nodo superior que no tiene padre, es la meta raíz.
Verificación de restricciones, todo el proceso y además en qué casos se produce una contradicción.
Es un procedimiento de búsqueda que funciona en un espacio de conjuntos de restricciones. El estado inicial contiene las restricciones que se dan en la descripción del problema. Un estado objetivo es aquel que ha satisfecho las restricciones.
Consta de dos pasos, primero se descubren las restricciones y se propagan tan lejos como sea posible a través del sistema. Entonces si todavía no hay una solución, la búsqueda comienza. Se hace una suposición sobre algo y se añade como una nueva restricción. Entonces la propagación continúa con esta nueva restricción, y así sucesivamente
El primer paso, la propagación, es necesario por el hecho de que normalmente existen dependencias entre las restricciones. La propagación de restricciones también surge debido a la presencia de reglas de inferencia que permiten que se infieran restricciones adicionales a partir de las que se tenían. Este paso termina cuando se detecta una contradicción o cuando no se pueden hacer más cambios basándose en el conocimiento actual que se posea (Una contradicción se produce cuando no hay solución).
Aquí comienza el segundo paso, para ver la forma de fortalecer las restricciones, pueden realizarse algunas hipótesis, una vez hecho se debe comenzar de nuevo la propagación de las restricciones a partir de este nuevo estado. Si se encuentra una solución, se muestra. Si se necesitan más restricciones se hacen y ante una contradicción puede usarse una vuelta-atras para intentarlo con una suposición diferente y comenzar con ella.
Componentes de un sistema de planificación
En los sistemas de resolución de problemas basados en técnicas elementales, era necesario lo siguiente:
A. Elección de las reglas a aplicar, basándose en la mejor información heurística disponible.
B. Aplicación de la regla elegida para calcular el nuevo estado del problema.
C. Detección de una solución
D. Detección de callejones sin salida
E. Identificación de soluciones casi correctas, de modo de emplear técnicas especiales para hacer que sea totalmente correcta.
Ramificación y acotación, explicar. Contar los métodos de búsqueda para juegos, cual usa ramificación y acotación?
Esta técnica comienza generando rutas completas, manteniéndose la ruta más corta encontrada hasta el momento. Deja de explorar una ruta tan pronto como su distancia total, hasta ese momento, sea mayor que la que se ha marcado como la más corta. Usar esta técnica garantiza hallar la ruta más corta. Aunque este algoritmo es más eficiente que el anterior, todavía se necesita un tiempo exponencial. La cantidad de tiempo utilizado en un problema en particular depende del orden en que se exploren las rutas, igualmente es inadecuado para problemas grandes.
Los métodos de búsqueda para juegos son:
1. Juegos de dos jugadores
2. Procedimiento minimax
3.Procedimiento alfa/beta
El procedimiento alfa/beta utiliza el método de ramificación y acotación.
minmax/poda alfa, beta.
- Minimax: Es un procedimiento de búsqueda en profundidad limitada. La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar un conjunto de posiciones sucesivas posibles. Entonces se puede aplicar la función de evaluación estática a esas posiciones y escoger la mejor. Después, puede llevarse hacia atrás ese valor hasta la posición de partida para representar nuestra evaluación de la misma. Nuestra meta es maximizar el valor de la función heurística. Debemos tener en cuenta el hecho de que el movimiento que se realiza a continuación debe ser elegido por el oponente, y por lo tanto, deberá propagarse hacia atrás al siguiente nivel. El objetivo del oponente es minimizar el valor de la función de evaluación.
- Poda alfa/beta: La búsqueda primero en profundidad puede mejorarse usando técnicas de ramificación y acotación, en las que pueden abandonarse rápidamente aquellas soluciones parciales que son claramente peores que otras. Esta estrategia modificada se denomina poda alfa-beta.
Requiere el mantenimiento de dos valores umbral, uno que representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante (que llamaremos alfa) y otro que represente la cota superior del valor que puede asignarse a un nodo minimizante (que llamaremos beta).
En los niveles maximizantes podemos excluir un movimiento tan pronto como quede claro que su valor será menor que el umbral actual, mientras que en los niveles minimizantes la búsqueda termina cuando se descubran valores mayores que el umbral actual.
Método de generación y prueba (Tanto heurístico como exhaustivo)
- Generar una posible solución. Esto significa generar un objetivo particular en el espacio del problema o también, generar un camino a partir de un estado inicial.
- Verificar si realmente el objetivo elegido es una solución comparándolo con el objetivo final o comparando el camino elegido con el conjunto de estados objetivo aceptable.
- Si se ha encontrado la solución, terminar. Si no, volver al paso 1.
Si se generan las posibles soluciones de forma sistemática, si la solución existe, este procedimiento es capaz de encontrarla en algún momento, pero si el espacio problema es grande, ese “algún momento” puede ser demasiado tiempo.
Puede funcionar de forma que genere las soluciones de forma aleatoria, pero esto no garantiza que se pueda encontrar alguna vez la solución.
Puede hacerse en función exhaustiva (probando todas las opciones, mucho más lento) o con función heurística, donde el proceso de búsqueda actúa de forma sistemática, a pesar de que algunos caminos no se consideren porque se cree que a través de ellos no se llega a una solución.
Para problemas sencillos, una generación y prueba exhaustiva es normalmente una técnica razonable. Para problemas complicados, una técnica de generación y prueba no es muy eficiente por sí misma, pero cuando se combina con otras técnicas que restrinjan el espacio de búsqueda, puede llegar a ser muy eficaz.
Búsqueda a ciegas.
Para poder resolver un problema, primero hay que reducirlo a una forma en la que pueda darse una definición precisa. Esto puede lograrse mediante la definición de un espacio de estados del problema, incluyendo los estados iniciales y finales, y de un conjunto de operadores para trasladarse a través del espacio. El problema se reduce entonces a buscar una ruta a través del espacio que una un estado inicial con un estado objetivo. El proceso de resolución del problema puede modelarse como un sistema de producción y entonces se debe elegir la estructura de control apropiada.
Técnicas:
1. Explosión combinatoria
2. Ramificación y acotación
3. Búsqueda primero en anchura
4. Búsqueda primero en profundidad
Definición uso general de heurística.
Con el fin de resolver problemas complicados con eficiencia, con frecuencia es necesario comprometer los requisitos de movilidad y sistematicidad, y construir una estructura de control que no garantice encontrar la mejor respuesta pero que casi siempre encuentre una buena solución. De esta manera surge la idea de heurística. Una heurística es una técnica que aumenta la eficiencia de un proceso de búsqueda, posiblemente sacrificando demandas de completitud. Usando buenas heurísticas se pueden esperar buenas soluciones para problemas difíciles, en un tiempo menor al exponencial.
Técnicas:
1- Generación y prueba
2- Escalada de colinas
3- Búsqueda el primero mejor
4- Reducción de problemas
5- Verificación de restricciones
6- Análisis de medios y fines
Búsqueda primero en anchura y primero en profundidad. Mencionar el método que combina las ventajas de ambos métodos anteriores.
1- Búsqueda Primero en Anchura: Este método evalúa cada nodo del mismo nivel antes de proceder al siguiente nivel más profundo. Garantiza que encontrará una solución, si existe, porque eventualmente degenerará en una búsqueda exhaustiva.
2- Búsqueda Primero en Profundidad: Una búsqueda primero en profundidad explora cada camino posible hacia el objetivo hasta su conclusión antes de intentar otro camino.
Esta estrategia se basa en continuar por una sola rama del árbol hasta encontrar una solución o hasta que se tome la decisión de terminar la búsqueda. Terminar la búsqueda tiene sentido cuando se llega a un callejón sin salida, se produce un estado ya alcanzado o la ruta se alarga más de lo especificado. Si esto ocurre, se produce una vuelta atrás (backtracking). Se revisa el estado más recientemente creado, desde el que sea posible algún movimiento alternativo más y se crea así un nuevo estado. Esta forma de vuelta atrás se denomina vuelta atrás cronológica.
El método que combina ambas ventajas es “El primero mejor”.
Cual es la diferencia entre un sistema reactivo y uno de planificación.
El deliberativo (planificación), es uno donde el plan que resuelve una tarea completa se construye antes de actuar. Los sistemas reactivos consisten en evitar planificar totalmente y utilizar la situación observable como pista a la que simplemente reaccionar.
El sistema reactivo debe tener acceso a alún tipo de base de conocimiento que describa las acciones que deben realizarse bajo ciertas circunstancias. Este tipo es muy diferente a los sistemas de planificación porque elige solo una acción a la vez; no anticipa y selecciona una secuencia completa de acciones antes de realizar una primera acción.
