在尝试找到最长路径时，消除有向无环图中的多余边

Question

在尝试找到最长路径时，消除有向无环图中的多余边

javascriptalgorithmgraphdirected-acyclic-graphs

4

我曾经提出了一个问题，关于在变量数量的集合中找到不重复字符的子序列。解决方法是创建每对字母的矩阵，丢弃那些不在每个集合中出现的字母，然后在有向无环图中找到最长路径。然而，我不仅想要最长路径，我还想要几个最长路径（例如，如果它生成长度为10、10、9、8、8、3、3、2和1的子序列，则我可能只想显示前5个子序列）。

因此，由于我不仅寻找最长路径，为了生成结果子序列，我使用了一个简单的算法来生成所有可能的子序列列表，而不是使用维基百科文章中描述的最长路径算法。这将生成类似于之前问题的答案中的结果集。

问题是我想要减少其生成的子序列数量。

例如，如果我有以下集合：

A = AB12034
B = BA01234
C = AB01234

目前，我的算法会找出每个集合中出现的以下配对：

A - 1     B - 1     1 - 2     2 - 3     0 - 3     3 - 4
    2         2         3         4         4
    3         3         4
    4         4
    0         0

这在技术上是正确的，但我想消除其中的一些对。例如，请注意2始终在1之后出现。因此，我想消除A2和B2对（即A和B不应直接跳到2...它们应该始终先经过1）。此外，1不应跳到除2之外的任何数字，因为2总是紧随其后。此外，请注意0始终出现在B和3之间，因此我想消除对B3（同样，B在跳到3之前应始终通过0，因为所有集都将这三个字母的位置设置为：B < 0 < 3）。

清楚地说，当前算法将得出以下子序列（为简洁起见，我仅包括以A开头的序列）：

A1234
A124  *
A134  *
A14   *
A234  *
A24   *
A34   *
A4    *
A034
A04   *

...并且所有标记为*的都应该被消除。

生成所需子序列的（正确）对将是：

A - 1     B - 1     1 - 2     2 - 3     0 - 3     3 - 4
    0         0

...并且完整的子序列列表将是:

换句话说，我正试图从这个有向无环图中进行转换：

enter image description here

到这个：

enter image description here

我应该使用什么样的算法/逻辑才能摆脱这些多余的对（即图形边缘）？或者您认为我生成这些对的逻辑是应该改变的东西？

- Senseful

如果我理解正确，您想要最大公共子序列，并且在图中想要消除存在更长路径的两个节点之间的边？ - Daniel Fischer

@DanielFischer：确切地说……有没有一种简单/高效的方法来做到这一点？我应该先按拓扑顺序对图进行排序吗？ - Senseful

请澄清一下 - 您是想在无权DAG中找到所有最长路径，还是您也对较短的路径感兴趣？对于前者，可能有一个简单的算法（尽管我想不出来）。对于后者，您可以使用K短路算法来实现。 - Nabb

3个回答

1

Easy就是易懂。如果图不太大，那么它可能也足够高效。

对于每个节点（从没有入边的节点开始），跟随所有路径，标记距离，将所有直接子节点标记为1并放入队列中。当队列不为空时，取出一个节点n，让d为其距离起点的距离。查看其所有直接子节点，如果有任何一个被标记为1，则从起点到该节点的边缘被移除，将n的所有子节点标记为距离d+1并放入队列中。从队列中取出下一个节点。

就像JSPerfUnkn0wn所说的那样，只是多了一些细节。

- Daniel Fischer

0

由于图是无环的，一个可能的解决方案是应用您喜欢的最短路径算法（Bellman-frod、Floyd-Warshal等），但将比较条件翻转（使较长的路径胜过较短的路径）。

- hugomg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keldon Alleyne · Accepted Answer

此外，请注意0总是出现在B和3之间，因此我想消除B3这一对（同样，B应该在跳到3之前经过0，因为所有集合的这三个字母的位置为：B < 0 < 3）。

嗯，好的，所以如果在所有集合中都保持n0 < n1 < n2，则删除所有(n0, n2)对？可以通过以下方式实现（伪Python代码）：

for(edge in node):
    if(len(LongestPath(node, edge.Node)) > 1):
        RemovePair(node, edge.Node)