2.3 Optimizacion Iterativa [Inteligencia Artificial]

¿Qué es la profundización iterativa?

Volvamos a nuestro problema de hacer que nuestro equipo responda a un oponente en dos segundos o menos. Antes, se calculó la profundidad máxima que pensamos que podíamos buscar en el tiempo sin peligro.

Con la profundización iterativa, vamos a hacer algo más simple. Vamos a buscar el nivel 1 y obtener una respuesta para lo que creemos que es el mejor movimiento.


Vamos a mantener esa respuesta en caso de que se nos acabe el tiempo.
Pero vamos a empezar el proceso de nuevo e ir al nivel 2 en esta ocasión.


Si terminamos buscando Nivel 2 antes de que acabe el tiempo, vamos a seguir su mejor movimiento y reiniciar la búsqueda pasando al nivel 3.


Vamos a seguir haciendo este proceso hasta que se nos acabe el tiempo y a continuación, volver a nuestra mejor respuesta.

Entonces se necesitaría hacer lo mismo para determinar la inactividad, por que básicamente la quiescencia es un buen efecto secundario. Sorprendentemente, profundización iterativa es no perder mucho tiempo. Debido a la naturaleza exponencial del problema, la cantidad de tiempo está dominado por el último nivel buscado.

Veamos un caso de profundización iterativa en un árbol con factor de ramificación de 2.
A nivel 0, solo un nodo se busca.
En el nivel 1 tocamos este primer nodo de nuevo y luego miramos a los dos nodos secundarios. Hemos tenido que explorar tres nodos de nivel 1, además de un nodo desde el nivel 0. Por lo tanto, nuestro total de nodos de profundización iterativa, es 4.

En el nivel 2, añadimos cuatro nodos a la parte inferior del árbol. Para agregar estos nodos, estamos buscando en el 3 por encima de ella, así como para un total de 7 para este nivel. Adición de nivel 2 en nuestro recuento actualizado es de 11 nodos de profundización iterativa.

En el nivel 3, que tenía 8 nodos más, examinamos 15 nodos para este nivel en total. Nuestro total de profundización iterativa es ahora de 26.


Saber que cada nivel, la suma total de nodos visitados y revisados por profundización iterativa es en realidad bajo dos veces el número de nodos expandido en este nivel.
Una búsqueda en profundidad limitada al nivel 4 examinaría 31 nodos, pero del total de profundización iterativa seria 57.

La profundidad limitada al nivel 5 sería de 63 nodos y la profundización iterativa seria 120.
Mientras investigaba el árbol puede parecer una pérdida en la práctica. Es un pequeño multiplicador en comparación con el aumento exponencial de buscar cada nivel más profundo.

Con un factor de ramificación de 2, la profundización iterativa se expande menos de dos veces el número de nodos a una profundidad, la búsqueda limitada lo hubiera hecho en el mismo nivel.
Cuando el factor de ramificación es mayor que 2, como en la mayoría de los juegos, a continuación, la redundancia causada por profundización iterativa es aún menos.

Ahora vamos a considerar un árbol con un factor de ramificación de tres.
¿Cuantos nodos son visitados a nivel cero, uno, dos, tres y cuatro?
También el número de nodos del árbol visitados por profundización iterativa.





Intente resolverlo antes de continuar...







Recuerde que cuando el factor de 2, tuvimos 2^d+1-1 nodo en el árbol.
Ahora con el factor de proyecto de tres, tenemos 3^d+1-1 sobre dos nodos del árbol.
Vamos a seguir adelante y generalizar esto.


Para un factor de k, las formulas k^d+1-1 sobre k-1 para el numero de nodos en el árbol.

---