На днях Кнут читал в Стенфорде очередную новогоднюю лекцию. Называлась она Fun with ZDD.
Впервые слышал его живьем, и должен сказать, что Кнут — классный дядька, хотя и очень плохой лектор. Ему гораздо интереснее был предмет лекции, чем состояние аудитории. Вместо запланированного часа лекция шла больше двух, и дослушать интеллектуальных сил хватило не всем.
Для тех, кто не знает про ZDD, поясню, в стиле лектора, что ZDD очень похожи на BDD, но с подавлением нулей (лектор также подчеркнул, что тем, кто не знает про BDD, будет понятнее).
Был описан очень интересный способ решения комбинаторных задач. Опять-таки, не могу удержаться от длинной цитаты. Один из примеров решал довольно большую задачу коммивояжера. Комментарий Кнута:
"Я не утверждаю, что могу решить задачу коммивояжера за полиномиальное время. Много лет назад мой научный руководитель объяснил мне, что комбинаторную проблему можно решить вручную до некоторого N. Компъютер позволяет решить ее для N+1. Потом пришел закон Мура, и эту проблему стало можно решить для N+3. ZDD позволяет продвинуться до N+5"
Итак, ZDD:
Семейство F выборок из упорядоченного множества (то есть, булеву функцию) можно описать следующим образом. Пусть v — минимальный элемент, поддержаный семейством. Тогда
F -> v
/ \
F0 F1
где F0 есть подсемейство выборок, не поддерживающих v, а F1 — все остальные (t.e. поддерживающие v), из которых, однако, v вычеркнут.
Применяя рекурсивно, семейство представляется в виде списка кортежей (v, lo, hi), где lo и hi — ссылки на левое и правое подсемейства. Важно осознавать, что если по ходу рекурсии некий кортеж встретился дважды, то это один и тот же кортеж. Отдельно в скобках надо добавить, что правая ссылка на пустое множество, и левая ссылка на тождественный ноль оптимизируют список еще больше.
Получившийся список и есть ZDD — Zero-suppressed (binary) Decision Diagram — которая, по словам Кнута (и по его убедительнейшим примерам), есть data structure of choice для решения комбинаторных задач. Прошу заметить, как элегантно рекурсируются в этой схеме обычные булевские операторы.
Я, строго говоря, не хотел пересказывать материал Кнута (но он, то есть Кнут (или материал?) засасывает). Хотел я, собственно, спросить: как часто вам приходится иметь дело с комбинаторными проблемами?
