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。因此，我想消除A2andB2对（即A并且B永远不应该直接跳转到2......他们应该总是先通过1）。此外，1永远不要跳到除 之外的任何数字2，因为2总是紧跟在它之后。此外，请注意和0之间总是如何发生，所以我想消除这对（同样，应该总是在它跳转到 之前经过，因为所有集合都有这三个字母的位置：）。B3B3B03B < 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

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

A1234
A034
B1234
B034
1234
234
034
34

换句话说，我试图从这个有向无环图出发：

在此处输入图像描述

对此：

在此处输入图像描述

我应该使用什么样的算法/逻辑来摆脱这些无关的对（即图形边缘）？还是您认为我首先生成配对的逻辑是应该改变的？

4

3 回答 3

2

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

嗯，好吧，所以如果n0 < n1 < n2保留所有集合然后删除所有(n0, n2)对？这可以通过以下方式实现（在pseudoPython中）：

for(edge in node):
    if(len(LongestPath(node, edge.Node)) > 1):
        RemovePair(node, edge.Node)
于 2012-01-01T04:53:51.067 回答
1

容易就是容易。如果图表不是太大，它可能也足够有效。

  • 对于每个节点（从没有传入边的节点开始），遵循所有路径，标记距离，用 1 标记所有直接子节点并将它们放入队列中。当队列不为空时，拉出一个节点n，让它d从起点开始。查看它所有的直接子节点，如果有标记为 1 的，则从 start 到那个删除边，将 的所有子节点n放入标记为 distance 的队列中d+1。从队列中拉下一个节点。

JSPerfUnkn0wn 所说的，只是更详细一点。

于 2012-01-01T04:59:02.387 回答
0

由于该图是非循环的，因此可能的解决方案是应用您最喜欢的最短路径算法（Bellman-frod、Floyd-Warshal 等），但比较条件翻转（以便较长的路径胜过较短的路径）。

于 2012-01-01T04:59:09.780 回答