递归成堆栈形式.保留朝向递归结束的搜索路径 [英] Recursion into stack-form. Preserving a search path towards ends of recursion

问题描述

问题的简短形式是:如何将递归搜索转换为堆栈搜索?诀窍是能够抓住一个分支，导致每个递归的结尾.

A short form of question is: How do I convert a recursive search into a stack search? The trick is to be able to grab a branch that leads towards each of the recursion's endings.

本文的建议不能作为结局无法追查.(最终如果我们可以通过稍后的跟踪引用将每个步骤保存到数组中)

This Article's suggestion won't work as the path to the ending cannot be traced. (Ultimately if we could save each step into array via the reference to trace later on)

我正在使用 c#，并构建一个节点网络.

I am using c#, and building a web of nodes.

每个节点都包含有关其邻居的信息.此外，每个节点包含 2 个数组.第一个是引用该节点可以与之通信的所有节点.第二个数组包含列表，每个列表包含路径"，由有序的节点引用组成.

Each node contains an information about its neighbors. Also, each node contains 2 arrays. The 1st one is referencing all the nodes to which this node can communicate. The 2nd array holds lists, each of which contains "a path", consisting of ordered node references.

如果节点 A 希望与节点 B 通信，他将查看第一个数组以查看 B 是否在他的范围内.如果他找到它，他使用第二个数组上的第一个数组中的这个索引来获得路径".

If node A wishes to communicate to node B, he will look at the first array to see if B is even in his reach. If he finds it, he uses this index from a first array on a 2nd array to obtain "a path".

保持这个顺序对我来说很重要.

It's important for me to preserve this order.

除此之外，每个节点都包含一个直接邻居列表(在 1 范围内).

As well as that, every node contains a list of direct neighbors (within a reach of 1).

知道它的邻居实际上是每个节点在 Bake 过程发生之前唯一知道的事情.

Knowing its neighbors is actually the only thing each node knows before a Bake process occurs.

在烘焙期间，我递归地搜索被检查节点的每个邻居，将递归分支"记录到路径缓冲区列表中.一旦没有更多邻居，我就将此缓冲区路径列表"复制到第二个数组中+将此死端节点复制到第一个数组的下一个单元格中.corse 1st 和 2nd 数组属于我们开始的节点.

During the Bake, I recursively search through each neighbor of an inspected node, recording the "recursion branch" into a path-buffer list. As soon as there are no more neighbors, I copy this buffer "path-list" into the 2nd Array + copy this dead-end node into a next cell of the 1st Array. of corse 1st and 2nd array belong to the node which we started from.

然后我从路径列表的最后一个单元格中删除 1 个死端节点，回滚到前一个节点以检查另一个邻居并重复该过程.

I then remove 1 dead -end node from the path list's last cell, rollback to a previous node to inspect another neighbor and the process repeats.

问题是 - 如果网络变得太大，巨大的递归导致堆栈溢出.我需要将它翻译成堆栈形式.

The problem is - huge recursions cause a stack overflow if the web gets too big. I need to translate it into a stack form.

我查看了一些文章，例如这篇，但显然没有办法累积这个路径列表"，因为途中每个节点的每个邻居都被推入堆栈，期待将来进一步检查.我们到达这个死胡同的路径没有明确的痕迹".

I've looked over articles, such as this one, but there is obviously no way of accumulating this "path list", since every neighbor of every node on the way is pushed into a stack, anticipating a further inspection in future. There is no clear "trace" of the path we took to get to this dead-end node.

这是代码的简化版本(2个类)

Here is a simplified version of the code (2 classes)

class Node{

    List neighbours;
    List accessNodes;
    List allPaths;
}

class Baker{

  List bakerBufferPaths;
  List bakerBanned;


   foreach particular node in scene{
        clear accessNodes;
        clear allPaths;
        clear bakerBufferPaths;
        }

        MainNodeList1 = particular node's list1 by reference. //those 2 variables will always  refer to the base node for which the search happens. They will be unchanged on all the levels of recursion
        MainNodeList2 = particular node's list2 by reference.


    void  function LookFurther(Node node){
          Node current;
          current = node;


          bakerBufferList(add current);


          foreach (not banned neighbor in current){

               LookFurther(current);
          }//end of foreach neighbor of current

          MainNodeList 1 (add current);
          MainNodeList 2 (add bakerBufferList);

          bakerBanned(add current);

         bakerBufferList(remove last);
     } //end of look further function

} //end of baker class

怎么办?

谢谢

推荐答案

好的，这是一个有趣的问题，所以这是我编写的一些示例 C# 代码.

OK, this was an interesting question, so here's some example C# code I wrote up.

private static void SearchConnections(Node root)
{
    var path = new Stack<Node>();
    var progress = new Stack<int>();

    path.Push(root);        // start with root
    progress.Push(0);       // start with root's first neighbour

    while (path.Any())
    {
        var topnode = path.Peek();

        // continue the search until we get to a leaf
        int neighbourIx = progress.Pop();
        if (neighbourIx < topnode.Neighbours.Count())
        {
            // next time we are at this node, take the next neighbour
            progress.Push(neighbourIx + 1); 
            // don't push cycles onto the stack!
            var nextNeighbour = topnode.Neighbours[neighbourIx];
            if (!path.Contains(nextNeighbour))
            {
                path.Push(nextNeighbour);
                // when we process the neighbour we just pushed,
                // start with its first neighbour
                progress.Push(0);
            }
        }
        else
        {
            // no more neighbours here - either a leaf, or we've searched all 
            // neighbours. this is the last time we'll see this node, so 
            // process it now. record the path to the top node unless 
            // topnode is root - no path to self!
            if (topnode != root)
            {
                var trace = path.Reverse().ToList();
                root.Reachable.Add(topnode);
                root.Paths.Add(trace);
            }

            // remove the topnode from the stack
            path.Pop();
        }
    }
}

这是一个显示它工作的小提琴:http://dotnetfiddle.net/6ijNzb

Here's a fiddle that shows it working: http://dotnetfiddle.net/6ijNzb

我使用了两个堆栈 - 一个用于跟踪路径中的节点，另一个用于跟踪我们在路径中的每个分支上选择的邻居.

I've used two stacks - one to keep track of the nodes in the path, and one to keep track of which neighbour we picked at each branch in the path.

这篇关于递归成堆栈形式.保留朝向递归结束的搜索路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！