algorithm - 寻找两个随机节点之间路径的递归公式的优化

Question

我编写了一个递归公式，用于查找以网格模式排列的两个节点之间的路径。我的代码有两个问题。第一个是有时起始节点的位置会从一个数字更改为另一个数字，但我通过在递归后重新分配它来解决这个问题，所以这没什么大不了的。第二个问题是它运行得慢得令人难以忍受。生成 5x5 大约需要 30 秒，而我无法生成 7x7，这是我的最终目标。我希望有人会看看是否可以进行任何优化。

如下所示，Node 类具有一个 Key 属性和一个 Value 属性。 Key 是网格中从 0 开始的位置。因此，对于 5x5，左上角节点的 Key 为 0，右下角节点的 Key 为 24。每个节点都有 Up、Down、Left 和 Right它连接到的其他节点的属性。当该方向上没有节点时，该值为空。例如，在 5x5 中，Key = 0 的节点的 Up 为 null，Key = 5 的节点的 Down，为 null 的 Left，以及 Key = 1 的节点的 Right。再举一个例子，仍然在 5x5 中，Key = 6 的节点将有一个 Key = 1 的节点的 Up，Key = 11 的节点的 Down，Key = 5 的节点的 Left，以及 Key = 5 的节点的 Right Key = 7. Position 属性是路径。该路径从 Position = 1 的节点开始，然后转到 Position = 2 的节点，依此类推，直到到达结束节点，即 NxN 板上的 N*N 位置(例如，5x5 的板将有一个结束节点位置 25)。这些节点被添加到一个名为 nodeList-(全局变量)的列表中。其中一个节点被随机标记为 Start-(boolean)，另一个节点被随机分配为 End-(boolean)。

下一部分是路径。我们想要在 Start 和 End 节点之间找到一条随机路径(从 1 开始)，该路径接触所有其他节点而不接触同一节点两次。这是一个游戏，所以它是随机的很重要，这样用户就不会玩同一个棋盘两次。如果给定开始位置和结束位置这不可能，则选择新的开始位置和结束位置并再次运行算法。

class Node
{
    public int Key { get; set; }
    public int? Position { get; set; } = null;
    public Node Up { get; set; } = null;
    public Node Down { get; set; } = null;
    public Node Left { get; set; } = null;
    public Node Right { get; set; } = null;
    public bool Start = false;
    public bool End = false;

    public Node(int key)
    {
        Key = key;
    }
}


public bool GeneratePath()
    {
        var current = nodeList.Where(w => w.Start).FirstOrDefault();
        var start = current;
        int position = 1;

        bool Recurse(Node caller)
        {
            if (current.Position == null)
            {
                current.Position = position;
            }
            if (current.End)
            {
                return true;
            }               


            var directions = GetDirections();

            for (var i = 0; i < 4; i++)
            {
                var done = false;
                if (directions[i] == 0 && current.Up != null && current.Up.Position == null
                    && (!current.Up.End || position == n * n - 1))
                {
                    var temp = current;
                    current = current.Up;
                    position++;
                    done = Recurse(temp);
                }
                else if (directions[i] == 1 && current.Down != null && current.Down.Position == null 
                    && (!current.Down.End || position == n * n - 1))
                {
                    var temp = current;
                    current = current.Down;
                    position++;
                    done = Recurse(temp);
                }
                else if (directions[i] == 2 && current.Left != null && current.Left.Position == null 
                    && (!current.Left.End || position == n * n - 1))
                {
                    var temp = current;
                    current = current.Left;
                    position++;
                    done = Recurse(temp);
                }
                else if (directions[i] == 3 && current.Right != null && current.Right.Position == null 
                    && (!current.Right.End || position == n*n - 1))
                {
                    var temp = current;
                    current = current.Right;
                    position++;
                    done = Recurse(temp);
                }
                if(done)
                {
                    return true;
                }
            }


            current.Position = null;
            position--;

            if(caller == null)
            {
                return false;
            }

            current = caller;

            return false;
        }

        var success = Recurse(null);

        if (success)
        {
            start.Position = 1;
        }

        return success;
    }



private int[] GetDirections()
    {
        List<int> toPerm = new List<int>();
        for (var i = 0; i < 4; i++)
        {
            toPerm.Add(i);
        }

        Random random = new Random();
        var perms = HelperMethods.GetPermutations(toPerm, toPerm.Count);
        var randomNumber = random.Next(0, perms.Count());
        var directions = perms.ElementAt(randomNumber).ToArray();

        return directions;

    }



public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetPermutations(list, length - 1)
            .SelectMany(t => list.Where(o => !t.Contains(o)),
                (t1, t2) => t1.Concat(new T[] { t2 }));
    }

重申一下，我想知道我是否可以进行优化，因为它对我的目的来说运行得太慢了。

Answer 1

所以我找到了一个惊人算法的实现，它可以在 12 秒内生成 10,000 个 7x7。你可以找到实现 here .作者是 Nathan Clisby，它基于一篇论文“长致密聚合物中的二级结构”。这个想法是在两点之间产生一条非随机路径，然后根据用户的意愿随机改变路径多次。据推测，通过足够的迭代，该算法可以生成几乎与我在问题中发布的算法一样随机的路径。

计算机科学家之路!