Математика · объяснение и практика

Как посчитать допустимые порядки при заданных зависимостях

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

Допустимый порядок сохраняет каждую исходную зависимость. Для подсчёта выбирают возможный первый элемент и суммируют количества продолжений, а не умножают безусловно числа доступных задач.

Найти один порядок и сосчитать все — разные задачи

Пусть подготовка A должна предшествовать сборке C, а проверка B тоже должна завершиться до C. Разрешены порядки A,B,C и B,A,C. Поиск любого из них решает вопрос выполнимости, но для подсчёта необходимо учесть оба. В общем случае направленный цикл зависимостей не оставляет допустимого линейного порядка.

В ациклической схеме первым может быть любой элемент без незавершённых предшественников. После его удаления доступный набор меняется. Разные первые решения способны оставлять разное число продолжений. Поэтому одно число доступных задач на текущем шаге нельзя автоматически умножать на одно и то же число будущих вариантов без проверки оставшейся структуры.

Разбить по первому элементу

Обозначим через F(S) число порядков для оставшегося набора S с сохранёнными зависимостями. Тогда F(S) равно сумме F(S без v) по доступным первым v. Для пустого набора F=1: это один способ закончить уже построенный порядок. Если набор непуст, но доступных элементов нет, ветвь даёт ноль.

Для двух независимых цепочек A<B<C и D<E порядок внутри каждой фиксирован. Достаточно выбрать три позиции первой цепочки среди пяти; остальные займёт вторая. Поэтому порядков C(5,3)=10. Это особая простая структура. При дополнительных перекрёстных зависимостях свободное перемешивание уже включает запрещённые варианты и требует пересчёта.

Пример

Три задачи A,B,C не имеют связей между собой, но все должны предшествовать задаче D. Сколько порядков?

Задача D обязана стоять последней, а A,B,C занимают первые три места в любом порядке. Получаем 3!=6. Это подсчёт всех продолжений, а не просто один возможный список.

Что считать различным результатом

Предполагается, что все задачи различимы и выполняются в одной последовательности, без одновременных шагов. Если одинаковые операции не различают или разрешают параллельные временные слоты, объект подсчёта меняется. Линейный порядок не содержит сведений о длительностях и сам по себе не даёт время завершения проекта.

Для маленьких схем можно явно перечислить продолжения и проверить каждую зависимость. Для больших конечных схем запоминают F(S), чтобы одинаковый остаточный набор не пересчитывался из разных начал. Однако возможных подмножеств много, поэтому такая точная схема не обещает быстрого решения произвольного огромного графа. Учебная ценность — в прозрачном разделении ветвей и сохранении условий.

От чтения к действию

А теперь — вы

Пять разных задач A,B,C,D,E нужно расположить так, чтобы A предшествовала B,C,D; других зависимостей нет. Сколько порядков?

Частые вопросы

Почему нельзя просто поделить n! на число зависимостей?

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

Что означает отсутствие доступной задачи?

Если задачи ещё остались, исходные зависимости содержат цикл среди оставшихся и ветвь не имеет допустимого продолжения.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться