0

问题

我知道在我的功能的某个地方，我没有返回我应该返回的东西。

我正在返回递归调用，但似乎我没有返回“一路”

语境

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

我正在保持我的组合的“状态”，并且正在回溯我应该在哪里（我认为）。

我究竟做错了什么？

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

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

在这种情况下，最佳数量是对列表中每个钉书钉实例的数量求和，并作为 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)
4

3 回答 3

1

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

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

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

于 2016-05-13T19:39:37.263 回答
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。如果他们得到返回值，顶级调用者需要检查combo他们为实际解决方案传入的实例：True

combo = Combo(something)
if IterateStaples(combo, target):
    do_stuff(combo) # success!
于 2016-05-14T05:53:52.673 回答
0

通过在以下内容中合并一个辅助函数，我能够通过我自己的测试用例：

这不是回溯吗？我用类似的方法实现了 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
于 2016-05-13T20:16:20.217 回答