0

問題

関数のどこかで、返すべきものを返していないことを認識しています。

再帰呼び出しを返していますが、「ずっと」返していないようです

環境

リスト内のすべての組み合わせの深さ優先検索を行っています。条件に合う組み合わせにたどり着いたら、戻りたい。

私は自分のコンビネーションの「状態」を維持しており、あるべき場所に戻っています (私はそう思います)。

私は何を間違っていますか？

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

コンボには、ステープル クラスのリストで構成される「ステープル」と呼ばれるプロパティがあります。最適な数を見つけるために、ディシジョン ツリーのステープルのリストを反復処理したいと考えています。

この場合、リスト内の各ステープル インスタンスの数量全体で最適な数が合計され、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

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と同じように戻ることができます。再帰ロジックは結果を渡し、結果の後でバックトラックします。トップレベルの呼び出し元は、戻り値を取得した場合、実際のソリューションに対して渡したインスタンスを確認する必要があります。TrueFalseTrueFalsecomboTrue

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 に答える