Устранение посторонних ребер в ориентированном ациклическом графе при попытке найти самые длинные пути

Question

Я задал вопрос о поиске подпоследовательностей в переменном количестве наборов без повторяющихся символов. Решение состояло в том, чтобы создать матрицу из каждой пары букв, отбросить те, которые не встречаются в каждом наборе, а затем найти самый длинный путь в ориентированном ациклическом графе. Тем не менее, я не хочу только самый длинный путь, я хочу несколько самых длинных путей (например, если он генерирует подпоследовательности длиной 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 всегда должен проходить через 0, прежде чем она перейдет к 3, поскольку все наборы имеют позиции этих трех букв как: 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                           

... и полный список подпоследовательностей будет:

A1234
A034
B1234
B034
1234
234
034
34

Другими словами, я пытаюсь перейти от этого ориентированного ациклического графа:

На это:

Какой алгоритм / логику я должен использовать, чтобы избавиться от этих посторонних пар (т. Е. Ребер графа)? Или вы думаете, что моя логика в генерации пар - это то, что нужно изменить?

Answer 1

Кроме того, обратите внимание, как 0 всегда происходит между B и 3, поэтому я хотел бы исключить пару B3 (опять же, B всегда должен проходить через 0, прежде чем он перейдет к 3, поскольку все наборы имеют позиции этих трех букв как : B <0 <3). </p>

Хм, ладно, так что если n0 < n1 < n2 сохраняется на всех подходах, то удалить все пары (n0, n2)? Это может быть достигнуто с помощью этого (в псевдо-Python):

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

Answer 2

Легко, легко.Если график не слишком большой, он, вероятно, также достаточно эффективен.

• Для каждого узла (начиная с узлов без входящих ребер) следуйте по всем путям, отмечая расстояния, отметьте все прямые потомки 1 ипоставить их в очередь.Пока очередь не пуста, вытяните узел n, пусть d будет его расстоянием от начала.Посмотрите на все его прямые дочерние элементы, если они помечены 1, удалите ребро от начала до этого, поместите все дочерние элементы n в очередь, отмеченную расстоянием d+1.Извлечь следующий узел из очереди.

То, что сказал JSPerfUnkn0wn, только с более подробной информацией.

Answer 3

Поскольку график является ациклическим, возможное решение - применить ваш любимый алгоритм кратчайшего пути (Bellman-frod, Floyd-Warshal и т. Д.), Но с условием сравнения (так что более длинные пути выигрывают у более коротких путей).