Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації
Дана робота є першою в циклі трьох статей, присвячених проблемі оцінки складності логічних дерев класифікації та розробці універсально підходу їх оптимізації. Проаналізований зв’язок логічних функцій та логічних дерев розпізнавання, на основі якого запропоновано досить простий спосіб мінімізації лог...
Gespeichert in:
| Veröffentlicht in: | Штучний інтелект |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/58820 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації / Ф.Г. Ващук, Ю.А. Василенко, І.Ф. Повхан, Л.С. Повхан // Штучний інтелект. — 2011. — № 1. — С. 141-146. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860127756802588672 |
|---|---|
| author | Ващук, Ф.Г. Василенко, Ю.А. Повхан, І.Ф. Повхан, Л.С. |
| author_facet | Ващук, Ф.Г. Василенко, Ю.А. Повхан, І.Ф. Повхан, Л.С. |
| citation_txt | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації / Ф.Г. Ващук, Ю.А. Василенко, І.Ф. Повхан, Л.С. Повхан // Штучний інтелект. — 2011. — № 1. — С. 141-146. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Дана робота є першою в циклі трьох статей, присвячених проблемі оцінки складності логічних дерев класифікації та розробці універсально підходу їх оптимізації. Проаналізований зв’язок логічних функцій та логічних дерев розпізнавання, на основі якого запропоновано досить простий спосіб мінімізації логічних дерев. Важливими перевагами даного способу мінімізації дерев є те, що з ним відносно просто працювати при великій кількості аргументів.
Данная работа первая в цикле трех статей, посвященных проблеме оценки сложности логических деревьев классификации и разработке эффективного подхода их оптимизации. Проанализирована связь логических функций и логических деревьев распознавания, на основании которых предложен довольно простой способ минимизации логических деревьев. Важными преимуществами данного метода минимизации деревьев есть то, что с ним относительно просто работать при большом количестве аргументов.
The given work is the first in a cycle of three articles devoted to the problem of estimation of complexity of logic trees of classification and elaboration of universal approach of their optimization. Connection of logic functions and logic trees of recognition is analysed and on basis of this connection enough simple way of minimization of logic trees is offered. Important advantages of the given method of minimization of trees is that it is rather easy to work with it at a considerable quantity of arguments.
|
| first_indexed | 2025-12-07T17:42:41Z |
| format | Article |
| fulltext |
«Штучний інтелект» 1’2011 141
2В
УДК 004.89:004.93
Ф.Г. Ващук, Ю.А. Василенко, І.Ф. Повхан, Л.С. Повхан
Закарпатський державний університет, м. Ужгород, Україна
zakdu@ukrpost.edu.ua
Проблема оцінки
складності логічних дерев розпізнавання
та загальний метод їх оптимізації
Дана робота є першою в циклі трьох статей, присвячених проблемі оцінки складності логічних дерев
класифікації та розробці універсально підходу їх оптимізації. Проаналізований зв’язок логічних функцій
та логічних дерев розпізнавання, на основі якого запропоновано досить простий спосіб мінімізації логічних
дерев. Важливими перевагами даного способу мінімізації дерев є те, що з ним відносно просто працювати
при великій кількості аргументів.
Вступ
Як відомо, більшість синтезованих систем розпізнавання (СР) у вигляді дерев
класифікації можна записати або в ДНФ, або в КНФ формі. Так дерево розпізнаван-
ня, яке являє собою певне правило класифікації, можна представити за допомогою
відповідної логічної функції )...,,,( 21 nxxxfy . Отже важливою проблемою при по-
будові СР такого типу буде проблема синтезу логічної функції, яка еквівалентна да-
ному дереву розпізнавання [1], [2].
Так кількість усіх бінарних дерев, які фактично еквівалентні деякій логічній
функції )...,,,( 21 nxxxf , дорівнює !n – кількості перестановок, серед яких знаходить-
ся і саме складне. Під самим складним деревом будемо розуміти дерево, яке містить
максимальну кількість різних міток, тобто якщо маємо дерева D і *D та позначимо
кількість міток на цих деревах через )(DS і )( *DS , зафіксувавши при цьому деяке n,
то дерево *D буде максимальним (найскладнішим) тоді і тільки тоді, коли для нього
буде виконуватися рівність )(max)( * DSDS nn .
Головною метою даної роботи буде мінімізація фіксованого класу самих склад-
них дерев, причому нас буде цікавити знаходження не мінімальної форми, а най-
більш ефективний спосіб мінімізації (перестановки ярусів), який дає найбільше число
скорочених міток, іншими словами, спосіб, який значно зменшує складність почат-
кового логічного дерева [1], [3].
Задача полягає в проведенні такої мінімізації нижчевказаним способом до кін-
ця та знаходженні ефекту мінімізації, тобто відношення
SD
D0 , де 0D – найбільш склад-
не дерево, з якого починається процес мінімізації, а SD – дерево, отримане на S-му
(останньому) етапі мінімізації.
Ващук Ф.Г., Василенко Ю.А., Повхан І.Ф., Повхан Л.С.
«Искусственный интеллект» 1’2011 142
2В
Загальна схема логічної дерева
Перш за все побудуємо найбільш складне дерево.
Зауваження 1
Домовимося для зручності відлік ярусів починати з нульового. Нехай є довільне
дерево nD (блок розмірності )1( n змінних) з впорядкуванням )2...,,2,1,( k
ij ji
на останньому ярусі, причому ,jiij (рис. 1а, рис 1б).
a)
б)
Рисунок 1(а, б) – Дерево nD розмірності )1( n змінних з впорядкуванням ij
Причому k221 ...,,, – мітки, які також побудовані якимось способом. Але
вони є функціями, залежними від змінних miii xxx ...,,, 21 , які знаходяться на нижніх
ярусах (причому це твердження справедливе для довільної мітки дерева). В такому
Проблема оцінки складності логічних дерев розпізнавання та загальний метод...
«Штучний інтелект» 1’2011 143
2В
випадку добудоване дерево 122 222
mm
буде залежати вже від N змінних, де
N2...,,2,2,2 210 – кількість вершин, а
NNNNN 2222 2...,,2,2,2
21
– кількість функцій
(міток) відповідно на N...,,2,1,0 ярусах.
Слід відзначити наступний дуже важливий момент – зі збільшенням номера
ярусу кількість вершин збільшується, а кількість функцій зменшується, тому природ-
но зробити припущення, що настане такий момент, коли на якомусь i-му ярусі кіль-
кість вершин )2( i стане рівною кількості функцій )2( 2
iN
, які можна розставити в цих
вершинах, тобто:
iNi
222 . (1)
Критичний ярус логічного дерева
Введемо поняття критичного ярусу.
Визначення 1
Ярус i довільного дерева nD називається критичним, якщо всі його мітки різні.
Легко бачити, що ярус довільного дерева буде критичним тоді і тільки тоді,
коли для нього буде виконуватися умова (1). З усього вищесказаного випливає
наступна лема.
Лема 1
Якщо на i-му ярусі всі функції (мітки) різні між собою, то на )1(...,,2,1 i -му яру-
сі функції також будуть різними.
Зауваження 2
В подальшому критичний ярус будемо позначати через K , тоді для критичного
ярусу маємо наступне співвідношення:
KNK
222 . (2)
Таким чином, для того, щоб добудоване дерево nD було найбільш складним,
необхідно, щоб воно мало максимальне число різних міток, що, в свою чергу, рівно-
сильне тому, щоб дерево nD було найбільш складним, а це можливо в тому і лише в
тому випадку, (при даній структурі дерева), якщо всі i , які знаходяться на n-му
ярусі, будуть різними, тобто якщо n-й ярус буде критичним, так-як тоді (відповідно
лемі 1) всі мітки, які стоять вище критичного ярусу, будуть також різними. Але ви-
бране нами впорядкування )( jiijij на останньому ярусі таке, що забезпечує різ-
ні i на n-му ярусі, тому n-й ярус можна прийняти за критичний. Для справедливості
даного твердження достатньо показати, що для ярусу n умова (2) виконується, а для
)1( n -го яруса – вже ні. Знайдемо клас логічних дерев, які задовольняють рівність (2),
позначивши KN через m .
mKN . (3)
де mKN ,, цілі числа. Підставивши (3) у (2), отримуємо:
mK 222 . (4)
З (4) випливає (5).
mK 2 . (5)
Ващук Ф.Г., Василенко Ю.А., Повхан І.Ф., Повхан Л.С.
«Искусственный интеллект» 1’2011 144
2В
Підставивши значення K з (5) у (3) будемо мати mN m 2 , а отже
mN m 2 . (6)
Формула (6) при imm ...,,2,1 з врахуванням формули (5) дає нам клас най-
більш складних дерев.
Таблиця 1 – Клас найбільш складних дерев
m mK 2 mN m 2
1 2 3
2 4 6
3 8 11
. . .
. . .
im im2 i
m mi 2
Номер критичного ярусу знайдемо з рівняння (7).
xNx
222 , (7)
де xNx 2 , оскільки mN m 2 , то xmm
x 22 і остаточно:
Kx m 2 . (8)
Зробивши заміну в (2) К його значенням з (8), отримуємо рівність (2) в такому
виді:
mm 22 22 . (9)
Підрахувавши кількість вершин і функцій (міток) на )1( n ярусі, відповідно
твердженню kn маємо mnmkmN m 2 та
mnN . (10)
Тоді кількість вершин дорівнює кількості розгалужень
122 222
mm
, (11)
а кількість функцій (міток) буде
11)()1( 222 222
mnNnN
. (12)
Порівнявши (11) та (12), бачимо, що для )1( n -го ярусу рівність (2, 9) буде
порушуватися.
1212 22
mm
. (13)
(кількість вершин) (кількість функцій)
Отже n-й ярус буде критичним, тобто всі i , які знаходяться на ][Kn ярусі, різ-
ні. Таким чином, побудоване дерево nD буде самим складним. Разом з '
nD воно буде
належати класу самих складних дерев, в якому N визначається за формулою (6).
Зауваження 3
Кількість міток на 1K )1( n ярусі дорівнює
122
m
(12), оскільки для побу-
Проблема оцінки складності логічних дерев розпізнавання та загальний метод...
«Штучний інтелект» 1’2011 145
2В
дови впорядкування ij ми використали k2 міток: k221 ...,,, , – то зрозуміло, що
12 mk . (14)
Оцінимо складність дерева nD . Під складністю довільного дерева будемо розу-
міти кількість всіх різних міток дерева. Розрахунок будемо проводити наступним
чином: знаючи, що на кожному ярусі ])[...,,2,1,0( Kn кількість вершин відповідно
дорівнює K2...,,2,2,2 210 , а так як мітки, які знаходяться при даних вершинах, різні,
то і загальна кількість всіх міток буде дорівнювати сумі вершин на кожному ярусі, тобто
K2...222 210 .
За формулою геометричної прогресії
1
1
q
bqb
S n для 1q (в нашому випадку:
2,2,120
1 qbb K
n ), маємо наступну оцінку складності дерева nD :
1212
12
122
2...222 121210
mK
K
K ,
12 12 m
nD . (15)
Дослідимо зміни складності дерева nD , вважаючи його за початкове дерево
)( 0DDn . Скористаємося теоремою (без доведення) про перестановку змінних (яру-
сів), як приклад взявши функцію двох змінних [3-5].
Теорема 1
))();(())();(( 42131124322121 xxxxxx , тобто при перестановці ярусів 1x
та 2x мітки 2 та 3 міняються місцями (рис. 2).
Рисунок 2 – Схема перестановки ярусів при перестановці змінних
Так як задача полягає в знаходженні деякого способу мінімізації, який давав би
зменшення складності, то природно підібрати таку структуру розташування міток на
деякому i-му ярусі, щоб при мінімізації (перестановці ярусів) отримати найбільшу
кількість скорочень міток. Найбільш ефективною структурою є наступне розташу-
вання міток [6], [7].
k221 ...... . (*)
Ващук Ф.Г., Василенко Ю.А., Повхан І.Ф., Повхан Л.С.
«Искусственный интеллект» 1’2011 146
2В
Висновки
Тобто, якщо маємо дерево зі вказаною структурою (*) , то проробивши визна-
чене число кроків мінімізації, ми можемо розкласти його на два піддерева (підбло-
ки), які залежать від меншого числа змінних. Зважаючи на це загальна схема методу
мінімізації фіксованого класу логічних дерев базується на теоремі 1 та буде більш де-
тально проаналізована в наступній частині роботі.
Література
1. Василенко Ю.А. Алгоритмическое конструирование распознающих систем на основе метода раз-
ветвленного выбора признаков (метод РВП) / Ю.А. Василенко // Тез. докл. Третьей Всесоюзной
конференции «Математические методы в распознавании образов». – Львов, 1987. – С. 52-53.
2. Мінімізація логічних деревоподібних структур в задачах розпізнавання образів / І.Ф. Повхан,
Ю.А. Василенко, Е.Ю. Василенко [та ін.] // European Journal of Enterprise Technologies. – 2004. –
№ 3(9). – С. 12-16.
3. Construction and optimization of recongnizing systems / Yu.A. Vasilenko, E.Yu. Vasilenko, A. Kuhayivsky
[та ін.] // Інформаційні технології і системи. – 1999. – Т. 2, № 1. – С. 122-125.
4. Повхан І.Ф. Концептуальна основа систем розпізнавання образів на основі метода розгалуженого
вибору ознак / І.Ф. Повхан, Ю.А. Василенко, Е.Ю. Василенко // European Journal of Enterprise
Technologies. – 2004. – № 7(1). – С. 13-15.
5. Повхан І.Ф. Метод розгалуженого вибору ознак в математичному конструюванні багаторівневих
систем розпізнавання образів / І.Ф. Повхан, Василенко Ю.А., Василенко Е.Ю. // Штучний інтелект. –
2003. – № 7. – С. 246-249.
6. Витенько И.В. Схемы, алгоритмы и многообразия / Витенько И.В. – Ужгород : Ужгород. ун-т, 1970. –
76 с.
7. Вітенько І.В. Математична логіка / Вітенько І.В. – Ужгород : Ужгород. ун-т, 1971. – 210 с.
Ф.Г. Ващук, Ю.А. Василенко, И.Ф. Повхан, Л.С. Повхан
Проблема оценки сложности логических деревьев распознавания и общий метод их оптимизации
Данная работа первая в цикле трех статей, посвященных проблеме оценки сложности логических де-
ревьев классификации и разработке эффективного подхода их оптимизации. Проанализирована связь
логических функций и логических деревьев распознавания, на основании которых предложен довольно
простой способ минимизации логических деревьев. Важными преимуществами данного метода мини-
мизации деревьев есть то, что с ним относительно просто работать при большом количестве аргументов.
F.G. Vashchuk, J.A. Vasilenko, I.F. Povhan, L.S. Povhan
Problem of Estimation of Complexity of Logic Trees of Recognition and the General Method
of their Optimization
The given work is the first in a cycle of three articles devoted to the problem of estimation of complexity of
logic trees of classification and elaboration of universal approach of their optimization. Connection of logic
functions and logic trees of recognition is analysed and on basis of this connection enough simple way of
minimization of logic trees is offered. Important advantages of the given method of minimization of trees is
that it is rather easy to work with it at a considerable quantity of arguments.
Стаття надійшла до редакції 15.11.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58820 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:42:41Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Ващук, Ф.Г. Василенко, Ю.А. Повхан, І.Ф. Повхан, Л.С. 2014-03-31T11:32:37Z 2014-03-31T11:32:37Z 2011 Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації / Ф.Г. Ващук, Ю.А. Василенко, І.Ф. Повхан, Л.С. Повхан // Штучний інтелект. — 2011. — № 1. — С. 141-146. — Бібліогр.: 7 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58820 004.89:004.93 Дана робота є першою в циклі трьох статей, присвячених проблемі оцінки складності логічних дерев класифікації та розробці універсально підходу їх оптимізації. Проаналізований зв’язок логічних функцій та логічних дерев розпізнавання, на основі якого запропоновано досить простий спосіб мінімізації логічних дерев. Важливими перевагами даного способу мінімізації дерев є те, що з ним відносно просто працювати при великій кількості аргументів. Данная работа первая в цикле трех статей, посвященных проблеме оценки сложности логических деревьев классификации и разработке эффективного подхода их оптимизации. Проанализирована связь логических функций и логических деревьев распознавания, на основании которых предложен довольно простой способ минимизации логических деревьев. Важными преимуществами данного метода минимизации деревьев есть то, что с ним относительно просто работать при большом количестве аргументов. The given work is the first in a cycle of three articles devoted to the problem of estimation of complexity of logic trees of classification and elaboration of universal approach of their optimization. Connection of logic functions and logic trees of recognition is analysed and on basis of this connection enough simple way of minimization of logic trees is offered. Important advantages of the given method of minimization of trees is that it is rather easy to work with it at a considerable quantity of arguments. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації Проблема оценки сложности логических деревьев распознавания и общий метод их оптимизации Problem of Estimation of Complexity of Logic Trees of Recognition and the General Method of their Optimization Article published earlier |
| spellingShingle | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації Ващук, Ф.Г. Василенко, Ю.А. Повхан, І.Ф. Повхан, Л.С. Моделирование объектов и процессов |
| title | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| title_alt | Проблема оценки сложности логических деревьев распознавания и общий метод их оптимизации Problem of Estimation of Complexity of Logic Trees of Recognition and the General Method of their Optimization |
| title_full | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| title_fullStr | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| title_full_unstemmed | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| title_short | Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| title_sort | проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58820 |
| work_keys_str_mv | AT vaŝukfg problemaocínkiskladnostílogíčnihderevrozpíznavannâtazagalʹniimetodíhoptimízacíí AT vasilenkoûa problemaocínkiskladnostílogíčnihderevrozpíznavannâtazagalʹniimetodíhoptimízacíí AT povhaníf problemaocínkiskladnostílogíčnihderevrozpíznavannâtazagalʹniimetodíhoptimízacíí AT povhanls problemaocínkiskladnostílogíčnihderevrozpíznavannâtazagalʹniimetodíhoptimízacíí AT vaŝukfg problemaocenkisložnostilogičeskihderevʹevraspoznavaniâiobŝiimetodihoptimizacii AT vasilenkoûa problemaocenkisložnostilogičeskihderevʹevraspoznavaniâiobŝiimetodihoptimizacii AT povhaníf problemaocenkisložnostilogičeskihderevʹevraspoznavaniâiobŝiimetodihoptimizacii AT povhanls problemaocenkisložnostilogičeskihderevʹevraspoznavaniâiobŝiimetodihoptimizacii AT vaŝukfg problemofestimationofcomplexityoflogictreesofrecognitionandthegeneralmethodoftheiroptimization AT vasilenkoûa problemofestimationofcomplexityoflogictreesofrecognitionandthegeneralmethodoftheiroptimization AT povhaníf problemofestimationofcomplexityoflogictreesofrecognitionandthegeneralmethodoftheiroptimization AT povhanls problemofestimationofcomplexityoflogictreesofrecognitionandthegeneralmethodoftheiroptimization |