递归回溯-python.不返回值

Question

问题

我意识到，在我的职责范围内，我没有归还我应该归还的东西。

我正在返回递归调用，但似乎没有返回"完全退出"

上下文

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

我正在保持我的组合的"状态"，并且正在回溯我应该在的地方（我认为）。

我做错了什么？

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

Combo有一个名为"staples"的属性，由一系列staple类组成。我想迭代决策树中的主食列表，以找到一个最佳数量。

在这种情况下，最佳数量将在列表中每个装订实例的数量上求和，并作为组合实例上的属性存储/重新计算。

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

如果我正确理解您的代码（这比平时更困难，因为您没有显示您在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是默认的返回值。我只是觉得最好明确一点。

我遵循您的代码，在成功时返回combo（并将其扩展为在失败时返回None）。由于代码在适当的位置对combo进行了变异，您还可以返回True表示成功（在函数顶部的基本情况下），返回False表示失败（在函数底部，循环结束后）。递归逻辑将传递True结果，并在False结果之后回溯。如果得到True返回值：，那么顶级调用方将需要检查他们传递的combo实例以获得实际的解决方案

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

Answer 2

for循环中的第一个if语句不返回任何内容。应该返回什么取决于您的算法逻辑：

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

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

Answer 3

我能够通过在以下内容中加入一个助手函数来通过我自己的测试用例：

这不是在倒退吗？我用类似的方法实现了N皇后

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