Problema: una meta y su correspondiente conjunto de medios que permitan lograrla.
Formulación de metas.
Formulación de un problema: decidir qué acciones y estados habrán de considerarse.
Buscar la solución.
PROBLEMA ==> BÚSQUEDA ==> SOLUCIÓN
Si el agente conoce el estado en que se encuentra y el resultado producido por una de sus acciones, podrá calcular con exactitud en qué estado se encontrará luego de una determinada secuencia de acciones. El agente será capaz de calcular la secuencia de acciones que le permitirá alcanzar el estado meta. El anterior es el caso más sencillo, denominado problema de un solo estado. Si el mundo no es totalmente accesible, el agente deberá razonar en términos de los conjuntos de estados a los que puede llegar, en vez de pensar en función de estados únicos. Al anterior se lo denomina problema de estado múltiple o problema de contingencia. El agente debe calcular todo un árbol de acciones, en vez de una sola secuencia de ellas. Por lo general, cada una de las ramas del árbol se refiere a una posible contingencia que pudiera surgir. Por ello, al anterior se le denomina problema de contingencia. Muchos de los problemas del mundo real, físico, son problemas de contingencia, puesto que es imposible hacer predicciones exactas.
Un problema es un conjunto información que el agente utiliza para decidir lo que va a hacer. Elementos que configuran la definición de un problema:
El estado inicial, que el agente sabe que allí es en el que se encuentra.
El conjunto de las posibles acciones que el agente puede emprender.
El espacio de estados del problema: el conjunto de todos los estados que pueden alcanzarse a partir del estado inicial mediante cualquier secuencia de acciones. Una ruta del espacio de estados es simplemente cualquier secuencia de acciones que permiten pasar de un estado a otro.
La prueba de meta, es lo que el agente aplica a la descripción de un solo estado para decidir si se trata de un estado meta.
La función costo de ruta es una función mediante la que se asigna un costo a una ruta determinada. En general, este costo es la suma de los costos de cada una de las acciones individuales que se emprendan a lo largo de la ruta.
Solución: la salida producida por un algoritmo de búsqueda se denomina solución, es decir, una ruta que va del estado inicial al estado que satisface la prueba de meta.
Existen por lo menos tres formas de medir la eficiencia de una búsqueda. Primera: ¿permite encontrar una solución? Segunda: ¿es una buena solución (con un bajo costo de ruta)? Tercera: ¿cuál es el costo de búsqueda correspondiente al tiempo y memoria necesarios para encontrar una solución? El costo total de la búsqueda es la suma del costo de la ruta y el costo de búsqueda.
El proceso de la eliminación de detalles de una representación se denomina abstracción. Así como se abstrae en el caso de la descripción del estado, también hay que hacerlo en el caso de las acciones. Para escoger una buena abstracción hay que eliminar todos los detalles que sea posible, siempre y cuando se conserve la validez y se garantice la facilidad para emprender las acciones abstractas. Se quitan detalles innecesarios de la representación para que sea más barato encontrar la solución.
Distribución en la VLSI (Integración a muy alta escala o Very Large Scale Integration)
El diseño de circuitos integrados (CI) es una de las más complejas tareas de diseño de la ingeniería actual. En un CI con VLSI puede haber más de un millón de compuertas; la adecuada posición y conexión de cada una de ellas es determinante para el correcto funcionamiento del circuito. Dos de las tareas más difíciles son la distribución de las celdas y el ruteo de los canales. La distribución del CI deberá ser tal que permita construirlo ocupando un mínimo de área y de longitud de conexiones con el fin de obtener un máximo de velocidad.
Meta: distribuir las celdas y rutear los canales de forma tal que se obtenga el máximo de velocidad. |
Problema: se debe considerar que para obtener el máximo de velocidad se debe ocupar un mínimo de área y de longitud de conexiones en la pastilla. Se deben agrupar los componentes básicos en celdas, cada una de las cuales debe desempeñar una función bien definida y tener una configuración característica (en tamaño y forma), así como también disponer de un cierto número de conexiones para unirse a otra celda. Las celdas no deben encimarse y debe quedar espacio suficiente para conectar los alambres que van de una celda a otra. El ruteo de canales debe determinar una ruta para cada alambre, usando los espacios vacíos entre celdas. |
Búsqueda de la solución: algoritmo de búsqueda por endurecimiento simulado, explicado más adelante. |
Una búsqueda consiste en escoger una opción, haciendo de lado las demás para considerarlas posteriormente en caso de no obtener respuesta alguna mediante la primera, y verificando si ésta es un estado meta. Si no es así, se sigue probando y expandiendo hasta dar con una solución o hasta que no haya más estados que expandir. La elección del estado que se desea expandir primero se realiza a través de una estrategia de búsqueda.
Nodo del árbol de búsqueda |
||||
| Estado | Nodo padre | Operador | Profundidad | Costo de ruta |
| Estado en el espacio de estados al que corresponde el nodo | Nodo del árbol de búsqueda que generó este nodo | Operador que se aplicó para generar el nodo | Cuántos nodos de la ruta hay desde la raíz hasta dicho nodo | Costo de la ruta que va del estado inicial al nodo |
También es necesario representar al grupo de nodos que están en espera de ser expandidos, a los que se conoce como el margen o frontera.
Buena parte de los esfuerzos invertidos en el área de búsqueda han quedado en la determinación de la estrategia de búsqueda adecuada para un problema. Evaluaremos las estrategias en función de los cuatro criterios siguientes:
Completez: ¿La estrategia garantiza encontrar una solución, si es que ésta existe?
Complejidad temporal: ¿Cuánto tiempo se necesitará para encontrar una solución?
Complejidad espacial: ¿Cuánta memoria se necesita para efectuar la búsqueda?
Optimidad: ¿Con esta estrategia se encontrará una solución de la más alta calidad, en caso de que existan varias soluciones?
Aquí se presentan seis estrategias de búsqueda que se denominan genéricamente búsqueda sin contar con información o búsqueda ciega.
En esta sencilla estrategia, primero se expande el nodo raíz, y luego todos los nodos generados por éste; luego sus sucesores, y así sucesivamente. En general, todos los nodos que están en la profundidad d del árbol se expanden antes que los que están en d+1.
El problema que presenta este tipo de búsqueda es, al momento de implementarla en una computadora, el consumo de memoria y no el del tiempo de ejecución, como podríamos haber creído.
Por ejemplo, para concluir una búsqueda de profundidad 6, podríamos hacernos de la paciencia para esperar los 18 minutos que lleva hacer los cálculos, pero no todos dispondríamos de 111 megabytes de memoria. Igualmente, una espera de 31 horas alcanzaría para resolver un problema de profundidad 8, pero harían falta unos 11 gigabytes de memoria. Afortunadamente hay otras estrategias de búsqueda que utilizan menos memoria.En este caso se modifica la búsqueda preferente por amplitud en el sentido de expandir siempre el nodo de menor costo (medido por el costo de ruta).
Mediante este método se puede encontrar la solución más barata, siempre y cuando el coste de la ruta no vaya disminuyendo a medida que avanzamos por la ruta. Esto tiene sentido si se considera como costo de la ruta de un nodo a la suma de los costos de los operadores que configuran la ruta. Si el costo de los operadores nunca es negativo, el costo no irá disminuyendo conforme avanzamos y mediante ésta búsqueda será posible encontrar la ruta más barata sin tener que explorar el árbol en su totalidad.
Aquí expandiremos siempre uno de los nodos que se encuentre en lo más profundo del árbol. Sólo si la búsqueda conduce a un callejón sin salida, se revierte la búsqueda y se expanden los nodos de niveles menos profundos.
En la búsqueda preferente por profundidad el volumen de memoria necesario es bastante modesto. En comparación, para una profundidad de 12 con ésta búsqueda requeriríamos 12 kilobytes en vez de los 111 terabytes para una búsqueda preferente por amplitud. También el tiempo requerido es mucho menor en este caso que en los anteriores.
La desventaja de la búsqueda preferente por profundidad es la posibilidad de que se quede estancada al avanzar por una ruta equivocada. Es por esto que cuando hay árboles de búsqueda con prolongadas o infinitas profundidades máximas hay que evitar el empleo de la búsqueda preferente por profundidad.
En ésta búsqueda se eliminan las dificultades que conlleva la búsqueda preferente por profundidad al imponer un límite a la profundidad máxima de una ruta. De esta forma garantizamos que, de existir, se encontrará la solución; lo que no se garantiza es que la primera solución encontrada sea necesariamente la más breve; la búsqueda limitada por profundidad es completa, pero no óptima. Incluso, de escogerse un límite de profundidad excesivamente pequeño, la búsqueda ni siquiera será completa.
La búsqueda por profundización iterativa es una estrategia que esquiva el tema de la elección del mejor límite de la profundidad probando todos los límites de profundidad posibles. Aquí se combinan las ventajas de las búsquedas preferente por profundidad y preferente por ampitud. Es óptima y completa.
Una búsqueda por profundización iterativa que comience por la profundidad 1 y continúe hasta llegar a la profundidad d expande solo 11% más nodos que una búsqueda preferente por amplitud o por profundidad hasta la profundidad d. Por lo general, este tipo de búsqueda es el método idóneo para aquellos casos donde el espacio de búsqueda es grande y se ignora la profundidad de la solución.
Es una búsqueda simultánea que avanza a partir del estado inicial, retrocede a partir de la meta y se detiene cuando ambas búsquedas se encuentran en algún punto intermedio. En el caso de problemas cuyo factor de ramificación es b en ambas direcciones, la búsqueda bidireccional puede ser muy útil. Se definen los predecesores de un nodo n como todos aquellos nodos cuyo sucesor es n. En algunos problemas el cálculo de los predecesores puede resultar muy difícil. Es necesario contar con una manera eficiente de verificar cada uno de los nodos nuevos para ver si ya están en el árbol de búsqueda de la otra mitad de la búsqueda.
Un problema que satisface restricciones (PSR) es un tipo especial de problema que satisface alguna propiedades estructurales adicionales además de los requisitos básicos de los problemas en general. En el caso de un PSR los estados se definen mediante los valores de un conjunto de variables y la prueba de meta especifica un conjunto de restricciones que los valores deben satisfacer.
