Введение в схемы, автоматы и алгоритмы

             

Сокращенные УБДР - часть 2


Доказательство леммы проведем индукцией по высоте h поддиаграмм Dv и Dw с корнями v и w, соответственно (так как Dv и Dw изоморфны, то их высоты, т.е. длины максимальных путей из корней до стоков, одинаковы).

Базис: h=1. В этом случае 0- и 1-сыновьями вершин v и w являются одинаковые стоки.

Шаг индукции. Предположим, что утверждение верно для h=k. Пусть Dv и Dw - поддиаграммы высоты h=k+1. Пусть v0 и w0 - это 0-сыновья вершин v и w, соответственно, а v1 и w1 - их 1-сыновья. Если v0=w0 и v1=w1, то в качестве v', w' подходят сами v и w. Если же для некоторого i

{0,1} vi
wi, то поддиаграммы
D_{v_i}
и
D_{w_i}
с корнями vi и wi являются изоморфными и имеют высоту k. Тогда по предположению индукции утверждение леммы выполнено.

Из теоремы 3.1 непосредственно следует, что, применяя к произвольной УБДР правила сокращения и слияния, мы, в конце концов, получим сокращенную УБДР. Чтобы эта процедура работала эффективо, нужно применять правила в порядке "снизу-вверх". Мы опишем этот алгоритм для "естественного" порядка переменных: x1, … , xn.

Алгоритм СОКРАЩЕНИЕ-УБДР

Вход: УБДР D для функции f(x1, … , xn).

Выход: сокращенная УБДР для

f
.

1. Занумеруем множество вершин D: V = {v1, v2, …, vm}; 2. ДЛЯ i = n, n-1, …, 1 ВЫПОЛНЯТЬ 3. { 4. V(i) = { v | v помечена переменной xi }; /* Применение правила сокращения: 5. ДЛЯ КАЖДОЙ v

V(i) ВЫПОЛНЯТЬ 6. ЕСЛИ (0-сын v) = (1-сын v) = w ТО} 7. { удалить v из V(i); 8. перенаправить все ребра, входящие в v, в вершину w; 9. удалить v из D } 10. ИНАЧЕ key(v) = (j, k), где vj - это 0-сын v, а vk - 1-сын v; /* Применение правила слияния: 11. Отсортировать V(i) по ключу key(v): пусть в этом порядке V(i)={ u1, …, uki}; 12. тек_ключ=(0, 0); 13. ДЛЯ j = 1, …, ki ВЫПОЛНЯТЬ 14. ЕСЛИ тек_ключ=key(uj) ТО 15. { удалить uj из V(i); 16. перенаправить все ребра, входящие в uj, в тек_вершина; 17. удалить uj из D } 18. ИНАЧЕ} {тек_вершина= uj; тек_ключ=key(uj)} 19. }

Пример 3.1. Рассмотрим пример применения алгоритма СОКРАЩЕНИЕ-УБДР, показанный на следующем рисунке.




Содержание  Назад  Вперед