Алгоритм быстрого получения частичного упорядочения по нескольким связанным спискам - PullRequest
Новая
       15

Алгоритм быстрого получения частичного упорядочения по нескольким связанным спискам

6 голосов
/ 17 июня 2011

У меня есть такая ситуация:

  • У меня есть n списки с двойной связью
  • Каждый список имеет начало и конец дозорного
  • Все списки имеют одинаковые начальный и конечный узлы (не обязательно, но для простоты)
  • Списки однородны и могут совместно использовать элементы

Я бы хотел найти частичное упорядочение всех узлов во всех списках n , начиная с начального узла и заканчивая, ну, в конце концов, конечным узлом, так что любой узел, который появляется в nx списки, где x , будут отсортированы относительно других узлов во всех списках, в которых он появляется.

Использование массивов для предоставления примера набора списков:

first  = [a, b,    d,    f,    h, i];
second = [a, b, c,       f, g,    i];
third  = [a,          e, f, g, h, i];

Очевидно, что одним из возможных ответов будет [a, b, c, d, e, f, g, h, i], но другим допустимым порядком будет [a, b, d, e, c, f, g, h, i].

Я знаю, что - это быстрый алгоритм, чтобы сделать это, кто-нибудь помнит, как это происходит или что яназывается?У меня уже есть несколько медленных версий, но я уверен, что где-то в Кнуте есть намного более быстрая.

(И, прежде чем вы спросите, это не для домашней работы или Project Euler, и я не могу сделатьэто более конкретно. Это является проблемой.)

Редактировать: Я относительно уверен, что частичное упорядочение определяется только до тех пор, пока конечные точки находятся во всех списках и водинаковые позиции (начало и конец).Я не был бы против поиска по линейному времени, чтобы найти эти конечные точки, и если они не могут быть найдены, тогда может возникнуть ошибка.

Ответы [ 2 ]

2 голосов
/ 18 июня 2011

Выглядит очень похоже на Топологическая сортировка для меня. Есть несколько алгоритмов, чтобы получить топологически отсортированное состояние. Тот, который мне особенно нравится, похож на поиск в ширину. Поддержите два списка, один из всех узлов, у которых нет внутренних ребер, скажем, L (первоначально это был только узел a), другой с частично упорядоченными узлами, F. Теперь на каждом шагу 

pick a node from `L`, 
do some operations (explained later), 
and move the chosen node to the `F` list.

В «шаге выполнения некоторых операций», 

choose all successors of the source node which have exactly one in-link add them to L.
Remove the link from the source node to all the successors in the previous step

Теперь в списке F все ваши узлы отсортированы топологически. Я извиняюсь за ужасное объяснение, вики-ссылка имеет хорошие диаграммы:)

0 голосов
/ 18 июня 2011

Либо я недопонимаю, либо алгоритм Чужого может сорваться.(Я бы добавил это как комментарий, но я слишком новичок, чтобы комментировать.)

Рассмотрим этот пример: 

first  = [a, b, c, d,             i];
second = [a,       d, e, f,       i];
third  = [a,             f, g, h, i];

Алгоритм Алиенхарда даст: a=0, b=1, c=2, d=3, e=2, f=3, g=2, h=3, i=4.

Затем алгоритм требует, чтобы e предшествовало d, хотя e следует за d в ​​секунду.

...