如何降低解决子集优化问题的时间复杂度?

问题描述 投票:0回答:1

首先,我知道标题非常模糊,所以请让我知道是否有更好的术语来描述我正在寻找的内容。

我有一个由两个不相关的正整数组成的元组 (a, b) 列表。我正在尝试创建另一个基于此的列表,该列表最大化 a 的总和,同时保持高于 b 平均值的阈值。

在我的用例中还有另一个实际限制,导致平均阈值相对于最终列表中的元素数量变得更低,所以我认为我的方法必须基于逐渐从初始集中删除元素,以防万一未达到平均阈值。我不知道这里的确切关系,但可以找到它是否与寻找解决方案相关。

为了最佳地解决这个问题,以下解决方案将有效,但时间复杂度为 O(2^n)。 我正在尝试找到一种更简单的方法来做到这一点。

const exampleQueue = [
  {a: 10, b: 4},
  {a: 7, b: 10},
  {a: 3, b: 6},
  {a: 1, b: 4},
  {a: 1, b: 1},
]
const mappedToA = [10, 7, 3, 1, 1] // does not meet the threshold
const firstAttempt = [10, 7, 3, 1, 0]
const secondAttempt = [10, 7, 3, 0, 1]
const thirdAttempt = [10, 7, 3, 0, 0]
const fourthAttempt = [10, 7, 0, 1, 1]
// ...

改善此问题的一种方法是首先映射到 B,找到需要删除的最小元素量,然后尝试从该开始。 然而在此之后我不知道如何进一步优化这个解决方案或者寻找什么来找到更好的方法

algorithm optimization data-structures subset big-o
1个回答
0
投票

我希望您告诉我们额外的限制。如果附加约束很小,则可以在“构建”版本中使用,该版本应该更有效。但我可以让它发挥作用。

我将使用的关键想法是:

  1. 动态规划。增量构建数据结构以避免重复重新计算。这将许多问题(包括子集和之类的问题)从指数问题转变为伪多项式问题。在实践中,这通常是可行的。
  2. 最佳边缘。我们不需要保留所有的可能性。只是那些可能导致某种最佳权衡的因素。
  3. 链接列表。很少有人意识到这一点,但动态编程可以有效地构建链表数据结构,从而提取最佳解决方案。关键是当你回溯选择时,两个不同的链表可以合并。因此,保留当前所有最佳可能性的历史比看起来便宜得多。

让我们的课程来跟踪当前的解决方案状态。

class SolutionState:
    def __init__ (self, tuples=None, prev=None, delete_at=None, threshold=None):
        if prev is None:
            # Base object.
            # Sort values by b increasing, then a decreasing.
            self.tuples = sorted(tuples, key=lambda t: (t[1], -t[0]))
            self.a = sum(t[0] for t in tuples)
            self.b = sum(t[1] for t in tuples)
            self.prev = None
            self.delete_at = delete_at
            self.deleted = 0
            self.threshold = threshold
        else:
            # Links back to previous solutions.
            self.tuples = prev.tuples # Cheap shallow copy!
            t = self.tuples[delete_at]
            self.a = prev.a - t[0]
            self.b = prev.b - t[1]
            self.prev = prev
            self.delete_at = delete_at
            self.deleted = prev.deleted + 1
            if threshold is None:
                self.threshold = prev.threshold
            else:
                self.threshold = threshold

    def solution (self):
        current = self
        reversed_answer = []
        i = len(self.tuples)
        while 0 < i:
            i -= 1
            if current.delete_at is None:
                reversed_answer.append(self.tuples[i])
            elif current.delete_at == i:
                current = current.prev
            else:
                reversed_answer.append(self.tuples[i])
        return list(reversed(reversed_answer))


    def score (self):
        n = len(self.tuples) - self.deleted
        if n == 0:
            # Guarantee valid.
            return self.threshold + 1
        else:
            return self.b / n

    def is_valid (self):
        return self.threshold < self.score()

如您所见,我们只是将解决方案状态记录为先前解决方案状态的链接列表,每次删除一个,直到我们到达我们保留的基本状态。我们总是知道

