Inteligencia artificial by unknow

autor:unknow
La lengua: spa
Format: epub
Tags: Ensayo, Ciencias naturales
editor: ePubLibre
publicado: 2016-12-31T16:00:00+00:00

Nuevas estrategias de búsqueda

A pesar de las fuertes limitaciones creadas por la explosión combinatoria, la comunidad de IA ha seguido mejorando los métodos de búsqueda para poder resolver problemas de mayor tamaño. En este sentido, mencionamos una serie de ideas que han surgido en los últimos 30 años y han demostrado su utilidad en IA. Dividimos la sección en dos partes dedicadas a búsqueda sistemática y búsqueda local.

La búsqueda sistemática considera las estrategias que se basan en una enumeración sistemática del espacio de estados; produce algoritmos completos que obtienen soluciones óptimas. El ejemplo clásico es el algoritmo)A*[18]. Un esquema diferente pero aplicable a problemas con ramas no infinitas es ramificación y poda. Trabaja con cotas inferiores y superiores del coste de una solución y realiza poda cuando estas cotas se alcanzan.

Dentro del esquema de búsqueda de A*, se ha mejorado la calidad de las heurísticas admisibles con las denominadas bases de datos de patrones. Se trata de bases de datos que almacenan buenas estimaciones (en el límite exactas) de la heurística para configuraciones parciales de los estados. Ello mejora mucho el rendimiento de A*. Estas bases de datos se calculan en una fase de preproceso, fuera de la búsqueda propiamente dicha. Esta idea se aplica a problemas que se han de resolver de forma repetida, como juegos o puzzles, de forma que se amortiza el esfuerzo de calcularla en muchas búsquedas. Otra idea que mejora la efectividad de A* es la búsqueda frontera. Es un ingenioso método para no guardar la lista de nodos ya expandidos por A* que, en la práctica, llega a doblar la capacidad de memoria del algoritmo en los problemas que resuelve.

Dado el alto consumo de memoria del A*, se han desarrollado otros algoritmos que también alcanzan soluciones óptimas con un consumo lineal de memoria. Uno de ellos, denominado de profundización iterativa, realiza búsquedas en profundidad con profundidad acotada que se incrementa en cada iteración (la primera vez que se resolvió el cubo de Rubik por ordenador fue utilizando este algoritmo). Un esquema diferente pero aplicable a problemas con ramas no infinitas es ramificación y poda. Trabaja con cotas inferiores y superiores del coste de una solución y realiza poda cuando estas cotas se alcanzan.

Una visión alternativa es la búsqueda con discrepancias. Consideramos un problema donde las soluciones están en un determinado nivel en el árbol, que se recorre con un esquema en profundidad. En este escenario, el papel de la heurística es disponer los nodos más prometedores a la izquierda (el recorrido del árbol es de izquierda a derecha y en cuanto se encuentra una solución, el algoritmo termina). Este nuevo esquema de búsqueda sugiere visitar las hojas del árbol por número de discrepancias creciente, en donde una discrepancia es no seguir la heurística en un nodo.

Todas estas aproximaciones se basan en el supuesto de que primero se calcula la solución y después esta se ejecuta, sin que ello pueda invalidar la solución. Sin embargo, en entornos no controlados, la ejecución de una solución puede

descargar

Descargo de responsabilidad:
Este sitio no almacena ningún archivo en su servidor. Solo indexamos y enlazamos.                                                  Contenido proporcionado por otros sitios. Póngase en contacto con los proveedores de contenido para eliminar el contenido de derechos de autor, si corresponde, y envíenos un correo electrónico. Inmediatamente eliminaremos los enlaces o contenidos relevantes.