2

在传统的加权区间调度问题中，我们有一个{i_1, ..., i_n}带有权重的区间列表w_j。这里给出了一种求解加权区间调度问题的算法，它是一个基本的动态规划问题。但是，如果在调度中，选定间隔的权重取决于它之前的间隔的权重（反过来，权重取决于顺序），会发生什么？一个例子是w_j' = w_j'*(w_(j-1)' + 1)，已准备好的变量是内在权重，而未准备好的权重是考虑到订单的“实际”权重，即您实际用于目标函数的权重。这个问题是NP难的吗？听起来确实如此。

编辑：为了使这更容易（也更现实），让我们假设离散的单位时间。

4

1 回答 1

0

好吧，我想通了。算法是（如果我错了，请纠正我）：

for t in times:
    if is_first(t):
        best_candidate = None
    else:
        best_candidate = best(t - 1)

    for interval in intervals if interval.end_time is t:
        value_i = f(best(interval.start_time) + interval)
        value_candidate = f(best_candidate)
        if value_i > value_candidate:
            best_candidate = best(interval.start_time) + interval

    best(t) = best_candidate

return best(times[-1])

其中集合times, intervals是间隔的潜在时间停止和间隔本身，并且f是目标函数。

迭代之间的常数是：随着时间的推移迭代t完成后，best(t)以 结束的最佳调度t。请注意，由于初始化步骤，best(t) == best(t - 1)是可能的。另请注意，正如我的评论中那样，这仅在f单调增加时才有效，因为f它意味着根据之前的间隔应用于每个单独的间隔。我以这里的方式使用它作为速记。

于 2013-08-15T01:05:31.820 回答