complejidad de espacio de DFS de profundización iterativa

7

Leemos en Wikipedia > Profundización iterativa: búsqueda en profundidad que

  

La complejidad del espacio de IDDFS es O (bd), donde b es el factor de bifurcación yd es la profundidad del objetivo más superficial.

Wikipedia también proporciona un pseudocódigo decente para IDDFS; Lo pitonicé:

def IDDFS(root, goal):
  depth = 0
  solution = None
  while not solution:
    solution = DLS(root, goal, depth)
    depth = depth + 1
  return solution

def DLS(node, goal, depth):
  print("DLS: node=%d, goal=%d, depth=%d" % (node, goal, depth))
  if depth >= 0:
    if node == goal:
      return node

    for child in expand(node):
      s = DLS(child, goal, depth-1)
      if s:
        return s

  return None

Mi pregunta es, ¿cómo incluye la complejidad del espacio el factor de ramificación? ¿Asume eso que expand(node) ocupa O(b) espacio? ¿Qué sucede si expand usa un generador que solo ocupa espacio constante? En ese caso, ¿la complejidad del espacio seguiría siendo una función del factor de ramificación? ¿Hay situaciones en las que incluso es posible que expand sea un generador de espacio constante?

    
pregunta Dan Burton 10.09.2011 - 20:56

2 respuestas

5

Tienes razón. Wikipedia está mal! ¿Alguien tiene el libro al que se hace referencia en Wikipedia para averiguar qué quiere decir (tal vez estén hablando de algún tipo de optimización)?

Consulte enlace y enlace

    
respondido por el blueberryfields 15.09.2011 - 23:42
0

Estoy estudiando esto mientras hablamos, así que déjame intentar responder a esta pregunta (muy tarde, lo sé) con la esperanza de entender más a IDDFS.

El costo O (bd) se deriva de una implementación que usa una cola para almacenar nodos no explorados, en lugar de recursión. Si lo piensa de esa manera, entonces puede imaginar que expandimos el nodo raíz y agregamos b hijos a la cola (que se expandirá más adelante), luego seleccionamos un hijo (nodos b-1 que quedan en la cola), expandimos y agregue sus b hijos (b + (b-1) nodos en la cola), y repita este proceso hasta que alcancemos el nodo objetivo en la profundidad d. En este punto, hemos ampliado d nodos, ¿sí? Y cada nodo que conduce al nodo objetivo ha contribuido con nodos b-1 a la cola. Por lo tanto, tenemos O ((d-1) (b-1)) = O (bd).

Volviendo a su implementación, sí, creo que tiene razón sobre el término O (b) que está contenido en la función expandir, ya que expand devolverá b children y expand se llamará d-1 veces. Si expand usa un generador que ocupa espacio constante, seguro, creo que reduciría el costo a O (d), pero no veo cómo expandir podría hacer otra cosa que escalar con el tamaño de b.

    
respondido por el user1340033 07.10.2014 - 23:53

Lea otras preguntas en las etiquetas