递归回溯 - python。不返回值

Question

问题

我知道在我的职能中的某个地方，我没有return做我应该做的事情。

我正在 return 进行递归调用，但似乎我没有 return 进行 "all the way out"

上下文

我正在对列表中的每个组合进行深度优先搜索。一旦我达到一个达到条件的组合，我想 return.

我正在维护我的组合 "state" 并且正在回溯我应该在的地方（我认为）。

我做错了什么？

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

Combo 有一个名为 "staples" 的属性，由主食列表类组成。我想遍历决策树中的订书钉列表以找到最佳数量。

在这种情况下，最佳数量是对列表中每个主食实例的数量求和，stored/recalculated 作为 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)

Answer 1

您在 for 循环中的第一个 if 语句没有 return 任何内容。应该 return 取决于您的算法逻辑：

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

此外，最后 3 行永远不会执行，它们是在 return 语句之后。

Answer 2

我能够通过在下面合并一个辅助函数来通过我自己的测试用例：

这不是回溯吗？我用类似的方法实现了 N-queens

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

Answer 3

如果我正确理解您的代码（这比平时更难，因为您没有显示您在 combo 和 staple 上调用的大多数方法是什么），这应该是你想要的：

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

末尾的 return None 不是绝对必要的，因为 None 是默认的 return 值，如果你不 return 任何其他东西。我只是觉得最好明确一点。

我正在按照您在 returning combo 中的代码成功（并将其扩展为 returning None 失败）。由于代码在适当的位置改变了 combo，您也可以 return True 表示成功（在函数顶部的基本情况下）和 False 表示失败（在函数的底部，在循环结束之后）。递归逻辑将传递 True 个结果，并在 False 个结果之后回溯。如果顶级调用者获得 True return 值，则他们需要检查他们传入的 combo 实例以获得实际解决方案：

combo = Combo(something)
if IterateStaples(combo, target):
    do_stuff(combo) # success!

递归回溯 - python。不返回值

recursive backtracking - python. not returning value

python

recursion

backtracking

recursive-backtracking