0

我在过去的考试中遇到了这样一个问题：

令 X 是一个有序（递增）整数的数组。我们希望将这些整数分组到 k 个连续的子序列中，即 k 路分区。我们希望每组最小化一个质量函数，定义为每组元素与该组平均值之间差异的总和。根据定义，我们需要一种回溯算法，该算法可以修剪非最优解决方案分支并返回最小化总成本的 k 路分区。

但是，这就是我感到困惑的地方：

  • 我为这个问题找到了这个漂亮的解决方案（嗯，几乎是一个完整的解决方案，我只需要完成成本函数）：用于解决分区问题的递归回溯算法。但我想，回溯算法不应该检查每个解决方案的可行性吗？根据我对 Antti 的回答的理解，所有可能性都被计算出来（从最后一个具有最大大小的分区开始，然后从右到左将元素杂耍到其他分区）。
  • 我的另一个疑问与问题的规格有关，不是要求回溯解决方案修剪非最佳分支与要求分支和绑定解决方案相同吗？我可以使用回溯解决方案，当找到不正确的解决方案时回溯，但我认为修剪非最优性太多了。

也就是说，我对 Antti 的 ideia 的 pythonic 实现是这样的：

def get_best_partition(k_partition_index: int, k: int, values, 
                        partitions, best_partition, partitions_errors):
    if (k == len(partitions)):
        error = get_total_heterogeneity(values, partitions)
        partitions_errors.append(error)
        if error <= min(partitions_errors):
            partition_index = 0
            for partition in partitions:
                best_partition[partition_index] = partition
                partition_index += 1
        return
    
    for i in range(k_partition_index, len(values)):
        partitions[k] = i
        get_best_partition(i + 1, k + 1, values, partitions, 
                            best_partition, partitions_errors)

它确实有效（至少在某些边界条件下它确实有效），但我不确定为什么这是回溯，它对我来说确实像是详尽的搜索。我想就是这样。

非常感谢，社区。

4

0 回答 0