Problema

Soy consciente de que en algún lugar de mi función, no estoy devolviendo algo que debería.

Estoy devolviendo la llamada recursiva, pero parece que no estoy respondiendo "completamente"

Contexto

Estoy haciendo una primera búsqueda en profundidad de cada combinación en una lista. Una vez que alcanzo una combinación que alcanza una condición, quiero regresar.

Estoy manteniendo el "estado" de mi combinación y estoy retrocediendo donde debería estar (creo).

¿Qué estoy haciendo mal?

class Combo:
    def __init__(self, list):
       self.staples = list

Combo tiene una propiedad llamada "grapas", que consiste en una lista de clases de grapas. Quiero iterar sobre la lista de grapas en un árbol de decisión para encontrar un número óptimo.

En este caso, el número óptimo se suma a las cantidades de cada instancia básica en la lista y se almacena / recalcula como una propiedad en la instancia Combo.

def IterateStaples(combo, target):        
  #Exit condition for combo dictionary
  if all(combo.diff[macro] < 2 for macro in combo.diff):    
    return combo;                            

  #iterate through all items in list
  for staple in combo.staples:                                  

    #Increment and calc conditions
    staple.increment()         
    combo.calcTotals()      
    combo.findDiff(target)

    #If exceeds target value, backtrack
    if combo.findConflict(target):                
      staple.decrement()
      combo.calcTotals()                
      combo.findDiff(target)              

    #Redundant exit condition to try and return
    elif all(combo.diff[macro] < 2 for macro in combo.diff):                                  
      return combo                

    #Recursive call
    else:        
      return IterateStaples(combo, target)
      staple.decrement()
      combo.calcTotals()
      combo.findDiff(target)
0
Anthony Chung 13 may. 2016 a las 22:34

3 respuestas

La mejor respuesta

Si entiendo su código correctamente (lo cual es más difícil de lo habitual, ya que no ha mostrado cuáles son la mayoría de los métodos a los que llama combo y staple), esto debería ser lo que desea :

def IterateStaples(combo, target):        
    # base case
    if all(combo.diff[macro] < 2 for macro in combo.diff): # iterate on combo.diff.values()?
        return combo   # returning combo indicates success!

    for staple in combo.staples:
        staple.increment()                 # update state   
        combo.calcTotals()      
        combo.findDiff(target)

        if not combo.findConflict(target):  # skip recursing on invalid states
            result = IterateStaples(combo, target)    # recursive case
            if result is not None:      # if the recursion was successful, return the result
                return result

        staple.decrement()  # otherwise, undo the change to the state (backtrack)
        combo.calcTotals()     # these two lines might not be necessary when backtracking
        combo.findDiff(target) # since other branches will call them after staple.increment()

    return None # if we got to the end of the loop, explicitly return None to signal failure

El return None al final no es estrictamente necesario, ya que None es el valor de retorno predeterminado si no devuelve nada más. Solo creo que es mejor ser explícito al respecto.

Estoy siguiendo su código para devolver combo en caso de éxito (y extenderlo para devolver None en caso de error). Dado que el código muta combo en su lugar, también podría devolver True para el éxito (en el caso base en la parte superior de la función) y False para el fracaso (en la parte inferior de la función, después del final del ciclo). La lógica recursiva transmitiría los resultados de True y retrocedería después de los resultados de False. La persona que llama de nivel superior necesitaría verificar la instancia combo que habían pasado por la solución real si obtuviera un valor de retorno True:

combo = Combo(something)
if IterateStaples(combo, target):
    do_stuff(combo) # success!
1
Blckknght 14 may. 2016 a las 05:53

Pude pasar mi propio caso de prueba incorporando una función auxiliar en lo siguiente:

¿No es esto retroceder? Implementé N-queens con un enfoque similar

def IterateStaples(combo, target):        
  #iterate through all items in list
  bestCombo = []
  def helper(combo):
    for staple in combo.staples:                                      
      #Increment and calc conditions
      staple.increment()         
      combo.calcTotals()      
      combo.findDiff(target)    

      #If exceeds target value, backtrack
      if combo.findConflict(target):                      
        staple.decrement()
        combo.calcTotals()                
        combo.findDiff(target)                                        

      #Redundant exit condition to try and return
      elif all(combo.diff[macro] < 2 for macro in combo.diff):                                          
        bestCombo.append(deepcopy(combo))        
        return                

      #Recursive call
      else:        
        helper(combo)
        staple.decrement()
        combo.calcTotals()
        combo.findDiff(target)

  helper(combo)  

  return bestCombo
0
Anthony Chung 13 may. 2016 a las 20:16

Su primera declaración if dentro del bucle for no devuelve nada. Lo que debería devolver depende de la lógica de su algoritmo:

#If exceeds target value, backtrack
if combo.findConflict(target):                
   staple.decrement()
   combo.calcTotals()                
   combo.findDiff(target)
   return SOMETHING

Además, las últimas 3 líneas nunca se ejecutarán, son después de la declaración return.

1
Amit 13 may. 2016 a las 19:39