Skip to main content
 首页 » 编程设计

python之为 Python 中的递归函数重置装饰器

2025年05月04日13zhoujg

我正在使用递归函数通过完整的 KK 算法解决分区问题。

我的算法搜索一棵可能的分区树。我希望通过停止特定的分支来修剪那棵树。我的“修剪器”想要跟踪最小结果(实际上是到目前为止找到的两个子集之和之间的最小差值)。

我的代码是这样的形式:

def prune(branch): 
 
    def pruner(list_): 
         # If only single element in list, reached end of branch 
         if len(list_) == 1: 
             return list_[0] 
 
         # ... pruning code here ...  
         # Decision to prune depends on pruner.min 
 
         # If didn't prune, calculate as usual 
         # tracking minimum 
         min_branch = branch(list_) 
         pruner.min = min(pruner.min, min_branch) 
         return min_branch 
 
     pruner.__name__ = branch.__name__ 
     pruner.min = float("inf") 
     return pruner 
 
 
 @prune 
 def branch(list_): 
     # ... code to make two new branches here ... 
     return min(branch(list_1), branch(list_2)) 

对于 branch 的单个调用它工作得很好 - pruner.min 在我的装饰器的开头设置了一次 - 并且 branch 返回正确答案。

问题是如果我连续使用该函数两次或更多次。在那种情况下,pruner.min 不会在每次调用后重置,导致我决定修剪分支时出现问题。

我如何(优雅地)让它为每次初始(即非递归)调用我的 branch 函数重置 pruner.min = float("inf")?我唯一能想到的是添加一个 first 关键字参数,def branch(list_, first=True),我将其设置为 False用于 branch 函数内的递归调用。我的装饰者可以看看这个论点。这是最好的方法吗?

为了完整起见,这里是一个可运行的示例,它会产生正确的答案。欢迎任何更一般性的评论。

import copy 
 
def prune(CKK_branch): 
    def pruner(list_): 
 
        internal_list = copy.deepcopy(list_) 
 
        # Check whether end of branch or whether optimal solution achieved 
        if pruner.min == 0.: 
            return pruner.min 
        elif len(internal_list) == 1: 
            return list_[0] 
 
        # Sort branch 
        internal_list.sort(reverse=True) 
 
        # Prune branch 
        if pruner.min < internal_list[0] - sum(internal_list[1:]): 
            return internal_list[0] 
 
        # Find minimum in branch and track minimum of all branches 
        min_branch = CKK_branch(internal_list) 
        pruner.min = min(pruner.min, min_branch) 
 
        return min_branch 
 
    pruner.__name__ = CKK_branch.__name__ 
    pruner.min = float("inf") 
    return pruner 
 
 
@prune 
def CKK(list_): 
    internal_list = copy.deepcopy(list_) 
    # Replace maximum two numbers by their difference and their sum in two 
    # branches 
    diff = internal_list[0] - internal_list[1] 
    sum_ = internal_list[0] + internal_list[1] 
    sum_tree = copy.deepcopy(internal_list) 
    diff_tree = copy.deepcopy(internal_list) 
    del sum_tree[0:2] 
    del diff_tree[0:2] 
    sum_tree.append(sum_) 
    diff_tree.append(diff) 
 
    return min(CKK(diff_tree), CKK(sum_tree))  
 
example_list_1 = [1.4, 
                  10.1, 
                  19.55, 
                  11.71, 
                  51.7, 
                  122.1 
                  ] 
example_list_2 = [10, 
                  5, 
                  1, 
                  1 
                  ]    
print CKK(example_list_1) 
print CKK(example_list_2) 
print CKK(example_list_1) 
# 27.64  # Correct (122.1) - (1.4, ...) 
# 3  # Correct (10) - (5, 1, 1) 
# 122.1  # Something went wrong 

请您参考如下方法:

您可以将标志设置为 None 并在 CKK 中传递任何值,就像您使用默认 arg 一样:

import copy 
 
def prune(CKK_branch): 
    def pruner(list_, flag=None): 
        internal_list = copy.deepcopy(list_) 
        if flag is None: 
            pruner.min = float("inf") 
        # Check whether end of branch or whether optimal solution achieved 
        if pruner.min == 0.: 
            return pruner.min 
        elif len(internal_list) == 1: 
            return list_[0] 
        # Sort branch 
        internal_list.sort(reverse=True)     
        # Prune branch 
        if pruner.min < internal_list[0] - sum(internal_list[1:]): 
            return internal_list[0]   
        # Find minimum in branch and track minimum of all branches 
        min_branch = CKK_branch(internal_list) 
        pruner.min = min(pruner.min, min_branch) 
        return min_branch 
    pruner.__name__ = CKK_branch.__name__ 
    return pruner 
 
 
@prune 
def CKK(list_): 
    internal_list = copy.deepcopy(list_) 
    # Replace maximum two numbers by their difference and their sum in two 
    # branches 
    diff = internal_list[0] - internal_list[1] 
    sum_ = internal_list[0] + internal_list[1] 
    sum_tree = copy.deepcopy(internal_list) 
    diff_tree = copy.deepcopy(internal_list) 
    del sum_tree[0:2] 
    del diff_tree[0:2] 
    sum_tree.append(sum_) 
    diff_tree.append(diff) 
    return min(CKK(diff_tree,True), CKK(sum_tree,True)) 

每次调用 min(CKK(diff_tree,True), CKK(sum_tree,True)) 时,您都会将最小值重置为 inf。

In [26]:  CKK(example_list_1) 
Out[26]: 27.639999999999993 
 
In [27]:  CKK(example_list_2) 
Out[27]: 3 
 
In [28]:  CKK(example_list_1) 
Out[28]: 27.639999999999993