Búsqueda en profundidad iterativa

Una búsqueda en Profundidad Iterativa (BPI) es un algoritmo de búsqueda no informada utilizado para una estrategia de búsqueda en el espacio de estados en la que se realizan sucesivas búsquedas en profundidad limitada incrementando el límite de profundidad en cada iteración hasta alcanzarDado que BPI visita los estados múltiples veces, puede parecer extremadamente costoso, pero no lo es, dado que la mayor parte de los nodos se encuentran en el nivel más profundo del árbol, por lo tanto no tiene mucha importancia que se visiten los niveles superiores varias veces.[1]​ La principal ventaja de BPI en búsquedas en árboles de juegos es que las búsquedas anteriores tienen a mejorar la heurística usada, como heurística asesina o la poda alfa-beta, de forma que se puede obtener una estimación más precisa de la puntuación de varios nodos en la última búsqueda y la búsqueda se completa más rápidamente ya que se hace en un orden mejor.Por ejemplo, la poda alfa-beta es más eficiente si se busca el primer movimiento mejor.Esto permite al algoritmo proporcionar indicaciones sobre el resultado casi inmediatamente, refinándolas segúnCuando se utiliza en un entorno interactivo, como en un programa para jugar al ajedrez, esta facilidad permite al programa jugar en cualquier momento con la mejor solución encontrada hasta el momento en la búsqueda realizada.En una búsqueda en profundidad iterativa, los nodos en el nivel más inferior se expanden una sola vez, los del nivel anterior dos veces y así hasta la raíz del árbol, que se expandeexpande, aproximadamente, un 11% más de nodos que una búsqueda en anchura simple o una búsqueda con profundidad limitada de profundidadEsto significa que la complejidad de la BPI es aúnUna búsqueda en profundidad empezando en A, asumiendo que los lados izquierdos del gráfico se toman antes que los derechos y asumiendo que la búsqueda recuerda los nodos visitados previamente y no los repite (dado que esto es un pequeño grafo), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Realizando la misma búsqueda sin recordar los nodos previamente visitados, el resultado no tendrá fin: A, B, D, F, E, A, B, D, F, E, etc., esto ocurre por el ciclo entre A, B, D, F y E, lo que no permite alcanzar C o G. La búsqueda en profundidad iterativa nos soluciona estos bucles y alcanzará los nodos de los siguientes niveles.(Nótese que aún visita C, pero aparece más tarde.También visita E por un camino distinto, pero vuelve a F dos veces.)Para este grafo, cuanta más profundidad se añade, los ciclos "ABFE" y "AEFB" simplemente se alargan antes de que el algoritmo abandone e intente otra rama.Puede recorrer varias veces al mismo nodo siempre y cuando no sea la solución El siguiente pseudocódigo muestra una BPI implementada en términos de una búsqueda en profundidad limitada recursiva.Una búsqueda en profundidad limitada se puede implementar de forma recursiva como sigue.