消除在向无环图无关的边缘，而试图找到最长路径 [英] Eliminating extraneous edges in directed acyclic graph while trying to find longest paths

问题描述

我问了一个问题，关于寻找子序列中设定变量量没有重复字符。该解决方案是创建每对字母的矩阵，抛弃那些不发生在每一组，然后找到的最长路径的在向无环图。不过，我不希望仅仅是最长的路径，我想几个最长的路径（例如，如果它产生的长度10，10，9，8，8，3，3，2序列，和1，我可能要显示前5只子序列）。

所以，因为我不是在寻找只有最长的路径，因此，在使用维基百科的文章中所描述的最长路径算法生成结果序列，而不是，我使用的是一个天真的算法，它只是产生一个所有可能的子序列的列表。这会产生一组类似的结果回答我的previous的问题。

的问题是，我想减少子序列被产生的量。

例如，如果我有以下设置：

  A = AB12034
B = BA01234
C = AB01234
 

...我的算法，目前能想出发生在每一组下面的对：

  A  - 图1B  -  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 应该总是通过 0 才跳转到 3 ，因为所有套有这三个字母的位置： B＆LT; 0℃ ; 3 ）

只是要清楚，目前的算法将拿出这些子序列​​：（只有我包括那些与 A 开始为简洁起见）：

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

......，所有这些标有 * 应该被淘汰。

的（正确的）对，其产生所需的子序列是：

  A  - 图1B  -  1 1  -  2 2  -  3 0  -  3月3号至4号
    0 0
 

...和子序列的完整列表将是：

  A1234
A034
B1234
B034
1234
234
034
34
 

换句话说，我想从这个向无环图去：

要这样：

我应该为了使用什么样的算法/逻辑来摆脱这些外来的对（即图中边）的？或者你认为我在生成对摆在首位的逻辑是，应该改变的东西？

解决方案

  

此外，请注意0 B和3之间总是发生，所以我想以消除对B3（同样，乙方应随时通过0它跳跃前3，因为所有套有这三个字母的位置：乙℃，3;）

嗯，好吧，如果 N0＆LT; N1＆LT; N2 持有的所有集合，则删除所有（N0，N2）对？这可以用这个（pseudoPython）来实现：

 的（边缘节点）：
    如果（LEN（LongestPath（节点，edge.Node））→1）：
        RemovePair（节点，edge.Node）
 

I asked a question about finding subsequences in a variable amount of sets with no repeating characters. The solution was to create a matrix of each pair of letters, discard those that don't occur in each set, and then find the longest path in the directed acyclic graph. However, I don't want just the longest path, I want several of the longest paths (e.g. if it generates subsequences of lengths 10, 10, 9, 8, 8, 3, 3, 2, and 1, I may want to display the first 5 subsequences only).

And so, since I'm not looking for only the longest path, in order to generate the resulting subsequences, rather than using the longest path algorithm described in the wikipedia article, I'm using a naive algorithm which simply generates a list of all possible subsequences. This generates a set similar to the results in an answer to my previous question.

The problem is that I want to reduce the amount of subsequences it is generating.

For example, if I have the following sets:

A = AB12034
B = BA01234
C = AB01234

... my algorithm will currently come up with the following pairs that occur in each set:

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

This is technically correct, but I would like to eliminate some of these pairs. For example, notice that 2 always comes after 1. Therefore, I would like to eliminate the A2 and B2 pairs (i.e. A and B should never jump directly to 2... they should always go through 1 first). Also, 1 should never jump to any number besides 2, since 2 always occurs immediately after it. Furthermore, notice how 0 always occurs between B and 3, so I would like to eliminate the pair B3 (again, B should always go through 0 before it jumps to 3, since all sets have the positions of these three letters as: B < 0 < 3).

Just to be clear, the current algorithm will come up with these subsequences: (I included only those which begin with A for brevity):

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

... and all those marked with * should be eliminated.

The (correct) pairs which generate the desired subsequences would be:

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

... and the complete list of subsequences would be:

A1234
A034
B1234
B034
1234
234
034
34

In other words, I'm trying to go from this directed acyclic graph:

To this:

What sort of algorithm/logic should I use in order to get rid of these extraneous pairs (i.e. graph edges)? Or do you think that my logic in generating the pairs in the first place is the thing that should be changed?

解决方案

Furthermore, notice how 0 always occurs between B and 3, so I would like to eliminate the pair B3 (again, B should always go through 0 before it jumps to 3, since all sets have the positions of these three letters as: B < 0 < 3).

Hmm, okay so if n0 < n1 < n2 holds on all sets then remove all (n0, n2) pairs? This can be achieved with this (in pseudoPython):

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

这篇关于消除在向无环图无关的边缘，而试图找到最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！