具有多父节点的有向无环图 [英] Directed Acyclic Graph with multi-parent nodes

问题描述

给定:带有加权边的有向无环图，其中一个节点可以有多个父级.

Given: A directed acyclic graph with weighted edges, where a node can have multiple parents.

问题:对于根节点的每个子节点，找到从此类子节点到可以到达的某些叶子的最小成本(权重之和)路径.一个节点只能出现在一条这样的最小成本路径中.

Problem: For each child of root node, find a minimum-cost(sum of weights) path from such a child to some leaf which can be reached. A node can only be present in one such min-cost paths.

示例图:

在上图中，对于节点2，所有可用路径为:

In the above graph, for node 2, all the available paths are:

2 -> 5  
2 -> 1 -> 9 -> 6
2 -> 1 -> 10 -> 6
Among which 2 -> 1 -> 10 -> 6 has minimum cost of 3.5

类似地，对于节点4，所有可用路径为:

Similarly, for node 4, all the available paths are:

4 -> 11 -> 8
4 -> 7 -> 10 -> 6 
Among which 4 -> 7 -> 10 -> 6 has minimum cost of 3.0

当前结果为:

For node 2, the path is 2 -> 1 -> 10 -> 6 : Cost 3.5
For node 4, the path is 4 -> 7 -> 10 -> 6 : Cost 3.0
For node 3, there is no such path.

我已经编写了执行此操作的代码.现在，如果这样的最小成本路径没有任何共同点，该算法将停止并为我提供根节点所有子节点的最小成本路径.

I have written a code which does this. Now, if such min-cost paths didn't have any node in common, the algorithm would stop and give me min-cost paths for all children of root node.

但是，如果存在一个公共节点，那么我只能将其保留在其中一个节点中.原因是通常这种多父节点是由于噪声数据所致.一个节点应该仅属于一个父节点.我试图将这样的节点保持在成本最低的路径中.因此，与成本为3.5的节点2的最小路径相比，节点10属于成本为3.0的节点4的最小路径.节点6的逻辑也相同.因此，我将比较解除一些多父节点关联的成本.取消关联并不意味着将删除边缘.我要做的就是为节点的数据结构中的每个节点保存最佳父节点.例如，节点10将具有说最佳父节点是节点7"的条目，而节点6将具有最佳父节点是节点10"的条目.我实际上可以删除边缘本身，但我可能希望整个图形结构在以后的计算中保持不变.

However, if there exists a node in common, I have to retain it only in one of them. The reason is that normally such multi-parent nodes are due to noisy data. A node is supposed to belong to only one parent. I am trying to keep such a node in a path which has minimum cost. So here, node 10 belongs to min-path of node 4 which has cost of 3.0, compared to min-path of node 2 which has cost of 3.5. Same logic with node 6 too. So, I will just compare the costs to dis-associate some of the multi-parent nodes. Dis-association doesn't mean the edge will be removed. All I do is that save best parent for each node within node's data-structure. For example, Node 10 will have an entry saying "best parent is node 7" and Node 6 will have an entry "best parent is node 10". I can actually remove the edge itself but I may want the whole graph structure to remain intact for any future computations.

因此，逻辑看起来像这样:

So, the logic looks like this:

Do:
    For each child node of the root:
         Find out min-cost path. Store that path and the cost.
    If conflicting paths exist:
         Compare the costs of conflicting paths and save "best parent" for each node. 
While there were conflicting paths;

问题:

1. 这种逻辑有意义吗?我担心这种消除冲突的迭代方法可能无法在某些图形上收敛.例如，在重新计算节点2的最小路径时，如果现在发现2-> 5是最小路径，并假设在第一次迭代期间是否在其他某个节点的最小路径中使用了节点5，则我将不得不为节点5重新分配最佳父节点"作为节点2并重新迭代.简而言之，每次尝试修复某个节点的最小路径时，我可能都会更改另一个节点的最小路径.这样的算法可以收敛到某种解决方案吗?如果是，那么它的复杂性是什么?

1. Does this logic makes sense? I am worried that this iterative way of eliminating conflicts may not converge for some graphs. For example, while re-calculating the min-path for node 2, if 2 -> 5 is found to be the min-path now and assume if node 5 is being used in some other node's min-path during first iteration, then I would have to re-assign "best parent" for node 5 as node 2 and re-iterate. In a nut-shell, everytime I try to fix some node's min-path, I may change the other's. Can such an algorithm converge to some solution? If yes, what will its complexity be?

是否有办法在首先计算最小成本路径之前消除此类冲突?

Is there a way to eliminate such conflicts before computing the min-cost paths in the first place?

推荐答案

这是动态编程.

首先反转所有边缘以创建新图，我们将其称为newG.

First reverse all the edges to make a new graph, we call it newG.

1. 在newG中，没有父节点的节点的值为0.
2. 对于newG中具有父级的每个节点，计算 父项的值，然后选择最小值父项，它必须是 结果的一部分.
3. 从原始字形询问路径时，答案是相同的 在newG中.(可能答案中的边是相反的).

1. In newG, the node without parent has the value 0.
2. for every node which it have parents in newG, calculate it's parent's value, then choose the minimal value parent, it must be the part of the result.
3. when ask the path from the origin gtaph, the answer is the same in the newG.(may be the edges in the answer is in reverse order).

时间O(n)

这篇关于具有多父节点的有向无环图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！