logo标签列表

检测图重新收敛的算法（类似于公共子树？）

c#algorithmgraphsubtree
9
我一整天都在解决这个问题，我正在重写我们的一个旧产品，但我很难确定如何找到流程图中的特定节点。这个问题让我想起了大学，但我死活想不出用来解决它的算法。
我附上了3张屏幕截图以帮助说明问题，但基本的问题是，在给定一个YES/NO?决策节点的情况下，找到终止分支的最近子节点。我正在使用C# .NET和JSON进行开发。在JSON中，我有一个为每个节点分配唯一标识符并标识从一个节点到另一个节点的“链接”的对象。我希望能编写一个函数（或多个函数）来确定在C#中给定一个分支节点的第一个“结束节点”。目前，我已经在C#中将JSON构建为XML。
欢迎所有的想法，我不是真正想要代码，而是一种方法/算法。
以下是该图表的JSON输出：
{ "class": "go.GraphLinksModel",
  "linkFromPortIdProperty": "fromPort",
  "linkToPortIdProperty": "toPort",
  "nodeDataArray": [ 
{"key":-1, "category":"Start", "loc":"169 288", "text":"Start"},
{"key":-2, "category":"End", "loc":"855 394", "text":"End"},
{"category":"Branch", "text":"Yes or No", "key":-4, "loc":"284.8837209302326 285.7848837209302"},
{"category":"DelayNode", "text":"Delay", "key":-3, "loc":"365.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-5, "loc":"478.8837209302326 214.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-6, "loc":"568.8837209302326 151.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-7, "loc":"573.8837209302326 268.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-8, "loc":"653.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-9, "loc":"392.8837209302326 392.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-10, "loc":"454.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-11, "loc":"550.8837209302326 473.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-12, "loc":"549.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-13, "loc":"711.8837209302326 343.5234599717762"},
{"category":"Branch", "text":"Yes or No", "key":-14, "loc":"434.8837209302326 487.5234599717762"}
 ],
  "linkDataArray": [ 
{"from":-4, "to":-3, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-1, "to":-4, "fromPort":"R", "toPort":"L"},
{"from":-3, "to":-5, "fromPort":"R", "toPort":"L"},
{"from":-5, "to":-6, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-5, "to":-7, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-6, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-7, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-4, "to":-9, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-9, "to":-10, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-10, "to":-12, "fromPort":"R", "toPort":"L"},
{"from":-11, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-12, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-8, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-13, "to":-2, "fromPort":"R", "toPort":"L"},
{"from":-9, "to":-14, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-14, "to":-11, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-14, "to":-11, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"}
 ]}
1
在你的所有示例中，一旦你选择了其中一个分支，你总是最终到达“结束”。你永远不会回到决策节点并有可能再次进入。这个属性通常适用吗？还是需要考虑存在循环的情况？如果没有这样的循环，解决方案就很简单；如果可能存在循环，则稍微棘手一些。 - Eric Lippert
@EricLippert，你的假设是正确的，没有循环回来，一切都向前移动。我认为我在下面的答案评论中的评论实际上就是我正在寻找的解决方案。 - Brian Garson
1
很好。还要注意，您需要具有恰好一个“end”节点的属性，或者至少如果存在多个“end”节点，则它们相互比较相等。 - Eric Lippert
我再仔细想了一下，我不确定给出的答案是否正确。请看我的评论。 - Eric Lippert
5个回答
6
更新：我想出了另一个解决方案，这次使用了标准的最近公共祖先问题的解决方案。请查看我的另一个答案。
如Oren的答案中所述，他已经回答了“哪个是两个分支都可以到达的最近节点？”的问题。但实际上需要回答的问题是“哪个是两个分支必须到达的最近节点？”
这是一个相当困难的问题，我不知道有什么有效的解决方案。然而，以下是一种可能行之有效的算法的草图。
假设给定的决策节点称为A，WLOG它有两个子节点B和C。那么问题就是什么是节点G，并具备以下两个属性：
- 从B到END的每条可能路径以及从C到END的每条可能路径都通过G。 - G是离B和C最近的并具有第一个属性的节点。
（注意，G可能是END。我们可以有A->B、A->C、B->END、C->END。）
我们可以轻松地制作一组可能G的候选项。随意选择从B到END的任何路径，并将其节点放入哈希集合中。然后选择从C到END的任何路径，并将其节点放入哈希集合中。这两个集合的交集包含G。将交集集合称为Alpha。
现在让我们从Alpha集合中删除绝对不是G的所有节点。对于Alpha集合中的每个节点N：
- 构造一个与原始图相同但缺少N的新图。 - 在新图中是否仍然可以从B或C到达END？如果是，则N绝对不是G。如果不是，则将N添加到Beta集合中。
如果当我们完成时Beta为空，则G为END。
否则，Beta中存在节点。这些节点中的每一个都具有以下属性：如果该节点被删除，则没有其他方法可以从B或C到达END。其中恰好一个节点离B最近--如果两个节点距离相等，则其中之一是不必要的！所以从B开始进行广度优先遍历，第一次遇到Beta中的节点就是你的G。
这个草图似乎在图形很大的情况下不会很快，但我非常确定它会起作用。如果有更好的解决方案，我会很感兴趣知道。
我认为这个想法是从决策节点开始搜索图形。如果你到达另一个决策节点，你记录下当前的路径。然后再次开始搜索（寻找闭合）。如果到达死路或最大深度，则返回无解。否则，如果你找到了闭合，你将该子图合并成一个“延迟”节点，并使用记录下来的路径回溯到前一个决策节点并重复执行。 - Alan
5
我喜欢Alex的答案，它似乎非常高效。这里有另一种解决您的问题的方法，事实上它是最近公共祖先问题。这是图论中一个非常研究的问题；我一开始没有看到它，因为您必须反转所有箭头。
使用此解决方案，您只需进行一次昂贵的预处理，然后就可以拥有一个数据结构，您可以从中读取答案。
我已经给您的图中的节点贴了标签。您要做的第一件事是反转所有箭头，然后构造结果DAG的欧拉遍历，在每个步骤中记住离“根”（末尾）有多远。
欧拉遍历是“访问自己，对邻居进行递归，访问自己，对邻居进行递归，...访问自己”的过程。也就是说，如果我们用C#编写它，我们会说类似于：
void Eulerian(Node n, int i, List<Tuple<Node, int>> traversal)
{
    traversal.Add(Tuple.Create(node, i));
    foreach(Node neighbour in node.Neighbours)
    {
        Eulerian(neighbour, i + 1, traversal);
        traversal.Add(Tuple.Create(node, i));
    }
}

欧拉遍历是当您在遍历图形时实际上需要采取的遍历方式。

您提供的示例图形在反转所有箭头并从结束点开始时，其欧拉遍历如下。

A0 B1 C2 D3 E4 F5 G6 H7 G6 F5 E4 D3 C2 I3 E4 F5 G6 H7 G6 F5 E4 I3 C2 
B1 J2 K3 L4 G5 H6 G5 L4 K3 J2 B1 M2 N3 L4 G5 H6 G5 L4 N3 M2 N3 L4 G5 
H6 G5 L4 N3 M2 B1 A0

您的问题的答案现在可以从遍历中读取。在您的示例中，您有决策节点E、L和G。
对于E：在遍历中找到E的第一个和最后一个出现位置。现在在这两个位置之间的节点中搜索得分最低的节点。它是C，得分为2。
对于L：在遍历中找到L的第一个和最后一个出现位置。它们之间得分最低的节点是B，得分为1。
对于G：同样，在第一次和最后一次出现G之间得分最低的节点是B。
如果图形很大，则计算遍历可能很耗费时间，但好处是您只需要执行一次。之后，它就成为一个线性搜索问题。(如果你真的想做到亚线性搜索，那么这似乎需要很多额外的工作)
我真的很喜欢这个答案，我已经在脑海中想出了自己变化的不同算法，但我认为我可能会实现这个。 - Brian Garson
2

如果我理解问题的话，您正在尝试找到“yes”和“no”子树之间的第一个公共节点。在这种情况下，一种简单的方法是对“yes”子树进行广度优先遍历，将每个元素添加到列表中。然后对“no”子树进行广度优先遍历，在该子树中出现“yes”列表中的元素时停止。

1
这是我要推荐的解决方案。我只想补充一点，如果节点数量很大，你应该使用哈希集而不是列表。 - Eric Lippert
1
@EricLippert：说得好。使用哈希集合可以提高此算法的效率。这也意味着您的第一次遍历可以按任何顺序进行，而不像第二次遍历必须仍然是广度优先。 - Oren Melzer
谢谢大家。我简直不敢相信我忙了一整天，竟然忽略了这个问题。干杯。 - Brian Garson
2
等等，我不太确定这个答案是否正确；我认为问题描述不清。假设我们有图 START->A, A->B, A->C, B->E, B->G, C->D, C->E, D->F, E->G, F->G, G->END。我们希望找到 B 和 C 的最近公共后代。正确的答案是 E 还是 G？如果是 E，那么这个算法就是正确的。但是 OP 可能想要 G。 - Eric Lippert
1
另一种理解方式是：假设您想在“ A”和其他节点周围画一个框，使得只有一条线进入该框，并且只有一条线从该框中出来。如果框包含尽可能少的节点，则离开框的线连接到哪个节点？这个问题的答案是“ G”，我认为这就是OP所说的“终止分支”的意思。 是吗？ - Eric Lippert
显示剩余7条评论
1

使用两个广度/深度优先搜索，可以在O(V + E)的时间内完成此操作。

首先，让我们描述一下问题。我们有一个图形，一个起始节点A和一个结束节点END。根据@EricLippert的定义（并由我稍作改编，因为我们可以等效地使用A而不是B和C），我们正在寻找具有以下两个属性的节点G：

  • 从A到END的每条可能路径都经过G。
  • G是具有第一个属性的离A最近的节点。
首先，我们使用 X-first 搜索从 A 到 END 找到一条路径。设 P = (p1, p2, p3, ..., pk)，其中 p1 = A，pk = END 并将它们编号为 1, 2, ..., k（pi 的编号为 i）。将这些数字与图中的节点一起存储。从图中删除路径 P 使用的边。再次从 A 进行 X-first 搜索，并找到可从 A 到达的最高编号节点 pi。我们稍微调整了这个搜索：每当我们找到一个可到达的节点 pj，它比前一个可到达的节点 pk 更高时，我们将子路径（pk、pk+1、...、pj）中的所有边重新添加到图中，并将这些节点之间的所有节点标记为可达，并将以前不可达的所有节点添加到用于处理的队列/栈中的 X-first 搜索中。以此方式返回找到的 pi。
我们现在将证明pi满足G的条件。假设（为了达到矛盾）我们有一条路径S =（s1，s2，s3，...，sj），其中s1 = A且sj = END没有经过pi。此路径的某个前缀（s1，s2，s3，...，sm）与我们的路径P相符，因此s1 = p1，s2 = p2，...，sm = pm，但sm + 1！= pm + 1。由于S没有经过pi，并且当我们添加(s1，s2，s3，...，sm)使用的边时，sm在第二次X-first搜索中变得可达，因此，在我们第二次X-first搜索时，我们也将遍历路径S的其余部分，直到它到达END或者在S中使用的某个边（pr，pr + 1）位于路径P上，但r > i，因此删除该边。然而，那么我们会发现pr（或END）是可达的，r > i，所以我们不会返回pi，这是一个矛盾。因此，所有路径都经过pi。
现在假设存在一个节点G'，它具有上述属性，但比pi更接近A。由于所有路径都经过G'，因此P也经过G'，因此存在某个v，使得pv = G'且v < i。由于所有路径都经过G'且（pv，pv + 1）已被删除，因此最初无法到达pv之后的任何节点，因此（pv，pv + 1）永远不会被添加，因此pi也永远不会变得可达，因此它不可能被算法返回，这是一个矛盾。因此pi是最接近满足G条件的节点，证明了算法的正确性。
第一次X-first搜索需要O（V + E）时间。第二次也需要O（V + E）时间：所有节点最多只添加一次到队列/堆栈中，因此即使我们将边添加回图中，运行时间也保持不变；最终边数不超过原始图的边数。维护路径的索引和迄今为止找到的最高索引也需要O（V + E）时间，因此我们得出结论，我们的算法在O（V + E）时间内运行。
0

所以我考虑了一下这个问题，考虑到这里提供的一些答案，我还没有开始编写代码，但是鉴于其中一个答案，我稍微修改了一下伪代码。

我认为更有效的方法是在一个公共字典变量（键，值）对中跟踪任何分支节点的所有结果。 对此方法有什么想法吗？ 我应该提到的一件事是，图形永远不应该增长到超过25个节点。

//call this function for all nodes with 2 children
int getFirstCommonAllpathEndNode(currentNodeId, xml, endNodeId){

    Array[] possibleNodeIds;
    //traverse child nodes
    foreach(childnode of CurrentNode.TopPortChildNode){
        if(childNode has 2 ports)
        {
            possibleNodeIds.add( getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId));
        }
        else{
            possibleNodeIds.add(childNode.Id);
        }
    }

    foreach(childnode of CurrentNode.BottomPortChildNode){
        if(childNode has 2 ports)
        {
            //recursive call for this branch to get it's first common all path end node
            var someNodeId = getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId) 
            if(possibleNodeIds contains someNodeId) 
                return someNodeId;
            //otherwise skip forward to someNodeId as next node to process in for loop
        }
        else{
            if (possibleNodeIds contains childNode.Id)
                return childNode.id
        }
    }
    //return the endNode if nothing else is satisfied. although this code should never be hit
    return endNodeId;
}
2
如果图形永远不超过25个节点，那么您选择的任何解决方案都会表现得相当不错。尽管如此，如果一个图形是不可变的，那么记忆化肯定是一种合理的策略。您可以考虑编写一个通用函数记忆化器，而不是将记忆化逻辑添加到您的某个函数中。我会在下一个评论中给你一个。 - Eric Lippert
1
靜態函數 Memoize<A, R>（<A, R> 分別為輸入和輸出類型）可對傳入的 Func<A, R> 函數進行記憶化處理。使用一個字典來存儲已計算過的結果，如果再次呼叫該函數，直接返回已經存儲在字典中的結果即可，無需重複執行計算。此方法可大幅提高效率，而且不會污染原始業務邏輯。 - Eric Lippert
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接