a
的总和,
b
的总和,以及我们有多少个删除。

我们还可以找出所表示的精确解。但请注意,链表将是从最后一个删除到第一个删除,因此我们从末尾到开头构建答案,然后反转它。这是一个可能令人困惑的技术细节。

我还根据您给我们的规则添加了

score
is_valid

现在让我们谈谈我们的最佳边缘。假设我们位于第

i
个元组。假设我们有一个潜力
SolutionState
。假设此时还有另一个
SolutionState
具有相同的删除次数,并且
a
b
至少同样好。那么这个部分解就无法产生更好的最终有效解。因为无论从这个中保留或删除什么,都要对那个做同样的事情。如果这变得有效,那也是如此。有一个与此相同或更好的
a

因此,在每个

i
,对于每个删除次数
d
,我们都有一个最佳边缘。我们可以通过严格减少
a
和严格增加
b
来存储它。因此,我们可以将当前的可能性集存储在如下所示的数据结构中:

by number of deletions d
   list of SolutionStates, sorted by a descending, and b ascending

现在我们如何处理从

i
i+1
的移动?对于每个
d
,我们都有一个之前带有
d
删除的最佳边缘,以及另一个带有
d-1
删除的最佳边缘。我们通过从第二个列表中删除当前元素来创建可能位于最佳边缘的第二个列表。然后我们合并两个列表并保留新的最佳边缘。

现在有一个好技巧。如果我们采用 descending

d
,那么我们就可以就地更新这个数据结构。因为我们更新后就不再需要第
d
边缘了。

代码如下。

def find_optimal (threshold, tuples):
    base = SolutionState(tuples=tuples)
    base.threshold = threshold
    if base.is_valid():
        # Don't think too hard, deleting elements reduces a, so this is best.
        return base.solution()
    else:
        optimal = [[base]]
        best = None
        for i in range(len(tuples)):
            d = len(optimal)
            optimal.append([]) # Add blank optimal fringe.
            while 0 < d:
                fringe_keep = optimal[d]
                fringe_delete = [SolutionState(prev=ss, delete_at=i)
                        for ss in optimal[d-1]]

                # Did we find possible final solutions?
                while 0 < len(fringe_delete) and fringe_delete[-1].is_valid():
                    # Any further deletion reduces a
                    ss = fringe_delete.pop()
                    # Is this an improvement?
                    if best is None or best.a < ss.a:
                        best = ss

                # Merge what's left
                fringe_merge = []
                j = 0
                k = 0
                while j < len(fringe_keep) and k < len(fringe_delete):
                    # Would fringe_delete[k] come after?
                    if fringe_keep[j].b <= fringe_delete[k].b:
                        # Is fringe_keep[j] in the fringe?
                        if fringe_delete[k].a < fringe_keep[j].a:
                            fringe_merge.append(fringe_keep[j])
                        j += 1
                    else:
                        # Check if fringe_delete[k] is kept.
                        if fringe_keep[j].a < fringe_delete[k].a:
                            fringe_merge.append(fringe_delete[k])
                        k += 1

                # Keep remainder of whatever is left.
                while j < len(fringe_keep):
                    fringe_merge.append(fringe_keep[j])
                    j += 1
                while k < len(fringe_delete):
                    fringe_merge.append(fringe_delete[k])
                    k += 1

                # Replace and move down.
                optimal[d] = fringe_merge
                d -= 1

            # We might have empty fringes at top? Small optimization.
            while 0 < len(optimal) and 0 == len(optimal[-1]):
                optimal.pop()

        # If nothing else, delete everything was valid.
        return best.solution()

最后,这是一些基于您的示例的测试代码。

tuples = [(10, 4), (7, 10), (3, 6), (1, 4), (1, 1)]
for threshold in range(11):
    print(i, find_optimal(threshold, tuples))

如果你有

n
元组,并且
a
的总和是
A
,那么这将使用最多空间和时间
O(n*n*A)
找到答案。它通常会使用比这少得多的空间。而且时间常数往往会相当好。

© www.soinside.com 2019 - 2024. All rights reserved.