Кіріспе

Буль функцияларының дерек құрылымы

Компьютерлік ғылымда, екілік шешім диаграммасы (БДД) немесе тармақталу бағдарламасы – Буль функциясын ұсынуға қолданылатын дерек құрылымы. Көбірек абстрактілі деңгейде, БДД жиынтардың немесе қатынастардың сығылған түрі ретінде қарастырылуы мүмкін. Басқа сығылған түрлерден айырмашылығы, операциялар сығылған түрінде тікелей, яғни сығылудан босатусыз орындалады. Осыған ұқсас дерек құрылымдарына теріске шығару нормалық формасы (NNF), Жегалькин полиномдары және логикалық бағытталған ациклдік графтар (PDAG) жатады.

Анықтама

Бульдік функция бірнеше (шешім) түйіндер мен екі терминалды түйіннен тұратын тамырланған, бағытталған, ациклді граф ретінде көрсетілуі мүмкін. Екі терминалды түйін 0 (FALSE) және 1 (TRUE) деп белгіленеді. Әрбір (шешім) түйін Бульдік айнымалымен белгіленеді және төменгі ұл және жоғары ұл деп аталатын екі ұл түйінге ие. Түйінден төменгі (немесе жоғары) ұлға дейінгі қабырға айнымалыға FALSE (немесе сәйкесінше TRUE) мәнін беруді білдіреді. Егер түбірден барлық жолдарда әртүрлі айнымалылар бірдей ретпен келсе, мұндай BDD "реттелген" деп аталады. BDD "қысқартылған" деп есептеледі, егер келесі екі ереже оның графигіне қолданылса: кез келген изоморфты кішкентай графтарды біріктіру; екі ұлы изоморфты кез келген түйінді жою. Көпте қолданылатын термин БДД көбінесе Қысқартылған Реттелген Бинарлық Шешім Диаграммасын (әдебиетте РОБДД, реттілік және қысқарту аспектілерін баса көрсету қажет болғанда қолданылады) білдіреді. ROBDD-нің артықшылығы – ол белгілі бір функция мен айнымалылар реті үшін каноникалық (бірегей) болып табылады. Деректер құрылымына негізделген тиімді алгоритмдердің толық мүмкіндігін Карнеги Меллон университетінің Рандал Брайант зерттеді: оның негізгі кеңейтулері – каноникалық өрнектеу үшін тұрақты айнымалыларды және сығу үшін ортақ кішкентай графтарды пайдалану болды. Осы екі ұғымды қолдану жиындар мен қатынастарды көрсету үшін тиімді деректер құрылымы мен алгоритмдерді қамтамасыз етеді.

Өзгергіш реттілік

BDD-нің мөлшері бейнеленетін функциямен де, айнымалылардың таңдалған ретімен де анықталады. Айнымалылардың ретіне байланысты, түйіндер саны ең жақсы жағдайда сызықтық (n) және ең нашар жағдайда экспоненциалды болатын булелік функциялар бар (мысалы, толқынды көтеру қосылғышы). Булелік функцияны қарастырайық. Айырмалылардың ретін пайдаланып, BDD функцияны бейнелеу үшін түйіндер қажет. Ал, басқа ретті пайдаланса, BDD түйіндерден тұрады. Осы дерек құрылымын іс жүзінде қолданғанда айнымалылардың ретіне ерекше назар бөлу өте маңызды. Ең жақсы айнымалылар ретін табу мәселесі NP-қиын.