我正在寻找一种算法来解决这个问题，而不是代码。我想尝试使用线性规划进行松弛，但也许有更有效的方法来解决这个问题？
问题描述
给定一组带权重的区间，这些区间可以重叠。需要找到最大权重的不相交区间子集。
示例
带权重的区间：
|--3--| |---1-----|
|----2--| |----5----|
答案：8
找到具有最大权重的不相交区间子集
4
- Pawel Zubrycki
6
你是在寻找精确算法还是近似算法？LP松弛通常不能直接给出整数解，但是可以检查是否存在连续1约束矩阵的公式：这样的矩阵自动是完全单峰的，最优基本解将是整数的。 - Ulrich Schwarz
我在《算法书》中看到了类似的东西。http://www.amazon.com/gp/product/0262033844/ref=pd_lpo_k2_dp_sr_2?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262032937&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=06QJDKMCA5ETPXCSZ09S 我并不建议你购买它，只是懒得找其他参考资料。那本书中的算法可能有所不同，但它可能会给你启发。 - Hamish Grubijan
我欠这本书，回家后我会研究它。我正在寻找一个精确的算法。 - Pawel Zubrycki
你的意思是你更喜欢一个精确算法（可能需要指数时间，但在间隔数量较少时可以接受），而不是一个近似算法（即使有许多间隔也可以工作，但答案可能不是最优的）？无论如何，你有多少个间隔？ - ShreevatsaR
不知道，我不知道测试用例。 - Pawel Zubrycki
这个问题是作业吗？你的教授没有告诉你输入的大小吗？ - ShreevatsaR
5个回答
2
如果没有权重，那很容易，你可以通过按它们的结束时间对区间进行排序来使用贪心算法，并在每一步中获取可能的最小结束时间间隔。
但在您的案例中，我认为这是NPC问题（需要考虑一下），但是您可以通过按“权重/长度”对每个间隔进行价值评估，并每次以排序格式获取一个可能的间隔来使用类似的贪心算法。此外，您还可以使用模拟退火，意味着每次您都可以按上述值的概率P（p接近1）获得最佳答案，或者以概率1-P选择另一个间隔。您可以在while循环中执行n次以找到一个好的答案。
- Saeed Amiri
1
你可以使用回溯法来得到精确解。 - Saeed Amiri
2
这是一个想法：
考虑下面的图表：为每个间隔创建一个节点。如果间隔I1和间隔I2不重叠且I1在I2之前，则从节点I1到节点I2添加有向边。请注意，此图形是无环的。每个节点的成本等于相应间隔的长度。
现在，想法是在此图中查找最长路径，可以使用动态规划（例如）在无环图中以多项式时间找到。问题是成本在节点而不是在边缘。这里是一个技巧：将每个节点v分成v'和v''。现在进入v的所有边将进入v'，离开v的所有边将离开v''。然后，从v'到v''添加一条边，其成本为节点的成本，在这种情况下，即间隔的长度。所有其他边的成本都为0。
嗯，如果我没错的话，这个图中的最长路径将对应于具有最大总和的不相交间隔集合。
考虑下面的图表：为每个间隔创建一个节点。如果间隔I1和间隔I2不重叠且I1在I2之前，则从节点I1到节点I2添加有向边。请注意，此图形是无环的。每个节点的成本等于相应间隔的长度。
现在，想法是在此图中查找最长路径，可以使用动态规划（例如）在无环图中以多项式时间找到。问题是成本在节点而不是在边缘。这里是一个技巧：将每个节点v分成v'和v''。现在进入v的所有边将进入v'，离开v的所有边将离开v''。然后，从v'到v''添加一条边，其成本为节点的成本，在这种情况下，即间隔的长度。所有其他边的成本都为0。
嗯，如果我没错的话，这个图中的最长路径将对应于具有最大总和的不相交间隔集合。
- kunigami
2
不错。但是你不能在线性时间内计算DAG的最长路径吗？ - Nate Kohl
是的，我认为你可以在图的大小（节点+边）的线性时间内完成它。不过有一个观察结果：边的数量可能是O(n^2)，其中n是区间的数量。 - kunigami
1
你可以将这个问题表述为一个整数规划问题，二进制变量指示是否选择间隔。目标函数将是变量的加权线性组合。然后，您需要适当的约束来强制在间隔之间进行排他性...... 鉴于“作业”标签，应该足够了。
此外，仅因为一个问题可以被公式化为整数规划（解决这个问题是NP-Hard）并不意味着问题类本身是NP-Hard。所以，正如Ulrich指出的那样，可能存在多项式可解的公式化/算法，例如将问题公式化/解决为线性规划。
- Tryer
1
我有一个精确的O(nlog n) DP算法。由于这是一份作业，所以这是一个提示：
按Saeed建议将区间按右端点位置排序，然后从1开始编号。定义f(i)为仅使用不延伸到区间i右边缘的区间可达到的最高权重。
编辑：提示2：按i递增顺序计算每个f(i)。请记住，每个区间都将存在或不存在。要计算“存在”情况的分数，您需要寻找与区间i兼容的“最右侧”区间，这将需要通过已经计算出的解进行二进制搜索。
这是一个很大的提示，不确定是否可以给出更多提示而不完全解释它 ;)
按Saeed建议将区间按右端点位置排序，然后从1开始编号。定义f(i)为仅使用不延伸到区间i右边缘的区间可达到的最高权重。
编辑：提示2：按i递增顺序计算每个f(i)。请记住，每个区间都将存在或不存在。要计算“存在”情况的分数，您需要寻找与区间i兼容的“最右侧”区间，这将需要通过已经计算出的解进行二进制搜索。
这是一个很大的提示，不确定是否可以给出更多提示而不完全解释它 ;)
- j_random_hacker
7
“Rightmost” 是什么意思？我不确定我理解得对不对。f(i) 是一个集合，其中包含区间数，这些数具有最高的权重并且是不相交的吗？ - Pawel Zubrycki
@Pawel：可能有人在书中提到过，但我是自己想出来的。所谓“最右侧、兼容”，指的是右边缘最大且仍在区间 i 的左边缘或左边缘上的区间。对不起，我的表述不够清晰：f(i) 实际上并不是一组非重叠区间，而只是这样一组集合的权重。因此，我们实际上计算的只是每个候选解的权重；要想找到最优解中的区间，需要像其他 DP 算法一样进行回溯。 - j_random_hacker
现在你能把它拼写出来吗？我用了其他方式完成，但知道应该如何完成会更好。 - Pawel Zubrycki
@Pawel：首先观察如果a > b，则f(a) >= f(b) -- 这是因为在最坏的情况下，我们总是可以选择与f(b)相同的一组区间来计算f(a)（并在右侧留下一些“空间”）。现在，我们想要计算f(i)，而我们已经计算出j < i的所有f(j)。有两种情况：第i个区间将存在或不存在--我们只需要评估两种情况的权重并选择最大值。如果第i个区间不存在，则权重将为f(i-1)（请记住，这必须>=所有j < i-1的f(j)... - j_random_hacker
@j_random_hacker：谢谢。我刚刚结束了学期，所以我会在空闲时间写它 :) - Pawel Zubrycki
显示剩余2条评论
1
- user2329823
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接