3

我有一个图，每个节点有 4 个子节点。我编写了一个算法来生成从开始节点到结束节点的随机路径。在每个节点，它选择一个随机的下一个节点。访问过的节点可以重新访问。

代码如下：

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;
    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[new Random().Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}

但有时，Random 无法按预期工作。“new Random().Next(4)”不断生成 0。因此它始终是第一个子节点被选中，并且生成了一个非常长的重复序列，如 node1->node2->node1->node2... 并最终生成发生内存不足异常。

有没有办法让 Random 类正常工作？

4

4 回答 4

12

原因是因为 Random 是根据当前时间初始化的（计算机中没有真正的随机......只有伪随机）。while 循环迭代太快，并且系统时间没有记录更改。因此，您正在重新初始化一个以相同值开头的新 Random 对象。

尝试创建一个在整个方法中重复使用的 Random 对象：

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;

    Random r = new Random();
    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[r.Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}
于 2012-07-24T00:39:12.947 回答
5

在循环外初始化随机实例，例如：

public List<Node> GetPath(Node begin, Node end)
{
    var nodes = new List<Node>();
    var node = begin;

    var random = new Random();

    while (node != end)
    {
        nodes.Add(node);
        var next = node.Children[random.Next(4)];
        node = next;
    }

    nodes.Add(end);

    return nodes;
}
于 2012-07-24T00:38:29.077 回答
0

这里有几件事对你不利。第一个是每次你要求一个不同的数字，但这不是这个类所做的，也不是随机的定义。所以，这个类实际上工作正常。

随机的定义

  1. 没有方法或有意识地做出、完成、发生或选择：“100 个家庭的随机样本”。
  2. 由或涉及每个项目的平等机会。

现在，这个班级尽最大努力为每个选项提供平等的选择机会。因此，当您想到随机时，请确保您将术语的定义置于上下文中。但是，请记住，这门课不像人的大脑那样工作。

现在，为了解决您非常频繁地归零的事实，它的发生有两个原因。首先，您new在每次迭代中创建一个 Random 类。但更重要的是，您的范围太小，因为您希望它每次在只有 4 个选项的范围内给您一个不同的数字，并且因为它是伪随机的，正如MSDN所说的那样，您经常得到相同的答案。

我意识到你只给它 4 个选项的原因，但我认为你可能需要重新考虑你正在寻找的功能类型，因为它可能会减少挫败感。

于 2012-07-24T01:42:02.277 回答
0

您提到该方法在多个线程中被调用。一种解决方案是每个线程有一个随机数生成器，由静态 rng 播种。

我还删除了常量 4 并将其更改为node.Children.Count.

static Random seed = new Random();
[ThreadLocal] static Random rng;

public List<Node> GetPath(Node begin, Node end)
{
var nodes = new List<Node>();
var node = begin;

if (rng == null)
   rng = new Random(seed.Next());

while (node != end)
{
    nodes.Add(node);
    var next = node.Children[rng.Next(node.Children.Count)];
    node = next;
}

nodes.Add(end);

return nodes;
}
于 2012-07-24T01:30:15.790 回答