Алгоритм вычисления соединения в диаграмме двоичных решений с подавленным нулем - PullRequest
5 голосов
/ 30 августа 2011

Каков алгоритм для вычисления объединения двух диаграмм двоичных решений с подавленными нулями?

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

Я бы предпочел не разбираться с какой-либо конкретной реализацией; Я нахожу детали реализации очень отвлекающими.


Объединение ZDD f и g равно { a ∪ b | a ∈ f and b ∈ g }

1 Ответ

5 голосов
/ 30 августа 2011

В моей копии Искусство компьютерного программирования, том 4А этот точный вопрос поставлен как упражнение 205 в разделе 7.1.4. Это связано с двумя предыдущими вопросами, но ответы на все три находятся в конце книги. Возможно, вы захотите проверить это как ресурс.

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

Надеюсь, это поможет!

...