• Author / Uploaded
• sonia araujo

Citation preview

Algoritmo 8 puzzle El algoritmo de búsqueda IDA*. Descripción del algoritmo. El método IDA* (Iterative Deepening A*) consiste, como su nombre indica, en un algoritmo de profundización iterativa en el que se hace uso de la información heurística de que se dispone sobre el problema para decidir qué nodo expandir a continuación, y hasta dónde llegar en cada una de las iteraciones del proceso. En este algoritmo, como en cualquier algoritmo de profundización iterativa, cada iteración es una búsqueda "primero en profundidad". En este caso la profundización se basa en la información heurística y terminará no a una determinada profundidad, sino cuando se llegue a un nodo cuyo coste de la función heurística de evaluación f = g + h sea mayor que el actual límite de coste de f. De esta forma en cada iteración se revisan todos los nodos con un coste de f menor o igual que el actual límite de coste. Además de esto se evalúan los nodos del contorno del árbol, que tienen un coste mayor que el actual límite de f, para calcular el límite de f que se utilizará en la siguiente iteración. Este nuevo límite será el valor mínimo de todos los valores de f de los nodos del citado contorno. Todo esto se verá más claro después de analizar el seudocódigo del algoritmo y presentar un ejemplo ilustrativo. Seudocódigo de IDA* En adelante, "coste" representa un tipo de datos (tipicamente enteros o reales) en el que se almacenará el coste de los nodos. Para el problema del 8-puzzle basta con que "coste" sea de tipo entero. función IDA*(problema) responde con una lista que contiene la ruta solución Entradas: problema: Estructura que contiene lo siguiente: estado Inicial : Estado a partir del que se comienza la búsqueda estado Final : Estado o estados objetivo de la búsqueda. entero NumOps : Número de operadores aplicables a los estados. vector de entero CosteOperador : Vector en el que se almacena el coste de los operadores. coste CosteMaximo : Cota superior del coste de la solución. Variables: coste límite-f : En esta variable se almacena el límite del coste f para la iteración actual. nodo raíz : Almacena el primer nodo del árbol. lista solución : Almacena la ruta solución.

//Se crea el nodo raíz. raíz = nuevoNodo(problema.inicial, problema.final) //El primer límite-f es el coste-f del nodo raíz. límite-f = coste-f(raíz) bucle hacer solución, límite-f = Contorno-DFS(raiz, límite-f) si no EsVacia(solución) responde con solución si límite-f ³ CosteMaximo responde con ERROR finbucle función Contorno-DFS(nodoexp, límite-f) responde con lista solución, nuevo coste-f Entradas: nodo nodoexp : el nodo a expandir coste límite-f : límite actual de coste de f Variables: coste siguiente-f : límite de coste-f correspondiente al siguiente contorno. Se inicializa con valor CosteMáximo. // Si el coste de este nodo es mayor que el límite actual, devolvemos su coste. si coste-f(nodoexp) > límite-f responde con nulo, coste-f(nodoexp) // Si es un nodo meta, respondemos con una lista inicializada con el nodo. si EsMeta(nodoexp) responde con lista(nodoexp), límite-f // En otro caso expandimos el nodo. para cada operador op //Si existe un sucesor de nodoexp con el operador op si suc = sucesor(nodoexp, op) //hacemos una llamada recursiva a Contorno-DFS (solución, nueva-f ) = Contorno-DFS(suc, límite-f) // Al retorno de Contorno-DFS, si tenemos solución, añadimos a la lista //el nodo actual. si no EsVacia(solución) InsertarLista(solución, nodoexp) responde con solución, límite-f finsi // Si no hay solución comprobamos el valor de nueva-f, y si es menor // que siguiente-f lo almacenamos como valor provisional de limite-f para // la próxima iteración del algoritmo. siguiente-f = Minimo(siguiente-f, nueva-f) finsi //Si aún quedan operadores por comprobar continuamos iterando (bucle 'para') finpara // Si llegamos hasta aquí es que desde el nodo nodoexp no se llega a una solución // de coste menor o igual que límite-f. Retornamos una lista vacía y el valor provisional // de límite-f para la próxima iteración. responde con nulo, siguiente-f