EL ALGORITMO AO 1 HAGAMOS QUE G CONSISTA SOLAMENTE

REC UITR F7002 5 RECOMENDACIÓN UITR F7002 ALGORITMO PARA
10 OPTIMIZACION CAPITULO 5 ALGORITMOS DE APROXIMACIÓN A
2 ALGORITMOS DIAGNÓSTICOS Y TERAPÉUTICOS DISTENSIÓN ABDOMINAL

41 SECCIÓN I ALGORITMO 107 (S I 107) EVALUACIÓN
43 SECCIÓN I ALGORITMO 11 (S I 11) EVALUACIÓN
ALGORITMO – COMPRAR UN CARRO ENTRADA DINERO MARCA ESTILO

El algoritmo AO*

El algoritmo AO*


1. Hagamos que G consista solamente en el nodo que representa el estado inicial. (Llamaremos a este nodo INICIO). Calculemos h'(INICIO).


2. Repetir el siguiente procedimiento hasta que INICIO quede etiquetado como RESUELTO, o hasta que el valor h' de INICIO sea más grande que FUTILIDAD:

  1. Trazar los arcos marcados desde INICIO y seleccionar para expansionar uno de los nodos aun no expandidos, que aparezcan en ese camino. Llamaremos al nodo seleccionado NODO.

  2. Generar los sucesores de NODO. Si no hay ninguno, asignar FUTILIDAD al valor h' de NODO. Esto es equivalente a decir que NODO no es resolvible. Si hay sucesores, entonces, para cada uno (llamado sucesor) que no sea también un antecesor de NODO, hacer lo siguiente:

    1. Añadir SUCESOR al grafo G.

    2. Si SUCESOR es un nodo terminal, etiquetarlo RESUELTO y asignarle un valor h' igual a O.

    3. Si SUCESOR no es un nodo terminal, calcular su valor h'.


3. Propagar la información recién descubierta grafo arriba haciendo lo siguiente:

Sea S un conjunto de nodos que se han marcado RESUELTO o cuyos valores h' se han cambiado, por lo que necesitan propagar sus valores hacia atrás a sus antecesores. Inicializar S al NODO. Repetir el siguiente procedimiento hasta que S esté vacío:

  1. Seleccionemos un nodo de S tal que ninguno de sus descendientes en G forme parte de S. (En otras palabras, debemos estar seguros de que para cada nodo que vayamos a procesar, lo procesamos antes que ninguno de sus antecesores.) Llamaremos a este nodo ACTUAL, y lo quitaremos de S.

  2. Calcular el costo de cada uno de los arcos que emergen de ACTUAL. El coste de cada arco es igual a la suma de los valores h' de cada uno de los nodos al final del arco más el coste del arco mismo. Asignemos al nuevo valor h' de ACTUAL el mínimo de los costes que acabamos de calcular para los arcos que surgen de él.

  3. Marquemos el mejor camino que sale de ACTUAL marcando el arco que tiene el mínimo costo, tal como se calculó en el paso anterior.

  4. Marcar ACTUAL como RESUELTO si todos los nodos conectados a él a través del arco que acabamos de marcar están etiquetados RESUELTO.

  5. Si ACTUAL se ha marcado como RESUELTO o bien el costo de ACTUAL acaba de cambiar, entonces el nuevo estatus debe propagarse hacia el principio del grafo. Por lo tanto debemos añadir a S todos los antecesores de ACTUAL.


Es conveniente remarcar algunos puntos sobre la operación de este algoritmo. En el paso 2.3.5, los antecesores de un nodo cuyo coste se ha alterado se añaden al conjunto de nodos cuyos costos deben también revisarse. Tal como se ha establecido, el algoritmo insertará todos los antecesores del nodo en el conjunto. Esto puede producir la propagación del cambio de coste hacia atrás a través de un gran número de caminos que ya eran conocidos como muy buenos. Por ejemplo, en la figura 3.19 está claro que el camino a través de C siempre será mejor que el camino a través de B, por lo que se desperdicia el trabajo realizado en el camino a través de B. Pero si se revisa el coste de E y no se propaga ese cambio tanto a través de B como a través de C, puede parecer que B

EL ALGORITMO AO 1 HAGAMOS QUE G CONSISTA SOLAMENTE


será mejor. Por ejemplo, si como resultado de expandir el nodo E, actualizamos su coste a 10, entonces el coste de C se actualizará a 11. Si esto es lo único que se hace, entonces, al examinar A, el camino a través de B tendrá un coste de sólo 11 comparado a los 12 para el camino a través de C, y quedará marcado erróneamente como el camino más prometedor. En este ejemplo puede detectarse el error en el siguiente paso, durante el cual se expandirá D. Si su coste cambia y se propaga hacia B, el coste de B deberá recalcularse y se usará el nuevo coste de E. Entonces el nuevo coste de E se propagará hacia A. En ese punto el camino por C será otra vez el mejor. Lo único que ha sucedido es que se ha desperdiciado un poco de tiempo al expandir D. Pero si el nodo cuyo coste ha cambiado está más alejado hacia abajo en el grafo de búsqueda, el error puede no detectarse nunca. Un ejemplo de esto se muestra en la figura 3.20(a). Si el coste de G se revisa tal como se muestra en la figura 3.20(b), y si no se propaga inmediatamente hacia E, entonces nunca se registrará el cambio y se hallará una solución no óptima a través de B.


EL ALGORITMO AO 1 HAGAMOS QUE G CONSISTA SOLAMENTE


Una segunda observación que debemos hacer sobre el algoritmo AO* es que falla al no tener en cuenta ninguna interacción entre submetas. Un ejemplo simple de este fallo se muestra en la figura 3.21. Suponiendo que ambos nodos C y E conducen, en último término, a la solución, el algoritmo AO* proporcionará una solución completa que incluya a ambos. El grafo Y-O establece que para resolver A, deben resolverse ambos C y D. Pero entonces el algoritmo considera la solución de D como un proceso completamente separado de la solución de C. Observando sólo las alternativas desde D, E es el mejor camino. Pero resulta que C es necesario en todos los casos, por lo que sería mejor usarlo también para satisfacer D. Pero puesto que el algoritmo AO* no considera tales interacciones, encontraría un camino no óptimo. En la sección 8.1, se presentan métodos de resolución de problemas que consideran interacciones entre submetas.



ALGORITMO DE AUTO CLASIFICACIÓN PARA PERSONAS CON SÍNTOMAS DE
ALGORITMO DE CÁLCULO DE LA TIR Y DE LA
ALGORITMOS APROXIMADOS PARA EL PROBLEMA DEL 2ÁRBOL GENERADOR DE


Tags: algoritmo ao*, el algoritmo, hagamos, algoritmo, consista, solamente