1

我需要生成满足以下约束的 n 个随机实数值 P[0], P[1], ..., P[n-1]：

Pmin[0] <= P[0] <= Pmax[0]
Pmin[1] <= P[1] <= Pmax[1]
...
Pmin[n-1] <= P[n-1] <= Pmax[n-1]

P[0] + P[1] + ... + P[n-1] = S

知道如何有效地做到这一点吗？

4

2 回答 2

1

一般来说，如果从给定的范围内随机均匀地选择元素，是不可能解决这个问题的。

示例 1：假设 Pmin[i] = 0 和 Pmax[i] = 1。假设 n = 10 和 S = 100。那么没有解，因为最大可能的和是 10。

示例 2：假设 Pmin[i] = 0 和 Pmax[i] = 1。假设 n = 10 和 S = 10。那么只有一个解决方案：选择 P[i] = 1。

可以编写一个算法，从可能的解决方案集中随机均匀地选择结果序列；这与说 P[i] 均匀分布在 Pmin[i] 和 Pmax[i] 之间完全不同。

基本思想是，在每个阶段，进一步限制你的范围，如下所示：

  1. 范围的开始应该是以下两个量中较大的一个：Pmin[i]，或 S - Smax[i] - P，其中 Smax[i] 是和 Pmax[i+1] + ... + Pmax[n] 和 P 是和 P[0] + ... + P[i]。这可以保证您选择的数字足够大，最终可以工作。
  2. 范围的末端应该是以下两个量中较小的一个：Pmax[i]，或 S - Smin[i] - P，其中 Smin[i] 是和 Pmin[i+1] + ... + Pmin[n] 和 P 和以前一样。这可以保证您选择的数字足够小，最终可以工作。

如果您在选择每个 P[i] 时能够遵守这些规则，那么就有一个解决方案，您会随机找到一个解决方案。否则，没有解决办法。

请注意，要实际随机选择解决方案，最好对索引进行洗牌，执行此算法，然后重新排列序列，使其顺序正确。您可以在 O(n) 中洗牌，执行此算法（此处推荐动态编程，因为您可以自下而上构建解决方案），然后通过“解洗”结果序列来吐出序列。

于 2013-02-07T17:03:47.000 回答
0 
For every i, assign P[i] := Pmin[i]
Compute the sum
If sum>S, then stop (it's impossible)
For every i:
    If P[i]+S-sum <= Pmax[i]
        P[i] = P[i]+S-sum
        Stop (it's done :-)
    sum = sum+Pmax[i]-P[i]
    P[i] = Pmax[i]
    Go for next i
Stop (it's impossible)

哎呀，对不起，你说随机......这不是那么微不足道。让我想想...

运行前面的算法有一个起点。现在计算上下的总保证金。上面的边距是每个 i 的各个边距 Pmax[i]-P[i] 的总和。下面的边距是每个 i 的各个边距 P[i]-Pmin[i] 的总和。

以随机顺序遍历除一个之外的所有元素，每个元素只访问一次。对于他们每一个人：

  • 更新上面的边距和下面的边距，从它们中减去当前元素的贡献。
  • 建立当前值的最小值和最大值，同时考虑：
    • 它们必须在区间 [Pmin[i], Pmax[i]] AND
    • 这些最小值和最大值足够接近 P[i]，因此稍后更改其他元素可以补偿将 P[i] 更改为此最小值或最大值（这就是上下边距所指示的）
    • 将 P[i] 更改为计算间隔 [min, max] 中的随机值并更新总和和边距（我不是 100% 确定应该如何在此处更新边距......）

然后调整剩余元素以适合总和 S。

关于随机顺序的遍历，请参阅Knuth shuffles。

于 2013-02-07T16:42:16.317 回答