algorithm - 如何执行最小拆分以满足特殊的集合排序？

Question

我正在尝试创建一个算法来解决以下问题:

输入是一个未排序的集合列表，其中包含整数对(键，值)。每对中的第一个在集合中是正数且是唯一的。
我想找到一种算法来拆分输入集，以便可以对集合进行排序，使得对于每个键，值在集合顺序中是不递减的。

有一个简单的解决方案是将集合拆分为每个单独的值并对它们进行排序，我想要在拆分的集合数量方面更有效的方法。

您是否遇到过任何类似的问题和/或可以建议的技术？ 最优(最小分割数)解决方案听起来是否可能在多项式时间内实现？

---

编辑:在示例中，“<=”运算符表示对集合作为一个整体的约束，其中每个键值 (100、101、102) 的对应值等于或大于先前集合中的值 (或从集合中省略)。即使用输出集中的顺序提取每个键的值给出:

• 键 100 {0, 1}
• 键 101 {2, 3}
• 键 102 {10, 15}

Answer 1

A*

我建议使用 A*以找到最佳解决方案。从左到右逐步构建拆分集的顺序，最大限度地减少实现此目标所需的集数。

A* 根据对总成本的一些启发式 估计访问状态。我建议 状态 由我们目前拥有的订单中已包含的所有对的总和来描述。如果每个键的所有值都不同，那么您可以通过简单地存储每个键的最后一个值来相当简洁地表示此信息。否则你将不得不以某种方式处理相等的值，这样你就知道哪些已经被包含，哪些没有。对于每个状态，您都会维护导致它的最佳顺序的某种表示，但是在状态保持不变的情况下，它可能会不断更新。

启发式 应该是对从开始到当前状态到目标的路径总成本的估计。它可以太低，但绝不能太高。在我们的例子中，启发式应该计算到目前为止订单中包含的(可能拆分的)集合的数量，并添加仍在等待插入的(未拆分的)集合的数量。由于剩余的集合可能需要拆分，这可能太低了，但由于您的集合永远不会少于仍在等待插入的集合，因此这是一种合适的启发式方法。

现在您有了一些状态优先级队列，按此启发式的值排序。您从中提取最少的项目，并且知道从队列中提取状态的那一刻，到达该状态的成本不能再减少，因此到达该状态的路径是最优的。现在你检查从中可以达到哪些其他状态:在 split 集的顺序中，哪些其他对可以是下一个？对于每个具有准备好包含的对的剩余集合，您创建一个新的后续状态，从集合中获取所有准备好的对。到目前为止，成本增加了一个。如果你设法拿走一整套，没有 split ，那么剩余成本的估计值会减少一个。

对于这个新状态，您检查它是否已经存在于您的优先级队列中。如果是，并且它之前的成本高于刚刚计算的成本，那么你更新它的成本，以及通向它的最优路径。确保优先键相应地更改其位置(“减少键”)。如果该状态之前不在队列中，则将其添加到队列中。

迪杰斯特拉

想想看，这与运行 Dijkstra's algorithm 是一样的以拆分次数作为成本。由于每条边的成本为零或成本为一，因此您可以更轻松地实现这一点，根本不需要任何优先级队列。相反，您可以使用两个集合，称为 S₀ 和 S₁，其中来自 S₀ 的所有元素都需要相同数量的拆分，而来自 S₁ 的所有元素都需要再拆分一次。用伪代码粗略勾画:

S₀ = ∅ (empty set)
S₁ = ∅
add initial state (no pairs added yet, all sets remain to be added) to S₀
while True
    while (S₀ ≠ ∅)
        x = take and remove any element from zero
        if x is the target state (all pairs included in the order) then
            return the path information associated with it
        for (r: those sets which remain to be added in state x)
            if we can take r as a whole then
                let y be the state obtained by taking r as the next set in the order
                if y is in S₁, remove it
                add y to S₀
            else if we can add only some elements from r then
                let y bet the state obtained by taking as many elements from r as possible
                if y is not in S₀, add it to S₁
    S₀ = S₁
    S₁ = ∅