1

如果这是具有众所周知的解决方案的知名问题，请原谅我。我一直在寻找，但显然没有成功。

假设我有n 个事件必须在一个区间内发生（例如，[0,1]）。每个事件都与从预定义分布中随机抽取的持续时间相关联。假设间隔远大于所有事件持续时间的总和：有效的时间表总是存在的。[0,1]区间内事件发生的概率不均匀，但只要不重叠，事件就是独立的。

安排这些事件的有效和准确（随机）方式是什么？

这是我当前的伪代码：

lowerBound = min(interval)
上界 = 最大值（间隔）
对于 n in numEvents {
  绘制开始时间
  绘制结束时间
  while ( startTime 小于 lowerBound || endTime 超过 upperBound ) {
    绘制开始时间
    绘制结束时间
  }
  添加事件
  重置 lowerBound 和 upperBound 以定义最大剩余（无事件）间隔
}

我认为，通过选择更大的剩余间隔来安排新事件，我会让事件过度分散——比其他情况下的间隔更大。尽管如此，当事件数量很少时，这似乎非常有效并且可能非常准确。

我正在使用 C++，尽管这可能无关紧要。

如果您知道这种问题的名称，我也非常感谢搜索词。

背景：在这里，准确性对我来说是最重要的。这不是整个程序中耗时的步骤。

4

1 回答 1

2

我只是随机放置每个事件，检查碰撞，如果有碰撞擦干净并重新开始。

你说间隔远大于事件持续时间的总和，所以碰撞会很少，所以这种方法在实践中是相当快的。

你说你想要准确的结果。我不确定这意味着什么，但我猜我会说所有有效的解决方案都应该是同样可能的；该问题中的当前解决方案不满足该要求，但是这个解决方案可以。

于 2013-03-15T23:25:42.407 回答