如果这是一个众所周知的解决方案的众所周知的问题类别,请原谅我。我一直在寻找,但显然没有成功。
假设我有 n 个事件必须在一个时间间隔内发生(例如,[0,1])。每个事件都与从预定义分布中随机抽取的持续时间相关联。假设间隔远大于所有事件持续时间的总和:有效的时间表总是存在的。 [0,1]区间内事件发生的概率不均匀,但只要不重叠,事件就是独立的。
安排这些事件的有效且准确(随机)的方式是什么?
这是我当前的伪代码:
lowerBound = min(interval) upperBound = max(interval) for n in numEvents { draw startTime draw endTime while ( startTime is less than lowerBound || endTime exceeds upperBound ) { draw startTime draw endTime } add event reset lowerBound and upperBound to define largest remaining (event-free) interval }
我认为,通过选择更大的剩余时间间隔来安排新事件,我会让事件过度分散——比其他情况下的间隔更大。尽管如此,当事件数量较少时,这似乎非常有效并且可能非常准确。
我正在使用 C++,尽管这可能无关紧要。
如果您知道这类问题的名称,我也会非常感谢搜索词。
上下文:准确性对我来说是最重要的。在整个程序中,这不是一个耗时的步骤。
最佳答案
我只是随机放置每个事件,检查是否存在碰撞,如果发生碰撞,请将记录擦干净并重新开始。
你说间隔比事件持续时间的总和大得多,所以碰撞会很少见,所以这种方法在实践中是相当快的。
你说你想要准确的结果。我不确定这意味着什么,但我猜测我会说所有有效的解决方案都应该是同样可能的;问题中的当前解决方案不满足该要求,但这个解决方案满足。
关于c++ - 一个时间区间内n个非重叠事件的随机调度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15443271/