Кажется, это обычная проблема с расписанием, но я не вижу решения или даже как назвать проблему.Это похоже на топологическую сортировку, но отличается ...
Учитывая некоторые зависимости, скажем,
A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D
может быть несколько решений топологической сортировки:
A, B, C, D
and A, C, B, D
оба решения.
Мне нужен алгоритм, который возвращает это:
(A) -> (B,C) -> (D)
То есть, сделайте A, затем все B и C, затем вы можете сделать D. Все неоднозначностиили не заботятся, сгруппированы.
Я думаю, что алгоритмы, подобные Топологическая сортировка с группировкой , не будут правильно обрабатывать случаи, подобные следующим.
A -> B -> C -> D -> E
A - - - > M - - - > E
Для этого алгоритм должен вернуть
(A) -> (B, C, D, M) -> (E)
Этот
A -> B -> D -> F
A -> C -> E -> F
должен вернуть
(A) -> (B, D, C, E) -> (F)
В то время как этот
A -> B -> D -> F
A -> C -> E -> F
C -> D
B -> E
долженreturn
(A) -> (B, C) -> (D, E) -> (F)
И этот
A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
C -> D
C -> M
B -> E
B -> M
L -> D
L -> E
должен вернуть
(A) -> (B, C, L) -> (D, E, M) -> (F)
Есть имя и традиционное решение этой проблемы?(И правильно ли обрабатываются алгоритмы, размещенные в Топологическая сортировка с группировкой ?)
Редактировать, чтобы отвечать на запросы дополнительных примеров:
A->B->C
A->C
должен вернуть
(A) -> (B) -> (C). That would be a straight topological sort.
И
A->B->D
A->C->D
A->D
должен вернуть
(A) -> (B, C) -> (D)
И
A->B->C
A->C
A->D
должен вернуть
(A) -> (B,C,D)