В классическом императивном программировании изменение переменной или узла в дереве безвозвратно уничтожает старое значение. Если вам нужно отменить действие (Ctrl+Z), вам приходится заранее сохранять копию всей структуры, что катастрофически расходует оперативную память. В функциональном программировании и математической логике мутации запрещены. Для решения проблемы эффективного хранения истории изменений были придуманы персистентные структуры данных.

Ранее мы выяснили, что если задача может быть математически описана структурой матроида (как задача о минимальном остовном дереве), то для ее идеального решения достаточно использовать самый банальный Жадный алгоритм. Однако в реальном мире, при составлении сложных расписаний инженерам часто приходится сталкиваться с ограничениями, поступающими сразу из нескольких разных систем правил. Как оптимизировать решение, удовлетворяющее сразу двум матроидам?

Мы уже обсуждали задачу о минимальном разрезе (Min-Cut), которая изящно решается через алгоритмы максимального потока (или рандомизированный алгоритм Каргера). Кажется логичным, что если изменить слово "минимальный" на "максимальный", задача останется такой же легкой. Но в дискретной математике интуиция часто обманчива. Задача о Максимальном разрезе (Max-Cut) является одной из самых сложных NP-полных проблем, лежащей в основе статистической физики (модели спиновых стекол) и проектирования VLSI-чипов.