在x轴上寻找最大数量的非重叠线的算法

Question

在x轴上寻找最大数量的非重叠线的算法

3

我不太确定如何表达这个问题，但我会尽可能具体。想象一个俄罗斯方块屏幕，只有矩形，它们以不同的形状掉落到底部。我想计算最多能放置多少个不重叠的矩形。在计算时，我只关心矩形的长度，或者说是平行于x轴的线段。

因此，基本上我有一个自定义类型，包含起始点和结束点，都是0到100之间的整数。假设我们有一个矩形列表，从1到n。除非第n-1个矩形的结束点小于第n个矩形的起始点，否则rectangle_n.start（除非它是距离原点最近的矩形）必须大于rectangle_(n-1).end，以便它们永远不会重叠。我从一个包含随机数字的文件中读取矩形坐标（两个坐标都是x轴坐标）。

例如，考虑以下矩形类型对象列表：

rectangle_list {start, end} = {{1,2}, {3,5}, {4,7} {9,12}}

我们可以发现第三个物体的起始坐标小于前一个矩形的结束坐标，而前一个矩形的结束坐标是5。因此，在对该列表进行排序时，我需要删除第二个或第三个物体，以避免它们重叠。

我不确定这种问题是否有专门的名称，所以我不知道如何为其命名。我想要一个算法，能够应用于此类对象的列表，并相应地将它们排序。

我已经添加了C ++标签，因为我正在编写C ++代码，但任何语言都适用于该算法。 initial state

final state

- rares.urdea

我认为你需要一个启发式算法来解决这个问题。为什么不先从最小的部分开始呢？ - Josh C.

明确一点，如果您删除第二个或第三个矩形都没有关系，因为您想要最大化的是矩形的数量，而不是总长度的总和。 - Tom

你的意思是：“我们可以观察到第三个对象的起始坐标为4，小于前一个矩形的结束坐标，即5。”吗？ - John

@Tom 是的，就是这样。问题是，我需要根据多个因素来决定删除哪一个，比如：它们中的任何一个是否影响其他矩形的放置？哪一个更长？等等。 - rares.urdea

另外，你可以自由地在方块下落时来回移动它们吗？ - John

@John，它们实际上没有掉落。我只对每个x轴的着陆坐标感兴趣。如果你是这个意思，那么每个起始和结束的坐标都是从一个文件中读取并且固定的。 - rares.urdea

3个回答

3

这个问题的名称是装箱问题，通常被认为是一个难题，但对于少量箱子可以计算得相当好。

这里有一个视频，解释了解决这个问题的常见方法。

编辑：所谓难题，指的是必须采用某种暴力方法。您将不得不评估大量的解决方案并拒绝其中的大多数，因此通常需要一些评估机制。您需要能够比较解决方案，例如“这个方案包含15个面积为4的矩形”比“这个方案包含16个面积为3的矩形”更好。

- Eric

错了，这不是装箱问题，装箱问题是NP完全问题，也不是切割库存问题。如果user172818的答案正确的话，有一个O(n²)的方法。注意，在装箱问题中，物品在容器中没有固定位置。-1 - James Waldby - jwpat7

2

我想不到任何捷径，所以你可能需要按大小顺序枚举幂集并在第一个匹配时停止。

做这件事的直接方法是枚举递减大小的组合。你可以在C++11中这样做:

template <typename I>
std::set<Span> find_largest_non_overlapping_subset(I start, I finish) {
    std::set<Span> result;
    for (size_t n = std::distance(start, finish); n-- && result.empty();) {
        enumerate_combinations(start, finish, n, [&](I begin, I end) {
            if (!has_overlaps(begin, end)) {
                result.insert(begin, end);
                return false;
            }
            return true;
        });
    }
    return result;
}

实现enumerate_combination的任务留给读者自己完成。我假设你已经有了has_overlap。

- Marcelo Cantos

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user172818 · Accepted Answer

你需要解决的基本问题如下。假设我们有n个区间 {[x_1，y_1），[x_2，y_2），...，[x_n，y_n)}，其中 x_1<= x_2 <= ... <= x_n。我们想要找到这些间隔的最大子集，使得子集中任何间隔之间都没有重叠。

朴素的解决方案是动态规划。它保证找到最佳解决方案。让 f(i)，0<= i <= n，表示到区间[x_i,y_i)的最大子集的大小。我们有以下公式：

f(i)=\max_{0<=j<i}{f(j)+d(i,j)}

其中d(i,j)=1当且仅当[x_i,y_i)和[x_j,y_j)没有重叠时取值为1；否则d(i,j)为0。您可以从f(0)=0开始迭代计算f(i)。f(n)给出了最大子集的大小。要获得实际子集，您需要保留一个单独的数组s(i)=\argmax_{0<=j<i}{f(j)+d(i,j)}。然后，您需要回溯以获取“路径”。

这是一个O(n^2)的算法：您需要计算每个f(i)，并且对于每个f(i)，您需要进行 i 个测试。我认为应该有一个O(nlogn)的算法，但我不太确定。

编辑：Lua实现：

function find_max(list)
    local ret, f, b = {}, {}, {}
    f[0], b[0] = 0, 0
    table.sort(list, function(a,b) return a[1]<b[1] end)
    -- dynamic programming
    for i, x in ipairs(list) do 
        local max, max_j = 0, -1
        x = list[i]
        for j = 0, i - 1 do
            local e = j > 0 and list[j][2] or 0
            local score = e <= x[1] and 1 or 0
            if f[j] + score > max then
                max, max_j = f[j] + score, j
            end
        end
        f[i], b[i] = max, max_j
    end
    -- backtrack
    local max, max_i = 0, -1
    for i = 1, #list do
        if f[i] > max then -- don't use >= here
            max, max_i = f[i], i
        end
    end
    local i, ret = max_i, {}
    while true do
        table.insert(ret, list[i])
        i = b[i]
        if i == 0 then break end
    end
    return ret
end

local l = find_max({{1,2}, {4,7}, {3,5}, {8,11}, {9,12}})
for _, x in ipairs(l) do
    print(x[1], x[2])
end