0

当我有一个带有权重和随机生成器的图时，如何选择一些更理想的边？我有一个 x 权重的约束，我需要一个包含 x 权重的公式，让我选择下一条边，依此类推。例如，我有 4 个边，重量为 5、10、15、20。如何使用随机生成器使重量为 5 的边缘更理想，而且当我已经选择边缘 5 时，我不需要选择重量为 20 的边缘，因为它超出了我的约束。

4

2 回答 2

2

通过定义选择一个特定边的概率为：

  P(select_this_edge) = (x - Weight_of_this_edge) / x

这将使权重较低的边更有可能被选择，而权重大于“约束”x 的边则无法选择。

假设 RNG（随机数生成器）产生介于 0 和 1 之间的值，决定是否应选择给定边的过程是绘制一个随机数并查看它是否小于或等于公式中计算的概率。

根据您的具体需求，您可以稍微更改公式，例如通过引入一个小因素来阻止系统选择权重为 0 的边缘（通过引入不会被选择的剩余机会），反之亦然防止永远不会选择高于“约束”x 边缘值的边缘。

现在......上面讨论了分配概率以决定是否应该选择给定边缘的方式。如果程序逻辑确实有一种选择单个边的方法并且简单地问自己一个简单的问题“应该选择这个特定的边吗？”，这就足够了。然而，程序逻辑可能已经提出了一个边列表（可能是边的完整集合），并且想要回答一个更复杂的问题：“在这些 n 条边中，我应该选择哪一条？”。
我正要解释如何解决第二种类型的问题，但是在阅读各种评论的字里行间时，我想我更好地理解了手头的问题......

编辑（在评论中进行各种澄清之后）
正如怀疑的那样，潜在问题是优化问题而不是概率问题（尽管在这种情况下，概率用于以随机方式将搜索引导到解决方案空间）。
具体来说，该问题是Capacitated Vehicle Routing Problem的众多变体之一

在不知道我们正在尝试优化哪些特定参数（或其组合）的详细信息的情况下，我只能笼统地说，试图回答 OP 的问题之一：
可以将与权重相关的概率与概率结合起来与距离有关？

简而言之，是的。一个简单的乘法可以解决问题，尽管我想建议一个类似于以下的公式：

P(e) = Kw * Pw(e) + Kd Pd(e) + some_random_term
Where 
   P(e) is the probability of picking edge e, "all things considered"
   Kw and Kd are constant parameters which can be used to tweak the algorithm
   Pw(e) is the probability of picking egde e, with consideration to the Weight
   Pd(e) is the probability of picking egde e, with consideration to the Distance
   some_random_term is used to soften the algorithm in its tendency to favor too
      much high probability edges resulting in allowing the search process to get
      stuck in local minima.
      Rather than a added term, this can also be performed by a simple function
      which prevents the probability to be less than say 0.05 or more than say
      0.95.  A fancier sigmoid function may also do the trick.
于 2012-10-24T14:23:15.587 回答
1

这取决于您所说的“更可取”是什么意思。我也不太明白您所说的“我有 x 重量的限制”是什么意思。但一般来说，您可以创建一个数组概率，它存储在位置 i 处选择第 i 条边的概率。然后生成一个介于 0 和 1 之间的随机数并遍历 Array。如果这个数字小于当前位置的概率，我们就取那个边。否则，我们从数字中减去当前概率并移动到下一个位置。所以在伪代码中，它看起来像这样：

x = random([0.0, 1.0])
for i in 0..n
  if x < probabilities[i]
    choose(i)
    break
  else
    x -= probabilities[i]
  end
end

如果您有很多边，您还可以通过将边的概率总和从 0 到 i 存储在数组probability_sums 中的位置 i 中，然后在该数组中对 x 进行二分搜索并选择边那个位置。

于 2012-10-24T14:24:22.730 回答