Пересечение матроидов: Расширение границ жадной оптимизации
Ранее мы выяснили, что если задача может быть математически описана структурой матроида (как задача о минимальном остовном дереве), то для ее идеального решения достаточно использовать самый банальный Жадный алгоритм. Однако в реальном мире, при составлении сложных расписаний инженерам часто приходится сталкиваться с ограничениями, поступающими сразу из нескольких разных систем правил. Как оптимизировать решение, удовлетворяющее сразу двум матроидам?
Эта проблема формализуется как Задача о пересечении двух матроидов. Дано одно множество элементов E (например, множество дорог), на котором заданы два совершенно разных независимых матроида: матроид M1 и матроид M2. Нам нужно найти самое большое множество элементов, которое будет являться независимым одновременно и в первом, и во втором матроиде.
Потрясающая математическая новость заключается в том, что задача пересечения двух матроидов решается строго за полиномиальное время! (Хотя жадный алгоритм здесь уже не работает напрямую, требуется более сложный алгоритм поиска увеличивающих цепей, разработанный Джеком Эдмонсом). Это открыло двери для эффективного решения огромного класса реальных ИТ-задач, которые ранее считались безнадежными.
Классический пример — задача нахождения максимального двудольного паросочетания. Представьте себе двудольный граф (доля таксистов и доля пассажиров). Множество E — это все возможные ребра между ними. Матроид M1 контролирует, чтобы к каждому таксисту шло не более одного ребра. Матроид M2 контролирует, чтобы к каждому пассажиру шло не более одного ребра. Пересечение этих двух структур — это математически идеальное распределение заказов.
Но на этом чудеса заканчиваются. Если к нашей системе добавить всего одно дополнительное ограничение — Пересечение трех матроидов — задача мгновенно и безвозвратно становится NP-полной! Доказано, что к пересечению трех матроидов легко сводится задача о поиске Гамильтонова пути (задача коммивояжера) и задача о раскраске графа.
Этот резкий переход от легкой полиномиальной задачи (2 матроида) к невычислимой NP-трудной (3 матроида) является одной из самых красивых границ в теоретической информатике. Алгоритмы пересечения двух матроидов сегодня используются в анализе структурной жесткости каркасов мостов, проектировании топологии надежных электросетей (поиск упакованных остовных деревьев) и маршрутизации защищенных сетевых туннелей в телекоммуникациях.
