Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил
В статье приведены практические результаты создания программного комплекса «УДАВ», который реализует
 линейной вычислительной сложности матричный метод поиска маршрута логического вывода на миварной
 сети правил. Этот метод позволяет реализовать активный обучаемый логический вывод дл...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/8134 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил / А.В. Носов, А.Н. Владимиров, Т.С. Потапова, Е.Г. Колупаева, О.О. Варламов // Штучний інтелект. — 2009. — № 3. — С. 443-448. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860208741875449856 |
|---|---|
| author | Носов, А.В. Владимиров, А.Н. Потапова, Т.С. Колупаева, Е.Г. Варламов, О.О. |
| author_facet | Носов, А.В. Владимиров, А.Н. Потапова, Т.С. Колупаева, Е.Г. Варламов, О.О. |
| citation_txt | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил / А.В. Носов, А.Н. Владимиров, Т.С. Потапова, Е.Г. Колупаева, О.О. Варламов // Штучний інтелект. — 2009. — № 3. — С. 443-448. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| description | В статье приведены практические результаты создания программного комплекса «УДАВ», который реализует
линейной вычислительной сложности матричный метод поиска маршрута логического вывода на миварной
сети правил. Этот метод позволяет реализовать активный обучаемый логический вывод для любых
предметных областей, моделирование которых проводится в миварном информационном пространстве.
Реализация: в реальном времени и при любых наборах входных данных решаются геометрические задачи
решений треугольников с 33 объектами и 161 правилом (33! варианта), что ранее считалось невозможным.
У статті наведені практичні результати програмного комплексу «Удав», який реалізує лінійної обчислю-
вальної складності матричний метод пошуку маршруту логічного виводу на миварній сітці правил. Цей
метод дозволяє реалізувати активний научуваний логічний вивід для будь-яких предметних областей,
моделювання яких проводиться у миварному інформаційному просторі. Реалізація: в реальному часі і за
будь-яких наборів вхідних даних вирішуються геометричні задачі рішень трикутників з 33 об’єктами і
161 правилом (33! варіанти), що раніше вважалося неможливим.
An active trained logic conclusion for any subject spheres which modelling is carried out in mivar information
space is realized. As an example realization of "geometrical tasks of decisions of triangles" is shown. The
software "UDAV" is executed on technology Java and realizes "the universal maker of algorithms Varlamov"
which can be referred to a class of " intellectual packages of applied programs ".
|
| first_indexed | 2025-12-07T18:13:46Z |
| format | Article |
| fulltext |
«Штучний інтелект» 3’2009 443
8Н
УДК 004.82:007.52
А.В. Носов, А.Н. Владимиров, Т.С. Потапова, Е.Г. Колупаева, О.О. Варламов
ФГУП НИИ Радио, ООО «МИВАР», г. Москва, Россия
ovar@narod.ru
Программа «УДАВ»: реализация линейной
вычислительной сложности матричного
метода поиска маршрута логического
вывода на основе миварной сети правил
В статье приведены практические результаты создания программного комплекса «УДАВ», который реализует
линейной вычислительной сложности матричный метод поиска маршрута логического вывода на миварной
сети правил. Этот метод позволяет реализовать активный обучаемый логический вывод для любых
предметных областей, моделирование которых проводится в миварном информационном пространстве.
Реализация: в реальном времени и при любых наборах входных данных решаются геометрические задачи
решений треугольников с 33 объектами и 161 правилом (33! варианта), что ранее считалось невозможным.
Введение
Программный комплекс «УДАВ» реализует «универсальный делатель алгорит-
мов Варламова» на основе линейной вычислительной сложности матричного метода
поиска маршрута логического вывода [1]. Этот метод базируется на миварной логиче-
ской сети правил и предоставляет возможность активного обучения логического вывода,
управляемого потоком входных данных, со снижением вычислительной сложности с N!
до линейной: доказано практикой. «Удав. Геометрия» на обычной ПЭВМ в реальном вре-
мени решает задачи с 33 переменными (объектами) и 161 правилом, что ранее было
невозможным, т.к. здесь 33! (33 факториал) варианта [2]. «УДАВ. Геометрия» выполнен
по технологии Java, которая является объектно-ориентированной, платформо-независи-
мой, многопоточной средой программирования.
Общее описание технологии программы «УДАВ»
Целью данной работы является обоснование возможностей и практическое под-
тверждение решения сложных логических задач и обработки информации в реальном
масштабе времени и с линейной вычислительной сложностью.
«УДАВ» – это принципиально новый программный комплекс, предназначенный
для решения сложных логических задач и обработки информации в реальном ма-
сштабе времени. Новизна: автоматически формируется алгоритм решения задачи, кото-
рый на следующем этапе «выполняется» с конкретными исходными данными. Ранее
подобные алгоритмы относили к интеллектуальным пакетам прикладных программ
(ИППП). «УДАВ» полностью решает все проблемы ИППП и реализует все основные
идеи сервисно-ориентированной архитектуры (СОА).
Представление информации основано на продукционном подходе: любая предмет-
ная область описывается набором правил или процедур в формате «ЕСЛИ..., ТО...» (про-
дукции). Формируется перечень «объектов-переменных» и перечень «правил-процедур»
(это и логические правила, и процедуры обработки информации). Ограничение: если из-
Носов А.В., Владимиров А.Н., Потапова Т.С., Колупаева Е.Г., Варламов О.О.
«Искусственный интеллект» 3’2009 444
8Н
вестны все «входные» объекты-переменные (в правилах они стоят после «ЕСЛИ ...,» и до
«ТО...»), то должны быть выводимы и все «выходные» объекты-переменные (в правилах
они после «ТО»). Все задачи бизнес-аналитики могут быть представлены в таком виде.
Описание метода решения
Метод состоит в следующем. Формируется набор взаимосвязей – «правил» между
объектами предметной области: база данных объектов и база данных правил. Затем
системе «УДАВ» задают известные входные объекты и требуемые объекты, для ко-
торых надо определить алгоритм их получения из входных объектов (сформировать
маршрут логического вывода или «сделать алгоритм»). «УДАВ» по входным объектам
на основе базы данных всех правил формирует «алгоритм вывода».
Фактически решается классическая задача поиска маршрута логического вывода, но:
1) вычислительная сложность – линейная, а не NP-полная (факториал: N!), что
доказано математически и подтверждено на практике;
2) решаются и логические, и другие классы задач обработки информации;
3) «УДАВ» позволяет выполнять управляемую потоком данных активную обра-
ботку на адаптивной сети правил и переменных (самообучение).
Образно можно сказать следующее: решение основывается на отказе от полного
перебора всех вариантов путем «подъема над плоскостью лабиринта графа» и по-
строения специальных матриц, позволяющих анализировать «весь лабиринт графа»
в комплексе и быстро находить требуемые решения. «УДАВ» может работать с пол-
ностью автономными системами, т.е. автоматически обрабатывать входные значения
неких датчиков в реальном масштабе времени и на выходе выдавать сигналы по за-
данным параметрам, например: «аварийная ситуация» и т.п.
В качестве аналогии можно привести пример «рыбацкой сети»: сначала вяжут
рыболовную сеть, потом «наваливают кучей» сразу несколько сетей, а два рыбака
подходят к этой «куче» и тянут в разные стороны, один за «известные входные пере-
менные-объекты», другой – за «требуемые выводимые объекты-переменные».
Если в результате из этой «кучи» получается «растянуть» фрагмент целой сети,
связывающей входные и требуемые объекты, то задача решена: логический вывод
найден. Если же рыбаки «расходятся» с разными фрагментами сети, значит связи меж-
ду входными и требуемыми объектами нет: у задачи нет решения.
Можно в активном режиме определить те объекты, которые необходимо найти
для «связывания» сети в единый маршрут логического вывода.
Описание «УДАВ. Геометрия.
Решение задач в треугольниках»
Перейдем к решению задач школьной геометрии про треугольники. Известно
много зависимостей между сторонами, медианами, высотами, углами: теоремы сину-
сов, косинусов, Пифагора и т.п., формулы получения периметра, определения пло-
щади треугольника и т.д. Задачи различные: по двум сторонам и углу между ними
найти площадь; по высоте и стороне с углом определить другие стороны, построить
медианы и т.п. Получаем более 33 «объектов» и 160 «правил», описывающих взаи-
мосвязи объектов. Универсальных программ решения этих задач не было. «УДАВ.
Геометрия» позволяет автоматически решать «геометрические задачи в треугольниках».
Это пример решения вычислительных, а не логических задач с помощью УДАВа.
В нашей программе параметры треугольника будут являться переменными, а урав-
нения – правилами. Нахождение этих переменных возможно при различных начальных
Программа «Удав»: реализация линейной вычислительной сложности...
«Штучний інтелект» 3’2009 445
8Н
условиях. Например, если известны три стороны, или если известны две стороны и угол
между ними, или если известны два угла и сторона между ними, то мы можем найти
все остальные неизвестные параметры. Для расчёта параметров треугольника, т.е. на-
хождения неизвестных переменных, на вход программы подаются 2 списка: список
переменных и список правил. В списке существуют как переменные, обладающие
значениями, так и не обладающие ими. Некоторые из переменных, у которых нет зна-
чений, необходимо найти. Программа «УДАВ» просматривает список правил и ищет
среди них те, с помощью которых можно рассчитать искомые переменные (рис. 2).
После этого проверяется, достаточно ли известных переменных для расчёта правила.
Если параметров достаточно, то программа производит расчёт. Программа начинает
поиск заново, если:
– во время поиска найдено правило, с помощью которого можно найти искомую пе-
ременную и у него известны не все входные переменные, то недостающие переменные
помечаются как необходимые для поиска;
– во время поиска найдено правило, с помощью которого можно найти искомую пе-
ременную, и у него известны все входные переменные, то она помечается как извест-
ная, а правило удаляется.
Рисунок 2 – Обобщенный алгоритм программы «УДАВ. Геометрия»
Носов А.В., Владимиров А.Н., Потапова Т.С., Колупаева Е.Г., Варламов О.О.
«Искусственный интеллект» 3’2009 446
8Н
Работа программы считается законченной в том случае, если все искомые пере-
менные найдены или программа закончила обход правил, но не смогла найти ни од-
ного нового правила, с помощью которого можно найти неизвестную переменную.
В этом случае не хватает либо начальных данных, либо правил.
В главном окне (рис. 3) мы видим таблицу исходных данных – это поля (иден-
тификатор переменной, описание переменной, значение и поле для выделения искомой
переменной). Слева и справа находятся текстовый и графический выводы работы
программы соответственно.
Рисунок 3 – Внешний вид интерфейса без результатов расчёта
Существует область «parametrs», в которой описывается каждая переменная треу-
гольника и некоторая область «rules», в которой описаны правила для нахождения
переменных. Поле «parametr» состоит из: id – идентификатор переменной; value –
значение переменной; description – описание переменной. Поле «rule» состоит из: id –
идентификатор правила; resultId – идентификатор переменной, которую можно найти
из правила; initId – идентификаторы переменных, необходимых для выполнения прави-
ла; value – само правило; description – описание правила.
Преимуществом программы «УДАВ» является то, что для увеличения числа пере-
менных или правил не надо изменять программу. Это может сделать любой пользо-
ватель: необходимо открыть текстовый файл, где описаны параметры и правила, и
добавить туда нужную строку (рис. 4).
<?xml version="1.0" encoding="UTF-8" ?>
- <root>
- <parametrs>
<parametr id="P1" value="0.0" description="Угол A, против. стороне a (град)" />
<parametr id="P2" value="0.0" description="Угол B, против. стороне b (град)" />
<parametr id="P3" value="0.0" description="Угол C, против. стороне c (град)" />
...
</parametrs>
- <rules>
<rule id="R1" resultId="P1" initId="P2,P3" value="180-P2-P3" description="Сумма" />
<rule id="R2" resultId="P2" initId="P1,P3" value="180-P1-P3" description="Сумма" />
<rule id="R3" resultId="P3" initId="P1,P2" value="180-P1-P2" description="Сумма" />
...
</rules>
- <metadata>
<idParametr inc="33" />
<idRule inc="161" />
</metadata>
</root>
Рисунок 4 – Пример записи переменных и правил в файл формата XML
Программа «Удав»: реализация линейной вычислительной сложности...
«Штучний інтелект» 3’2009 447
8Н
Для начала расчета пользователю предлагается ввести исходные данные и выбрать
переменные, которые необходимо найти (рис. 5). Для демонстрации были введены следу-
ющие параметры: P1 (Угол а) = 30 град, P2 (Угол b) = 70 град, P4 (Сторона а) = 5. Выделены
следующие параметры для поиска: P9 (радиус вписанной окружности), P15 (высота,
опущенная из угла А на сторону а), P21 (биссектриса угла а), P27 (расстояние от точки
пересечения медианы стороны а до точки пересечения медиан).
По мере расчёта программа составляет текстовое описание своей работы (рис. 6),
где отображаются все обращения к переменным и правилам. Программа составляет
графическое представление своих расчётов в виде дерева (рис. 7), где графически пред-
ставлен порядок вычислений переменных и использованных правил, по которым они
были рассчитаны. Программу можно оптимизировать под любую задачу.
Выводы
Созданная программа «Удав. Геометрия» на основе миварного подхода адап-
тивно и с обучением в реальном времени решает сложные логические задачи, которые
ранее считались NP-полными. Фактически, программа «УДАВ» автоматически «де-
лает алгоритмы» для решения любой задачи, описанной в миварном информационном
пространстве [2].
Рисунок 5 – Внешний вид интерфейса с введенными данными
Рисунок 6 – Внешний вид интерфейса после расчета
Носов А.В., Владимиров А.Н., Потапова Т.С., Колупаева Е.Г., Варламов О.О.
«Искусственный интеллект» 3’2009 448
8Н
Рисунок 7 – Внешний вид интерфейса после расчета
Литература
1. Варламов О.О. Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных
систем. Миварное информационное пространство / Варламов О.О. – М. : Радио и связь, 2002. – 288 с.
2. Материалы сайта «дтн Варламов О.О.» [Електроный ресурс] / О.О. Варламов. – Режим доступа :
www.ovar.narod.ru.
А.В. Носов, А.Н. Владимиров, Т.С. Потапова, Е.Г. Колупаєва, О.О. Варламов
Програма «УДАВ»: реалізація лінейної обчислювальної складності матричного методу
пошуку маршруту логічного висновку на основі миварної сітки правил
У статті наведені практичні результати програмного комплексу «Удав», який реалізує лінійної обчислю-
вальної складності матричний метод пошуку маршруту логічного виводу на миварній сітці правил. Цей
метод дозволяє реалізувати активний научуваний логічний вивід для будь-яких предметних областей,
моделювання яких проводиться у миварному інформаційному просторі. Реалізація: в реальному часі і за
будь-яких наборів вхідних даних вирішуються геометричні задачі рішень трикутників з 33 об’єктами і
161 правилом (33! варіанти), що раніше вважалося неможливим.
A.V. Nosov, A.N. Vladimirov, T.S. Potapova, E.G. Kolupaeva, O.O. Varlamov
The Program Complex «UDAV»: Realization of Linear Computing Complexity of the Matrix
Method of Route Searching of the Logic Conclusion on the Basis of Mivarnoi Network of Rules
An active trained logic conclusion for any subject spheres which modelling is carried out in mivar information
space is realized. As an example realization of "geometrical tasks of decisions of triangles" is shown. The
software "UDAV" is executed on technology Java and realizes "the universal maker of algorithms Varlamov"
which can be referred to a class of " intellectual packages of applied programs ".
Статья поступила в редакцию 31.05.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8134 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:13:46Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Носов, А.В. Владимиров, А.Н. Потапова, Т.С. Колупаева, Е.Г. Варламов, О.О. 2010-04-30T15:39:52Z 2010-04-30T15:39:52Z 2009 Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил / А.В. Носов, А.Н. Владимиров, Т.С. Потапова, Е.Г. Колупаева, О.О. Варламов // Штучний інтелект. — 2009. — № 3. — С. 443-448. — Бібліогр.: 2 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8134 004.82:007.52 В статье приведены практические результаты создания программного комплекса «УДАВ», который реализует
 линейной вычислительной сложности матричный метод поиска маршрута логического вывода на миварной
 сети правил. Этот метод позволяет реализовать активный обучаемый логический вывод для любых
 предметных областей, моделирование которых проводится в миварном информационном пространстве.
 Реализация: в реальном времени и при любых наборах входных данных решаются геометрические задачи
 решений треугольников с 33 объектами и 161 правилом (33! варианта), что ранее считалось невозможным. У статті наведені практичні результати програмного комплексу «Удав», який реалізує лінійної обчислю-
 вальної складності матричний метод пошуку маршруту логічного виводу на миварній сітці правил. Цей
 метод дозволяє реалізувати активний научуваний логічний вивід для будь-яких предметних областей,
 моделювання яких проводиться у миварному інформаційному просторі. Реалізація: в реальному часі і за
 будь-яких наборів вхідних даних вирішуються геометричні задачі рішень трикутників з 33 об’єктами і
 161 правилом (33! варіанти), що раніше вважалося неможливим. An active trained logic conclusion for any subject spheres which modelling is carried out in mivar information
 space is realized. As an example realization of "geometrical tasks of decisions of triangles" is shown. The
 software "UDAV" is executed on technology Java and realizes "the universal maker of algorithms Varlamov"
 which can be referred to a class of " intellectual packages of applied programs ". ru Інститут проблем штучного інтелекту МОН України та НАН України Прикладные интеллектуальные системы Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил Програма «УДАВ»: реалізація лінейної обчислювальної складності матричного методу пошуку маршруту логічного висновку на основі миварної сітки правил The Program Complex «UDAV»: Realization of Linear Computing Complexity of the Matrix Method of Route Searching of the Logic Conclusion on the Basis of Mivarnoi Network of Rules Article published earlier |
