我正在使用递归函数通过完整的 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
