Часть 2 из 2
Часть 2 из 2
Три набора {a, b}, {a, c} и {b, c} образуют антицепь по включению. Они имеют одинаковый размер, поэтому один мог бы содержаться в другом лишь при совпадении. Как видно, антицепь не требует отсутствия общих элементов.
Можно ли найти антицепь побольше среди всех подмножеств {a, b, c}? Разобьём все восемь подмножеств на три цепи. Здесь ∅ означает пустое множество, а ⊂ обозначает строгое включение.
∅ ⊂ {a} ⊂ {a, b} ⊂ {a, b, c}
{b} ⊂ {b, c}
{c} ⊂ {a, c}
Антицепь может содержать не более одного элемента из каждой цепи, иначе два её элемента окажутся сравнимыми. Значит, её размер не превосходит трёх, и найденный пример достигает этой границы. Для конечного множества максимальный размер антицепи называют шириной порядка.
В планировании работ условие X ≤ Y означает, что X = Y или задача X должна завершиться до начала Y, прямо или через промежуточные зависимости. При отсутствии циклов это частичный порядок. Одновременно выполняемые задачи образуют антицепь, поэтому их число не превосходит ширины порядка. Но несравнимость ещё не гарантирует готовность к запуску. Сначала должны завершиться все предшественники, а для параллельной работы должно хватать ресурсов.
Антицепи возникают и при выборе по нескольким критериям. Пару (цена, время) считаем не хуже другой, если обе её координаты не больше соответствующих координат другой пары. Например, условные варианты (5, 10), (7, 6) и (9, 4) образуют антицепь. Уменьшение времени здесь требует большей цены. А вариант (8, 11) уступает (5, 10) по обоим показателям, и его можно исключить, если нас интересуют только цена и время.
Фронт Парето состоит из тех заданных пар, для которых нет другой пары с обеими координатами не больше и хотя бы одной строго меньше. Различные пары на этом фронте образуют антицепь. Если бы две из них были сравнимы, худшая не попала бы на фронт. В нашем примере после удаления (8, 11) остаются все три несравнимых варианта.
Сам порядок не подсказывает, какой из этих трёх вариантов предпочесть. Для обоснованного выбора потребуется дополнительное правило, например сначала уложиться в заданный срок, а затем минимизировать цену.
#Математика #Разбор #МатематическиеИдеи