| spellingShingle | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил Носов, А.В. Владимиров, А.Н. Потапова, Т.С. Колупаева, Е.Г. Варламов, О.О. Прикладные интеллектуальные системы |
| title | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| title_alt | Програма «УДАВ»: реалізація лінейної обчислювальної складності матричного методу пошуку маршруту логічного висновку на основі миварної сітки правил The Program Complex «UDAV»: Realization of Linear Computing Complexity of the Matrix Method of Route Searching of the Logic Conclusion on the Basis of Mivarnoi Network of Rules |
| title_full | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| title_fullStr | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| title_full_unstemmed | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| title_short | Программа «УДАВ»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| title_sort | программа «удав»: реализация линейной вычислительной сложности матричного метода поиска маршрута логического вывода на основе миварной сети правил |
| topic | Прикладные интеллектуальные системы |
| topic_facet | Прикладные интеллектуальные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8134 |
| work_keys_str_mv | AT nosovav programmaudavrealizaciâlineinoivyčislitelʹnoisložnostimatričnogometodapoiskamaršrutalogičeskogovyvodanaosnovemivarnoisetipravil AT vladimirovan programmaudavrealizaciâlineinoivyčislitelʹnoisložnostimatričnogometodapoiskamaršrutalogičeskogovyvodanaosnovemivarnoisetipravil AT potapovats programmaudavrealizaciâlineinoivyčislitelʹnoisložnostimatričnogometodapoiskamaršrutalogičeskogovyvodanaosnovemivarnoisetipravil AT kolupaevaeg programmaudavrealizaciâlineinoivyčislitelʹnoisložnostimatričnogometodapoiskamaršrutalogičeskogovyvodanaosnovemivarnoisetipravil AT varlamovoo programmaudavrealizaciâlineinoivyčislitelʹnoisložnostimatričnogometodapoiskamaršrutalogičeskogovyvodanaosnovemivarnoisetipravil AT nosovav programaudavrealízacíâlíneinoíobčislûvalʹnoískladnostímatričnogometodupošukumaršrutulogíčnogovisnovkunaosnovímivarnoísítkipravil AT vladimirovan programaudavrealízacíâlíneinoíobčislûvalʹnoískladnostímatričnogometodupošukumaršrutulogíčnogovisnovkunaosnovímivarnoísítkipravil AT potapovats programaudavrealízacíâlíneinoíobčislûvalʹnoískladnostímatričnogometodupošukumaršrutulogíčnogovisnovkunaosnovímivarnoísítkipravil AT kolupaevaeg programaudavrealízacíâlíneinoíobčislûvalʹnoískladnostímatričnogometodupošukumaršrutulogíčnogovisnovkunaosnovímivarnoísítkipravil AT varlamovoo programaudavrealízacíâlíneinoíobčislûvalʹnoískladnostímatričnogometodupošukumaršrutulogíčnogovisnovkunaosnovímivarnoísítkipravil AT nosovav theprogramcomplexudavrealizationoflinearcomputingcomplexityofthematrixmethodofroutesearchingofthelogicconclusiononthebasisofmivarnoinetworkofrules AT vladimirovan theprogramcomplexudavrealizationoflinearcomputingcomplexityofthematrixmethodofroutesearchingofthelogicconclusiononthebasisofmivarnoinetworkofrules AT potapovats theprogramcomplexudavrealizationoflinearcomputingcomplexityofthematrixmethodofroutesearchingofthelogicconclusiononthebasisofmivarnoinetworkofrules AT kolupaevaeg theprogramcomplexudavrealizationoflinearcomputingcomplexityofthematrixmethodofroutesearchingofthelogicconclusiononthebasisofmivarnoinetworkofrules AT varlamovoo theprogramcomplexudavrealizationoflinearcomputingcomplexityofthematrixmethodofroutesearchingofthelogicconclusiononthebasisofmivarnoinetworkofrules |